Đề bài
Trong dãy mã Gray, mỗi giá trị khác giá trị đứng trước nó đúng một bit. Mã Gray chuẩn (nhị phân phản xạ) của i là i XOR (i >> 1): với 2 bit, dãy là 0, 1, 3, 2, tức là 00, 01, 11, 10 ở dạng nhị phân. Bộ mã hóa vòng quay (rotary encoder) dùng mã này để khi đọc ở giữa hai vị trí, kết quả không bao giờ sai lệch quá nhiều.
Hãy viết gray_code(n).
Đầu vào
n: Số bit.
Đầu ra
Trả về 2^n giá trị của mã Gray nhị phân phản xạ theo thứ tự, dưới dạng số nguyên, bắt đầu từ 0. Với n = 0 trả về [0].
Ràng buộc
0 ≤ n ≤ 16
Ví dụ
Đầu vào:
n = 2
Kết quả mong đợi:
expected = [0, 1, 3, 2]
Đầu vào:
long long n = 2;
Kết quả mong đợi:
std::vector<long long> expected = {0, 1, 3, 2};
Đầu vào:
long n = 2;
Kết quả mong đợi:
long[] expected = new long[] {0, 1, 3, 2};
Giải thích
Ở dạng nhị phân, dãy là 00, 01, 11, 10, nên đáp án là [0, 1, 3, 2].
Đầu vào:
n = 3
Kết quả mong đợi:
expected = [0, 1, 3, 2, 6, 7, 5, 4]
Đầu vào:
long long n = 3;
Kết quả mong đợi:
std::vector<long long> expected = {0, 1, 3, 2, 6, 7, 5, 4};
Đầu vào:
long n = 3;
Kết quả mong đợi:
long[] expected = new long[] {0, 1, 3, 2, 6, 7, 5, 4};
Giải thích
Mỗi giá trị là i XOR (i >> 1) với i từ 0 đến 7: [0, 1, 3, 2, 6, 7, 5, 4].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Cho i chạy từ 0 đến 2^n − 1.
Gợi ý 2
Mỗi giá trị mã Gray được tính từ i và i dịch phải một bit.
Gợi ý 3
Với n = 0, vòng lặp chạy một lần và cho [0].
Độ phức tạp mong đợi
thời gian O(2^n), bộ nhớ phụ O(2^n)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.