Problema
In una sequenza in codice Gray ogni valore differisce dal precedente per un solo bit. Il codice Gray standard (binario riflesso) di i è i XOR (i >> 1): con 2 bit la sequenza è 0, 1, 3, 2, cioè 00, 01, 11, 10 in binario. Lo usano gli encoder rotativi, così una lettura fatta a metà tra due posizioni non è mai completamente sbagliata.
Implementa gray_code(n).
Input
n: il numero di bit.
Output
Restituisci in ordine i 2^n valori del codice Gray binario riflesso, come interi, a partire da 0. Per n = 0 restituisci [0].
Vincoli
0 ≤ n ≤ 16
Esempi
Input:
n = 2
Output atteso:
expected = [0, 1, 3, 2]
Input:
long long n = 2;
Output atteso:
std::vector<long long> expected = {0, 1, 3, 2};
Input:
long n = 2;
Output atteso:
long[] expected = new long[] {0, 1, 3, 2};
Spiegazione
In binario la sequenza è 00, 01, 11, 10, quindi la risposta è [0, 1, 3, 2].
Input:
n = 3
Output atteso:
expected = [0, 1, 3, 2, 6, 7, 5, 4]
Input:
long long n = 3;
Output atteso:
std::vector<long long> expected = {0, 1, 3, 2, 6, 7, 5, 4};
Input:
long n = 3;
Output atteso:
long[] expected = new long[] {0, 1, 3, 2, 6, 7, 5, 4};
Spiegazione
Ogni valore è i XOR (i >> 1) per i da 0 a 7: [0, 1, 3, 2, 6, 7, 5, 4].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Fai variare i da 0 a 2^n − 1.
Suggerimento 2
Ogni valore del codice Gray si ottiene da i e da i spostato a destra di un bit.
Suggerimento 3
Per n = 0 il ciclo viene eseguito una volta e dà [0].
Complessità attesa
tempo O(2^n), spazio aggiuntivo O(2^n)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.