В последовательности кода Грея каждое значение отличается от предыдущего ровно одним битом. Стандартный (отражённый двоичный) код Грея числа i равен i XOR (i >> 1). Для 2 битов последовательность выглядит так: 0, 1, 3, 2, или 00, 01, 11, 10 в двоичной записи. Его применяют в датчиках угла поворота (энкодерах), чтобы показание, снятое между двумя положениями, никогда не оказывалось сильно неверным.
Реализуйте 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};
Пояснение
В двоичной записи последовательность имеет вид 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 XOR (i >> 1) для i от 0 до 7: [0, 1, 3, 2, 6, 7, 5, 4].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Переберите i от 0 до 2^n − 1.
Подсказка 2
Каждое значение кода Грея получается из i и i, сдвинутого вправо на один.
Подсказка 3
При n = 0 цикл выполняется один раз и даёт [0].
Ожидаемая сложность
время O(2^n), доп. память O(2^n)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.