المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


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

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

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

بزرگترین مقسوم علیه مشترک میان دو عدد صحیح 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)

پیچیدگی زمانی

  • به ازای دو عدد طبیعی a و b اگر a بزرگتر مساوی b باشد آنگاه a % b حداکثر نصف a خواهد بود.

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


ابزار صفحه