โจทย์
ในลำดับรหัสเกรย์ แต่ละค่าจะต่างจากค่าก่อนหน้าเพียงหนึ่งบิตพอดี รหัสเกรย์มาตรฐาน (แบบ reflected binary) ของ i คือ i XOR (i >> 1) เช่น สำหรับ 2 บิต ลำดับคือ 0, 1, 3, 2 ซึ่งในเลขฐานสองคือ 00, 01, 11, 10 อุปกรณ์เข้ารหัสแบบหมุน (rotary encoder) ใช้รหัสนี้เพื่อให้ค่าที่อ่านได้ขณะอยู่ระหว่างสองตำแหน่งไม่ผิดเพี้ยนไปมาก
จงเขียนฟังก์ชัน gray_code(n)
อินพุต
n: จำนวนบิต
เอาต์พุต
คืนค่ารหัสเกรย์แบบ reflected binary ทั้ง 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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน