AlgoVerse

الگوریتم تقسیم

خارج‌قسمت q و باقیمانده‌ی r را طوری پیدا می‌کند که a = q·b + r و 0 ≤ r < b؛ با کم کردن یا اضافه کردن پیاپی b.

قضیه‌ی تقسیم: برای هر عدد صحیح a و هر b > 0، دقیقاً یک جفت q و r هست که

ادامه‌ی توضیح ↓
ورودی:
a=170 · b=11خروجی PDF

۱۷۰ تقسیم بر ۱۱: ۱۷۰ = ۱۵·۱۱ + ۵.

  1. def divide(a, b):
  2. # a = q·b + r with 0 ≤ r < b, by repeated subtraction (b > 0).
  3. q = 0
  4. r = a
  5. rows = [(q, r)]
  6. while r >= b:
  7. r = r - b
  8. q = q + 1
  9. rows.append((q, r))
  10. while r < 0:
  11. r = r + b
  12. q = q - 1
  13. rows.append((q, r))
  14. return q, r

ناوردا: در هر لحظه a = q·b + r برقرار است؛ فقط r هنوز ممکن است بیرون بازه‌ی [0, b) باشد.

شروع اجرا

q—
r—

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

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

a170
b11

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

Call stack

  1. divide()خط 1
گام ۱ از ۶۷
خط سیاه = take_away, add_back · خط نارنجی = گام کلیدیtake_away: 0/15 · done: 0/1
    توضیح

    ایده

    قضیه‌ی تقسیم: برای هر عدد صحیح a و هر b > 0، دقیقاً یک جفت q و r هست که

    a = q·b + r   و   0 ≤ r < b

    ساده‌ترین راه پیدا کردنشان: از q = 0 و r = a شروع کن. تا وقتی r ≥ b است یک b از آن کم کن و q را یکی زیاد کن؛ اگر a منفی بود، تا وقتی r < 0 است یک b اضافه کن و q را یکی کم کن.

    نکته درباره‌ی عددهای منفی

    در ریاضیات باقیمانده همیشه نامنفی است، پس −17 mod 5 = 3. بعضی زبان‌های برنامه‌نویسی (مثل C) −2 می‌دهند؛ پایتون مثل ریاضیات 3 می‌دهد.

    هزینه

    این روش |a| / b گام دارد؛ ماشین‌ها تقسیم را مستقیم و خیلی سریع‌تر انجام می‌دهند. ولی هدف اینجا دیدن معنای q و r است.