例子：??
以下是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);
}
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
