بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 19: بزرگ‌ترین شمارنده‌ی مشترک The Greatest Common Divisor

شمارنده‌هایی که دو عدد با هم دارند، شمارنده‌های مشترک‌اند و بزرگ‌ترینشان ب.م.م است؛ ب.م.م ۱۸ و ۱۲ را (۱۸ و ۱۲) = ۶ می‌نویسیم. ب.م.م را از فهرست شمارنده‌ها یا از شمارنده‌های اول مشترک پیدا می‌کنیم.

در این جلسه یاد می‌گیری

درس

بزرگ‌ترین کاشی مربعی. کف اتاقی ۱۸ در ۱۲ است و می‌خواهیم آن را با کاشی‌های مربعی یک‌اندازه بپوشانیم، بدون بریدن کاشی. ضلع کاشی را عوض کن: بزرگ‌ترین کاشی که درست جا می‌شود چند است؟

شمارنده‌های مشترک. شمارنده‌های ۱۲: ۱، ۲، ۳، ۴، ۶، ۱۲. شمارنده‌های ۱۸: ۱، ۲، ۳، ۶، ۹، ۱۸. مشترک‌ها: ۱، ۲، ۳ و ۶. بزرگ‌ترینشان ۶ است: (۱۸ و ۱۲) = ۶. این همان ضلع بزرگ‌ترین کاشی است.

از راه تجزیه. ⁦۱۲ = ۲ × ۲ × ۳⁩ و ⁦۱۸ = ۲ × ۳ × ۳⁩. شمارنده‌های اولی را که در هر دو هست بردار: یک ۲ و یک ۳. ضربشان، ⁦۲ × ۳ = ۶⁩، ب.م.م است.

مسئله. ۲۴ مداد و ۳۶ پاک‌کن داریم و می‌خواهیم بسته‌های یکسان بسازیم که چیزی نماند. حداکثر چند بسته؟ تعداد بسته‌ها باید هم ۲۴ را بشمارد هم ۳۶ را: (۳۶ و ۲۴) = ۱۲ بسته، هر کدام ۲ مداد و ۳ پاک‌کن.
اشتباه رایج: ب.م.م را با عدد کوچک‌تر یکی گرفتن. (۱۲ و ۸) = ۴ است، نه ۸. وقتی ب.م.م دو عدد ۱ است، می‌گوییم آن دو عدد نسبت به هم اول‌اند، مثل ۸ و ۹.

با پایتون (اختیاری): math.gcd ب.م.م را می‌دهد. پایین‌تر راه قدیمی اقلیدس را هم می‌بینی: تا باقی‌مانده صفر نشده، عدد بزرگ را با باقی‌مانده عوض کن.

import math
print(math.gcd(18, 12))

a = 18
b = 12
while b != 0:
    a, b = b, a % b
print(a)

مثال‌های این جلسه

چالش‌ها

  1. Shared by 16 and 24 (آسان)
  2. (20, 15) (آسان)
  3. A 24 by 18 Floor (متوسط)
  4. By Factorising (متوسط)
  5. Fruit Bags (سخت)
  6. Nine and Sixteen (سخت)

بیشتر بخوان

← جلسه‌ی 18: شمارنده‌ی اول جلسه‌ی 20: کوچک‌ترین مضرب مشترک →