Dado un número n, genere patrones de bits de 0 a 2 ^ n-1 de modo que los patrones sucesivos difieran en un bit.
Ejemplos:
Entrada: n=2
Salida: 00 01 11 10
Explicación:
Cada elemento adyacente del código gris difiere solo en un bit. Así que los códigos grises de n bits son: 00 01 11 10Entrada: n=3
Salida: 000 001 011 010 110 111 101 100
Explicación:
Cada elemento adyacente del código gris difiere solo en un bit. Así que los códigos grises de n bits son: 000 001 011 010 110 111 101 100
Ya se ha discutido otro enfoque de generar códigos grises de n bits .
Enfoque:
La idea es obtener el código gris de un número binario usando XOR y la operación de desplazamiento a la derecha.
- El primer bit (MSB) del código gris es el mismo que el primer bit (MSB) de los números binarios.
- El segundo bit (desde el lado izquierdo) del código gris es igual a XOR del primer bit (MSB) y el segundo bit (segundo MSB) del número binario.
- El tercer bit (desde el lado izquierdo) del código gris es igual a XOR del segundo bit (2nd MSB) y un tercer bit (3rd MSB) y así sucesivamente.
De esta forma, se puede calcular el código gris para el número binario correspondiente. Entonces, se puede observar que el i-ésimo elemento puede estar formado por XOR bit a bit de i y floor(i/2) que es igual al XOR bit a bit de i y (i >> 1), es decir, i desplazado a la derecha por 1. Al realizar esto, el MSB del número binario se mantiene intacto y todos los demás bits se ejecutan XOR bit a bit con su bit superior adyacente.
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.
Javascript
<script>
// JavaScript program to generate n-bit
// gray codes
// Function to convert decimal to binary
function decimalToBinaryNumber(x, n)
{
var binaryNumber = Array(x);
var i = 0;
while (x > 0) {
binaryNumber[i] = x % 2;
x = parseInt(x / 2);
i++;
}
// leftmost digits are filled with 0
for (var j = 0; j < n - i; j++)
document.write('0');
for (var j = i - 1; j >= 0; j--)
document.write( binaryNumber[j]);
}
// Function to generate gray code
function generateGrayarr(n)
{
var N = 1 << n;
for (var i = 0; i < N; i++) {
// generate gray code of corresponding
// binary number of integer i.
var x = i ^ (i >> 1);
// printing gray code
decimalToBinaryNumber(x, n);
document.write("<br>");
}
}
// Drivers code
var n = 3;
generateGrayarr(n);
</script>
000 001 011 010 110 111 101 100
Análisis de Complejidad:
- Complejidad temporal: O(2 n ).
Solo se necesita un recorrido de 0 a (2 n ). - Espacio Auxiliar: O(log x).
Se requiere un espacio de (log x) para la representación binaria de (x)
Publicación traducida automáticamente
Artículo escrito por Ajitesh Mandal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA