例子：
以下是2位序列（n = 2）
00 01 11 10
以下是3位序列（n = 3）
000 001 011 010 110 111 101 100
以下是4位序列（n = 4）
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111
1110 1010 1011 1001 1000
可以使用以下步骤从（n-1）位格雷码列表生成n位格雷码。
1
令（n-1）位格雷码列表为L1。 创建另一个与L1相反的列表L2。
2
通过在L1的所有代码中加上前缀“0”来修改列表L1。
3
通过在L2的所有代码中加上前缀“1”来修改列表L2。
4
连接L1和L2。 连接列表是n位格雷码的必需列表。
例如，以下是从2位格雷码列表中生成3位格雷码列表的步骤。
L1 = {00,01,11,10}（2位格雷码列表）
L2 = {10,11,01,00}（L1的反向）
用“0”前缀L1的所有条目，L1变为{000,001,011,010}
用“1”前缀L2的所有条目，L2变为{110,111,101,100}
连接L1和L2，得到{000,001,011,010,110,111,101,100}
为了生成n位格雷码，我们从1位格雷码列表开始。 1位格雷码的列表是{0,1}。 我们重复上述步骤，从1位格雷码生成2位格雷码，然后从2位格雷码生成3位格雷码，直到位数等于n。 以下是这种方法的实施。
解法思想为分治法
java解法
import
java.util.*;
class
GfG {
static
void
generateGrayarr(
int
n)
{
// base case
if
(n <=
0
)
return
;
// 'arr' will store all generated codes
ArrayList
new
ArrayList
//初始一位存入
arr.add(
"0"
);
arr.add(
"1"
);
// Every iteration of this loop generates 2*i codes from previously
// generated i codes.
int
i, j;
for
(i =
2
; i < (
1
<
1
)
{
//反转后存入
for
(j = i-
1
; j >=
0
; j--)
arr.add(arr.get(j));
//L1前加0
for
(j =
0
; j < i ; j++)
arr.set(j,
"0"
+ arr.get(j));
//L2前加1
for
(j = i ; j <
2
*i ; j++)
arr.set(j,
"1"
+ arr.get(j));
}
// 输出
for
(i =
0
; i < arr.size() ; i++ )
System.out.println(arr.get(i));
}
// 测试
public
static
void
main(String[] args)
{
generateGrayarr(
3
);
}
}
C++解法
void
generateGrayarr(
int
n)
{
if
(n <= 0)
return
;
vector
arr.push_back(
"0"
);
arr.push_back(
"1"
);
int
i, j;
for
(i = 2; i < (1<
{
//反转
for
(j = i-1 ; j >= 0 ; j--)
arr.push_back(arr[j]);
//L1前加0
for
(j = 0 ; j < i ; j++)
arr[j] =
"0"
+ arr[j];
//L2前加1
for
(j = i ; j < 2*i ; j++)
arr[j] =
"1"
+ arr[j];
}
// 输出
for
(i = 0 ; i < arr.size() ; i++ )
cout << arr[i] << endl;
}
//测试
int
main()
{
generateGrayarr(3);
return
0;
}
python解法
def
generateGrayarr(n):
# base case
if
(n <
=
0
):
return
# 'arr' will store all generated codes
arr
=
list
()
# start with one-bit pattern
arr.append(
"0"
)
arr.append(
"1"
)
# Every iteration of this loop generates
# 2*i codes from previously generated i codes.
i
=
2
j
=
0
while
(
True
):
if
i >
=
1
<< n:
break
# Enter the prviously generated codes
# again in arr[] in reverse order.
# Nor arr[] has double number of codes.
for
range
j
(i
-
1
,
-
1
,
-
1
):
arr.append(arr[j])
# append 0 to the first half
for
range
j
(i):
arr[j]
=
"0"
+
arr[j]
# append 1 to the second half
for
range
j
(i,
2
*
i):
arr[j]
=
"1"
+
arr[j]
i
=
i <<
1
# prcontents of arr[]
for
range
i
(
len
(arr)):
print
(arr[i])
# Driver Code
generateGrayarr(
3
)
C#解法
using
System;
using
System.Collections.Generic;
// C# program to generate n-bit Gray codes
public
class
GfG
{
// This function generates all n bit Gray codes and prints the
// generated codes
public
static
void
generateGrayarr(
int
n)
{
// base case
if
(n <= 0)
{
return
;
}
// 'arr' will store all generated codes
List<
string
> arr =
new
List<
string
> ();
// start with one-bit pattern
arr.Add(
"0"
);
arr.Add(
"1"
);
// Every iteration of this loop generates 2*i codes from previously
// generated i codes.
int
i, j;
for
(i = 2; i < (1 << n); i = i << 1)
{
// Enter the prviously generated codes again in arr[] in reverse
// order. Nor arr[] has double number of codes.
for
(j = i - 1 ; j >= 0 ; j--)
{
arr.Add(arr[j]);
}
// append 0 to the first half
for
(j = 0 ; j < i ; j++)
{
arr[j] =
"0"
+ arr[j];
}
// append 1 to the second half
for
(j = i ; j < 2 * i ; j++)
{
arr[j] =
"1"
+ arr[j];
}
}
// print contents of arr[]
for
(i = 0 ; i < arr.Count ; i++)
{
Console.WriteLine(arr[i]);
}
}
// Driver program to test above function
public
static
void
Main(
string
[] args)
{
generateGrayarr(3);
}
}
