算法设计(生成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 10Input: 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

【算法设计(生成n位灰度码 |set 2)】复杂度分析:
  • 时间复杂度:上)。
    从0到(n-1)只需一个遍历。
  • 辅助空间:O(对数x)。
    (x)的二进制表示需要空格(log x)。

    推荐阅读