کد گری
همه‌ی رشته‌های n بیتی را طوری مرتب می‌کند که هر دو رشته‌ی پشت سر هم فقط در یک بیت فرق داشته باشند؛ با بازتاب فهرست قبلی.
در شمارش دودویی معمولی گاهی چند بیت هم‌زمان عوض می‌شوند (0111 → 1000). در کد گری هر دو عدد پشت سر هم فقط در یک بیت فرق دارند. این در حسگرهای چرخشی، جدول کارنو و مسئله‌ی برج هانوی کاربرد دارد.
- زمان:
O(n · 2ⁿ) - حافظه:
O(n · 2ⁿ) - گریمالدی، فصل ۱۱
- جانسون‌باو، فصل ۶
کد گری ۳ بیتی: 000، 001، 011، 010، 110، 111، 101، 100.
def gray_code(n):codes = [""]for size in range(1, n + 1):reflected = codes[::-1]codes = ["0" + c for c in codes] + ["1" + c for c in reflected]rows = []for i in range(len(codes)):# The same code from the formula i XOR (i >> 1), written in n bits.formula = format(i ^ (i >> 1), "b").zfill(n) if n > 0 else ""rows.append((i, codes[i], formula))return codes
شروع اجرا
جدول هنوز خالی است.
متغیرهای محلی
نارنجی = در همین گام عوض شد
Call stack
- gray_code()خط 1
توضیح
ایده
در شمارش دودویی معمولی گاهی چند بیت هم‌زمان عوض می‌شوند (0111 → 1000). در کد گری هر دو عدد پشت سر هم فقط در یک بیت فرق دارند. این در حسگرهای چرخشی، جدول کارنو و مسئله‌ی برج هانوی کاربرد دارد.
ساختن با بازتاب
- فهرست کدهای
kبیتی را بنویس. - یک بار با
0در ابتدای هر کد، و بعد برعکس فهرست با1در ابتدا.
وسط فهرست تازه دو کدِ یکسان (با بیت اول متفاوت) کنار هم‌اند، پس ویژگی «یک بیت تفاوت» حفظ می‌شود.
فرمول مستقیم
کد شماره‌ی i برابر i XOR (i >> 1) است؛ ستون آخر جدول همین را نشان می‌دهد تا با روش بازتاب مقایسه کنی.