آموزش:الگوریتم‌های تکمـیلی:محاسبه‌ی بزرگ‌ترین مقسوم‌علیـه ...

فهرست مندرجات

در ریـاضیـات بزرگ‌ترین مقسوم علیـه مشترک یـا ب.م.مِ دو عدد صحیح، تجزیه یک عدد به عوامل اول به روش فلوچارت بـه بزرگ‌ترین عدد طبیعی گفته مـی‌شود کـه مقسوم‌الیـه آن دو است.

بزرگترین مقسوم علیـه مشترک مـیان دو عدد صحیح a و b بصورت (a, b) یـا (gcd (a, b نوشته مـی‌شود.

مثال: تجزیه یک عدد به عوامل اول به روش فلوچارت gcd (16, 24) = 8 و gcd (8, 9) = 1

برای محاسبه ب.م.م مـی‌توان هر دو عدد را بـه عوامل اول تجزیـه کرد. تجزیه یک عدد به عوامل اول به روش فلوچارت ب.م.م برابر حاصل ضرب عوامل مشترک با توان کوچکتر مـی‌شود.

برای مثال: $18=2.3^2$ و $84=2^2.3.7$ بعد $(84, 18)=2.3$gcd

در این روش لازم هست که بـه دو خاصیت مـهم ب.م.م توجه کنیم.

• ب.م.م دو عدد a و ۰ برابر |a| است. تجزیه یک عدد به عوامل اول به روش فلوچارت |gcd(a, ۰)=|a.

• اگر m یک عدد صحیح باشد آنگاه داریم: (gcd(a + m.b, b) = gcd(a, b.

با توجه بـه این خاصیت‌ها هر بار باقیمانده‌ی تقسیم عدد بزرگ تر بر عدد کوچکتر را محاسبه مـی‌کنیم. اگر برابر صفر بود ب.م.م عدد کوچکتر هست در غیر این صورت ب.م.م برابر ب.م.م عدد کوچکتر و باقیمانده‌ی تقسیم است.

مثال: یـافتن (۸۴٬۱۸)gcd

ابتدا ۸۴ را بـه ۱۸ تقسیم مـی کنیم؛ خارج قسمت تقسیم ۴ و باقی‌مانده ۱۲ بدست مـی‌آید. سپس ۱۸ را بر ۱۲ تقسیم مـی کنیم؛ خارج قسمت ۱ و باقی‌مانده ۶ بدست مـی‌آید؛ مجدداً ۱۲ را بر ۶ تقسیم مـی‌کنیم؛ خارج قسمت ۲ و باقی‌مانده ۰ مـی‌شود. بعد عدد ۶ ب.م.م دو عدد ۸۴ و ۱۸ است.

gcd.py def gcd(a, b): if b == 0: return a return gcd(b, a % b)

بنابراین هر بار کـه یک عدد را با باقیمانده تقسیم آن بر عدد کوچکتر جایگزین مـی‌کنیم این عدد حداکثر نصف مقدار قبلی اش را مـی‌گیرد بعد این الگوریتم دارای مرتبه زمانی $O(\log a + \log b)$ است.