AlgoVerse

تبدیل مبنا

عدد را با تقسیم‌های پیاپی بر مبنا به مبنای دیگر می‌برد؛ باقیمانده‌ها از آخر به اول، رقم‌های جواب‌اند.

در مبنای b، رقم سمت راست عدد n همان n mod b است و بقیه‌ی رقم‌ها عدد n div b را می‌سازند. پس:

ادامه‌ی توضیح ↓
ورودی:
n=156 · base=2خروجی PDF

۱۵۶ در مبنای ۲: هشت تقسیم و جواب 10011100.

  1. DIGITS = "0123456789ABCDEF"
  4. def to_base(n, base):
  5. if n == 0:
  6. return "0"
  7. rows = []
  8. digits = ""
  9. while n > 0:
  10. q = n // base
  11. r = n % base
  12. rows.append((n, q, r, DIGITS[r]))
  13. digits = DIGITS[r] + digits
  14. n = q
  15. return digits

ناوردا: عدد اولیه همیشه برابر n·bᵏ + (مقدار digits) است که k تعداد رقم‌های نوشته‌شده است.

شروع اجرا

n156
digits—

جدول هنوز خالی است.

متغیرهای محلی

n156
base2

نارنجی = در همین گام عوض شد

Call stack

  1. to_base()خط 4
گام ۱ از ۵۴
خط سیاه = digit · خط نارنجی = گام کلیدیdigit: 0/8 · done: 0/1
    توضیح

    ایده

    در مبنای b، رقم سمت راست عدد n همان n mod b است و بقیه‌ی رقم‌ها عدد n div b را می‌سازند. پس:

    1. n را بر b تقسیم کن؛ باقیمانده رقم بعدی (از راست) است.
    2. با خارج‌قسمت ادامه بده تا صفر شود.

    رقم‌ها از آخر به اول به دست می‌آیند؛ برای همین هر رقم تازه جلوی رشته گذاشته می‌شود. برای مبناهای بزرگ‌تر از ۱۰، رقم‌های ۱۰ تا ۱۵ را با A تا F می‌نویسیم.

    هزینه

    هر تقسیم یک رقم می‌دهد: O(log_b n) تقسیم.

    در trace به چه چیزی نگاه کنی

    • جدول همان تقسیم‌های پیاپی روی کاغذ است؛ ستون digit را از پایین به بالا بخوان.