Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Mã Gray

Liệt kê mã Gray nhị phân phản xạ n bit, trong đó hai giá trị liền kề khác nhau đúng một bit.

Bạn sẽ học được gì

  • Tính mã Gray bằng XOR và phép dịch
  • Sinh 2^n giá trị
  • Kiểm tra hai giá trị liền kề chỉ khác nhau một bit

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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].

Ví dụ 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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.