جلسهی 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)مثالهای این جلسه
چالشها
- Shared by 16 and 24 (آسان)
- (20, 15) (آسان)
- A 24 by 18 Floor (متوسط)
- By Factorising (متوسط)
- Fruit Bags (سخت)
- Nine and Sixteen (سخت)
بیشتر بخوان
← جلسهی 18: شمارندهی اول جلسهی 20: کوچکترین مضرب مشترک →