問題
グレイコードの列では、各値が直前の値とちょうど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
例
入力:
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] です。
入力:
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用に調整されています。上記の説明と制約に従ってください。