Mittel 0 gelöst 0% Erfolgsquote

Gray-Code

Gib den n-Bit-Gray-Code (reflektierter Binärcode) aus, bei dem sich benachbarte Werte in genau einem Bit unterscheiden.

Das lernst du

  • Einen Gray-Code mit XOR und Verschiebung berechnen
  • 2^n Werte erzeugen
  • Prüfen, dass sich Nachbarn in genau einem Bit unterscheiden

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

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

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

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.