中級 0件解決済み 正答率0%

グレイコード

隣り合う値がちょうど1ビットだけ異なる、n ビットの反射二進グレイコードを列挙します。

このチャレンジで学べること

  • XOR とシフトでグレイコードを計算できる
  • 2^n 個の値を生成できる
  • 隣り合う値が1ビットだけ異なることを確かめられる

問題

原文(英語)を表示

グレイコードの列では、各値が直前の値とちょうど1ビットだけ異なります。標準的な(反射二進)グレイコードでは、i に対応する値は i XOR (i >> 1) です。2 ビットの場合の列は 0, 1, 3, 2 で、2 進数で書くと 00, 01, 11, 10 です。ロータリーエンコーダーでは、2つの位置の中間で読み取っても大きく外れた値にならないよう、この符号が使われています。

gray_code(n) を実装してください。

入力

n:ビット数。

出力

反射二進グレイコードの 2^n 個の値を、0 から始めて順に、整数のリストとして返してください。n = 0 のときは [0] を返します。

制約

0 ≤ n ≤ 16

例

例 1
入力:
n = 2

期待される出力:
expected = [0, 1, 3, 2]
入力:
long long n = 2;

期待される出力:
std::vector<long long> expected = {0, 1, 3, 2};
入力:
long n = 2;

期待される出力:
long[] expected = new long[] {0, 1, 3, 2};

解説

2 進数で書くと 00, 01, 11, 10 となるので、答えは [0, 1, 3, 2] です。

例 2
入力:
n = 3

期待される出力:
expected = [0, 1, 3, 2, 6, 7, 5, 4]
入力:
long long n = 3;

期待される出力:
std::vector<long long> expected = {0, 1, 3, 2, 6, 7, 5, 4};
入力:
long n = 3;

期待される出力:
long[] expected = new long[] {0, 1, 3, 2, 6, 7, 5, 4};

解説

i = 0 から 7 について、それぞれ i XOR (i >> 1) を計算すると [0, 1, 3, 2, 6, 7, 5, 4] になります。

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

i を 0 から 2^n − 1 までループします。

ヒント 2

各グレイコードの値は、i と、i を1つ右にシフトした値から得られます。

ヒント 3

n = 0 のときはループが1回だけ回り、[0] になります。

目安の計算量

時間 O(2^n)、追加メモリ O(2^n)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。