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
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].
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.