FilesExpand file tree

 master

/

grayCode.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

152 lines (141 loc) · 3.36 KB

 master

/

grayCode.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

152 lines (141 loc) · 3.36 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

// Source : https://oj.leetcode.com/problems/gray-code/

// Author : Hao Chen

// Date : 2014-06-20

/**********************************************************************************

*

* The gray code is a binary numeral system where two successive values differ in only one bit.

*

* Given a non-negative integer n representing the total number of bits in the code,

* print the sequence of gray code. A gray code sequence must begin with 0.

*

* For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

*

* 00 - 0

* 01 - 1

* 11 - 3

* 10 - 2

*

* Note:

* For a given n, a gray code sequence is not uniquely defined.

*

* For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

*

* For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

*

**********************************************************************************/

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <iostream>

#include <vector>

using namespace std;

/*

* I designed the following stupid algorithm base on the blow observation

*

* I noticed I can use a `mirror-like` binary tree to figure out the gray code.

*

* For example:

*

* 0

* __/ \__

* 0 1

* / \ / \

* 0 1 1 0

* So, the gray code as below: (top-down, from left to right)

*

* 0 0 0

* 0 0 1

* 0 1 1

* 0 1 0

*

* 0

* _____/ \_____

* 0 1

* __/ \__ __/ \__

* 0 1 1 0

* / \ / \ / \ / \

* 0 1 1 0 0 1 1 0

*

* So, the gray code as below:

*

* 0 0 0 0

* 0 0 0 1

* 0 0 1 1

* 0 0 1 0

* 0 1 1 0

* 0 1 1 1

* 0 1 0 1

* 0 1 0 0

*/

vector<int> grayCode01(int n) {

vector<int> v;

//n = 1<<n;

int x =0;

v.push_back(x);

for(int i=0; i<n; i++){

int len = v.size();

for (int j=0; j<len; j++){

x = v[j]<<1;

if (j%2==0){

v.push_back(x);

v.push_back(x+1);

}else{

v.push_back(x+1);

v.push_back(x);

}

}

v.erase(v.begin(), v.begin()+len);

}

return v;

}

/*

* Actually, there is a better way.

* The mathematical way is: (num >> 1) ^ num;

* Please refer to http://en.wikipedia.org/wiki/Gray_code

*/

vector<int> grayCode02(int n) {

vector<int> ret;

int size = 1 << n;

for(int i = 0; i < size; ++i) {

ret.push_back((i >> 1)^i);

}

return ret;

}

//random invoker

vector<int> grayCode(int n) {

srand(time(0));

if (rand()%2){

return grayCode01(n);

}

return grayCode02(n);

}

void printBits(int n, int len){

for(int i=len-1; i>=0; i--) {

if (n & (1<<i)) {

printf("1");

}else{

printf("0");

}

}

}

void printVector(vector<int>& v, int bit_len)

{

vector<int>::iterator it;

for(it=v.begin(); it!=v.end(); ++it){

//bitset<bit_len> bin(*it);

printBits(*it, bit_len);

cout << " ";

//cout << *it << " ";

}

cout << endl;

}

int main(int argc, char** argv)

{

int n = 2;

if (argc>1){

n = atoi(argv[1]);

}

vector<int> v = grayCode(n);

printVector(v, n);

return 0;

}