Problem
In einer Gray-Code-Folge unterscheidet sich jeder Wert vom vorherigen in genau einem Bit. Der übliche Gray-Code (reflektierter Binärcode) von i ist i XOR (i >> 1). Für 2 Bits lautet die Folge 0, 1, 3, 2, binär also 00, 01, 11, 10. Drehgeber nutzen ihn, damit ein Messwert, der genau zwischen zwei Positionen abgelesen wird, nie völlig falsch ist.
Implementiere gray_code(n).
Eingabe
n: Die Anzahl der Bits.
Ausgabe
Gib die 2^n Werte des reflektierten Gray-Codes der Reihe nach als ganze Zahlen zurück, beginnend mit 0. Für n = 0 gib [0] zurück.
Einschränkungen
0 ≤ n ≤ 16
Beispiele
Eingabe:
n = 2
Erwartete Ausgabe:
expected = [0, 1, 3, 2]
Eingabe:
long long n = 2;
Erwartete Ausgabe:
std::vector<long long> expected = {0, 1, 3, 2};
Eingabe:
long n = 2;
Erwartete Ausgabe:
long[] expected = new long[] {0, 1, 3, 2};
Erläuterung
Binär lautet die Folge 00, 01, 11, 10, also ist die Antwort [0, 1, 3, 2].
Eingabe:
n = 3
Erwartete Ausgabe:
expected = [0, 1, 3, 2, 6, 7, 5, 4]
Eingabe:
long long n = 3;
Erwartete Ausgabe:
std::vector<long long> expected = {0, 1, 3, 2, 6, 7, 5, 4};
Eingabe:
long n = 3;
Erwartete Ausgabe:
long[] expected = new long[] {0, 1, 3, 2, 6, 7, 5, 4};
Erläuterung
Jeder Wert ist i XOR (i >> 1) für i = 0 bis 7: [0, 1, 3, 2, 6, 7, 5, 4].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Lass i von 0 bis 2^n − 1 laufen.
Hinweis 2
Jeder Gray-Code-Wert entsteht aus i und dem um eins nach rechts verschobenen i.
Hinweis 3
Für n = 0 läuft die Schleife genau einmal und liefert [0].
Erwartete Komplexität
Zeit O(2^n), zusätzlicher Speicher O(2^n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.