格雷码 Java python c++ C# 解法原理讲解

﹏ヽ暗。殇╰゛Y 2022-01-27 10:57 84阅读 0赞

例子：

以下是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<String> arr =` `new` `ArrayList<String> ();`

` `

`    ` `//初始一位存入`

`    ` `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` `)`

`    ` `{`

`        ` //反转后存入

`        ` `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<string> arr;`

`    ` `arr.push_back(` `"0"` `);`

`    ` `arr.push_back(` `"1"` `);`

` `

`    `

`    ` `int` `i, j;`

`    ` `for` `(i = 2; i < (1<<n); i = 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);`

`}`

` `

格雷码 Java python c++ C# 解法原理讲解

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关【Java】生成格雷码

相关十进制转格雷码 c语言,C语言输出格雷码

相关格雷码转十进制 c语言,格雷码的转换方法

相关 Gray Code（C++格雷编码）

相关格雷码

相关格雷码 Python编写

相关生成格雷码

相关生成格雷码 java实现

相关二进制转格雷码 - C语言代码实现

相关格雷码 Java python c++ C# 解法原理讲解