Moyen 0 résolus 0 % de réussite

Code de Gray

Lister le code de Gray binaire réfléchi sur n bits, où deux valeurs voisines ne diffèrent que d'un bit.

Ce que vous allez apprendre

  • Calculer un code de Gray avec un XOR et un décalage
  • Générer 2^n valeurs
  • Vérifier que deux valeurs voisines diffèrent d'un seul bit

Problème

Dans une suite en code de Gray, chaque valeur ne diffère de la précédente que d'un seul bit. Le code de Gray standard (binaire réfléchi) de i est i XOR (i >> 1) : sur 2 bits, la suite est 0, 1, 3, 2, soit 00, 01, 11, 10 en binaire. On l'utilise dans les codeurs rotatifs pour qu'une lecture faite entre deux positions ne soit jamais complètement fausse.

Implémentez gray_code(n).

Entrée

n : le nombre de bits.

Sortie

Renvoyez dans l'ordre les 2^n valeurs du code de Gray binaire réfléchi, sous forme d'entiers, en commençant par 0. Pour n = 0, renvoyez [0].

Contraintes

0 ≤ n ≤ 16

Exemples

Exemple 1
Entrée :
n = 2

Sortie attendue :
expected = [0, 1, 3, 2]
Entrée :
long long n = 2;

Sortie attendue :
std::vector<long long> expected = {0, 1, 3, 2};
Entrée :
long n = 2;

Sortie attendue :
long[] expected = new long[] {0, 1, 3, 2};

Explication

En binaire, la suite est 00, 01, 11, 10, donc la réponse est [0, 1, 3, 2].

Exemple 2
Entrée :
n = 3

Sortie attendue :
expected = [0, 1, 3, 2, 6, 7, 5, 4]
Entrée :
long long n = 3;

Sortie attendue :
std::vector<long long> expected = {0, 1, 3, 2, 6, 7, 5, 4};
Entrée :
long n = 3;

Sortie attendue :
long[] expected = new long[] {0, 1, 3, 2, 6, 7, 5, 4};

Explication

Chaque valeur vaut i XOR (i >> 1) pour i allant de 0 à 7 : [0, 1, 3, 2, 6, 7, 5, 4].

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Faites varier i de 0 à 2^n − 1.

Indice 2

Chaque valeur du code de Gray s'obtient à partir de i et de i décalé d'un cran vers la droite.

Indice 3

Pour n = 0, la boucle s'exécute une fois et donne [0].

Complexité attendue

temps O(2^n), espace supplémentaire O(2^n)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.