算法设计：生成n位灰度码 |set 2

本文概述

• 建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
• C ++
• Java
• Python3
• C#

给定数字n, 请生成从0到2 ^ n-1的位模式, 以使连续的模式相差一位。

例子：

Input: n=2
Output: 00 01 11 10
Every adjacent element of gray code differs 
only by one bit.
So the n bit grey codes are: 00 01 11 10

Input: n=3
Output: 000 001 011 010 110 111 101 100
Every adjacent element of gray code differs  
only by one bit.
So the n bit gray codes are:
 000 001 011 010 110 111 101 100

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

另一种方法生成n位灰度码已经讨论过了。

方法：

想法是使用XOR和Right shift操作获得二进制数的灰度码。

1. 灰度码的第一位(MSB)与二进制数的第一位(MSB)相同。
2. 灰度码的第二位(从左侧开始)等于二进制数的第一位(MSB)与第二位(2nd MSB)的XOR。
3. 灰度码的第三位(从左侧开始)等于第二位(第二MSB)和第三位(第三MSB)的XOR, 依此类推。

这样, 可以为相应的二进制数计算灰度码。因此, 可以观察到, 第i个元素可以由i和floor(i / 2)的按位XOR形成, 等于i和(i >> 1)的按位XOR, 即i右移1。通过执行此操作, 二进制数的MSB保持不变, 所有其他位与相邻的更高位按位进行XOR。

C ++

// C++ program to generate n-bit
// gray codes
#include <bits/stdc++.h>
using namespace std;
  
// Function to convert decimal to binary
void decimalToBinaryNumber( int x, int n)
{
     int * binaryNumber = new int (x);
     int i = 0;
     while (x > 0) {
         binaryNumber[i] = x % 2;
         x = x / 2;
         i++;
     }
  
     // leftmost digits are filled with 0
     for ( int j = 0; j < n - i; j++)
         cout << '0' ;
  
     for ( int j = i - 1; j >= 0; j--)
         cout << binaryNumber[j];
}
  
// Function to generate gray code
void generateGrayarr( int n)
{
     int N = 1 << n;
     for ( int i = 0; i < N; i++) {
  
         // generate gray code of corresponding
         // binary number of integer i.
         int x = i ^ (i >> 1);
  
         // printing gray code
         decimalToBinaryNumber(x, n);
  
         cout << endl;
     }
}
  
// Drivers code
int main()
{
     int n = 3;
     generateGrayarr(n);
     return 0;
}

Java

// Java program to generate
// n-bit gray codes
import java.io.*;
  
class GFG {
  
     // Function to convert
     // decimal to binary
     static void decimalToBinaryNumber( int x, int n)
     {
         int [] binaryNumber = new int [x];
         int i = 0 ;
         while (x > 0 ) {
             binaryNumber[i] = x % 2 ;
             x = x / 2 ;
             i++;
         }
  
         // leftmost digits are
         // filled with 0
         for ( int j = 0 ; j < n - i; j++)
             System.out.print( '0' );
  
         for ( int j = i - 1 ;
              j >= 0 ; j--)
             System.out.print(binaryNumber[j]);
     }
  
     // Function to generate
     // gray code
     static void generateGrayarr( int n)
     {
         int N = 1 << n;
         for ( int i = 0 ; i < N; i++) {
  
             // generate gray code of
             // corresponding binary
             // number of integer i.
             int x = i ^ (i >> 1 );
  
             // printing gray code
             decimalToBinaryNumber(x, n);
  
             System.out.println();
         }
     }
  
     // Driver code
     public static void main(String[] args)
     {
         int n = 3 ;
         generateGrayarr(n);
     }
}
  
// This code is contributed
// by anuj_67.

Python3

# Python program to generate
# n-bit gray codes
  
# Function to convert
# decimal to binary
def decimalToBinaryNumber(x, n):
     binaryNumber = [ 0 ] * x;
     i = 0 ;
     while (x > 0 ):
         binaryNumber[i] = x % 2 ;
         x = x / / 2 ;
         i + = 1 ;
  
     # leftmost digits are
     # filled with 0
     for j in range ( 0 , n - i):
         print ( '0' , end = "");
  
     for j in range (i - 1 , - 1 , - 1 ):
         print (binaryNumber[j], end = "");
  
# Function to generate
# gray code
def generateGrayarr(n):
     N = 1 << n;
     for i in range (N):
          
         # generate gray code of
         # corresponding binary
         # number of integer i.
         x = i ^ (i >> 1 );
  
         # printing gray code
         decimalToBinaryNumber(x, n);
  
         print ();
  
# Driver code
if __name__ = = '__main__' :
     n = 3 ;
     generateGrayarr(n);
  
# This code is contributed by 29AjayKumar

C#

// C# program to generate
// n-bit gray codes
using System;
  
class GFG {
  
     // Function to convert
     // decimal to binary
     static void decimalToBinaryNumber( int x, int n)
     {
         int [] binaryNumber = new int [x];
         int i = 0;
         while (x > 0) {
             binaryNumber[i] = x % 2;
             x = x / 2;
             i++;
         }
  
         // leftmost digits are
         // filled with 0
         for ( int j = 0; j < n - i; j++)
             Console.Write( '0' );
  
         for ( int j = i - 1;
              j >= 0; j--)
             Console.Write(binaryNumber[j]);
     }
  
     // Function to generate
     // gray code
     static void generateGrayarr( int n)
     {
         int N = 1 << n;
         for ( int i = 0; i < N; i++) {
  
             // Generate gray code of
             // corresponding binary
             // number of integer i.
             int x = i ^ (i >> 1);
  
             // printing gray code
             decimalToBinaryNumber(x, n);
  
             Console.WriteLine();
         }
     }
  
     // Driver code
     public static void Main()
     {
         int n = 3;
         generateGrayarr(n);
     }
}
  
// This code is contributed
// by anuj_67.

输出如下：

000
001
011
010
110
111
101
100

复杂度分析：

• 时间复杂度：上)。
  从0到(n-1)只需一个遍历。
• 辅助空间：O(对数x)。
  (x)的二进制表示需要空格(log x)。

---