本文概述
- 建议:在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
- C ++
- Java
- Python3
- C#
例子:
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操作获得二进制数的灰度码。
- 灰度码的第一位(MSB)与二进制数的第一位(MSB)相同。
- 灰度码的第二位(从左侧开始)等于二进制数的第一位(MSB)与第二位(2nd MSB)的XOR。
- 灰度码的第三位(从左侧开始)等于第二位(第二MSB)和第三位(第三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)。
推荐阅读
- 如何在服务器上将HTML 5 Canvas保存为图像()
- 算法设计(求最多k次交换后的最大排列)
- 博弈论中的极小极大算法第2组(评估功能简介)
- Python示例中的Lambda和filter用法指南
- Java中的已检查与未检查异常
- R编程中的回归及其类型
- 最新YouTube用户使用的14款最佳视频编辑软件推荐合集
- 16种用于编辑右键菜单的最佳Windows 10上下文菜单编辑器合集
- 如何修复Windows 10中的NVIDIA控制面板缺少选项(解决办法介绍)