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

سلام

یکی از پرکاربردترین مفاهیم ریاضی، که در بسیاری از برنامه های کامپیوتری هم مورد استفاده دارد، "بزرگ‌ترین مقسوم‌علیه مشترک" هست که با نام اختصاری "ب.م.م" نیز شناخته شده است. به احتمال زیاد در منابع خارجی با عبارت Greatest Common Divisor یا GCD مواجه شده باشید. البته الگوریتم‌های زیادی (با پیچیدگی های مختلف) برای محاسبه ب.م.م ارائه شده است؛ اما یکی از راه هایی که بسیاری از ما در دوران مدرسه از آن استفاده کرده ایم، روش تقسیم متوالی، یا روش نردبانی هست.

امروز با الگوریتم محاسبه بزرگترین مقسوم علیه مشترک دو عدد و همچنین برنامه آن در زبان برنامه نویسی #C در خدمت شما هستم.

به تصویر زیر دقت کنید:

در این شکل روش محاسبه ب.م.م دو عدد 12 و 20، نشان داده شده است. تا زمانیکه به باقیمانده صفر نرسیده باشیم، عمل تقسیم را ادامه می‌دهیم. به این صورت که هر دفعه باید یکسری جابجایی‌ها را انجام دهیم که این جابجایی‌ها در تصویر بالا، با فلش‌ها مشخص شده‌اند.

کاملا واضح هست که باید عدد بزرگتر را بر عدد کوچکتر، تقسیم کنیم. بنابراین باید قبل از هرچیز عدد بزرگتر را تشخیص دهیم.

و اما برنامه محاسبه GCD

1. ویژوال استودیو را باز کنید و یک پروژه WindowsFormApplication ایجاد کنید.
2. سه عدد TextBox به نام‌های txtA ، txtB و txtAns روی فرم قرار دهید.
3. یک عدد Button با متن "ب.م.م" روی فرم قرار دهید و نام آن‌را btnGCD قرار دهید.
4. روی دکمه دابل‌کلیک کنید، تا به بخش کدنویسی برای رویداد "کلیک" دکمه، منتقل شوید.
5. برنامه زیر را با دقت بنویسید. (بعضی از قسمت‌های برنامه، بیرون از رویداد کلیک دکمه نوشته شده اند)

پ.ن: هیچ اجباری در نام و متن اشیائی که روی فرم قرار می‌دهید، وجود ندارد و تاکید بر روی نامگذاری اشیاء، صرفا جهت جلوگیری از اشتباه در فهم کدها است.

public void swap(ref int a, ref int b)
{
    int temp = a;
    a = b;
    b = temp;
}
public int gcd(int a, int b)
{
    if (a < b)
    {
        swap(ref a, ref b);
    }
    int rem = 0;
    while (a % b > 0)
    {
        rem= a % b;
        a = b;
        b = rem;
    }
    return b;
}
private void btnGCD_Click(object sender, EventArgs e)
{
    int a = Int32.Parse(txtA.Text);
    int b = Int32.Parse(txtB.Text);
    txtAns.Text= gcd(a, b).ToString();
}

در برنامه بالا، متد swap کار جابجا کردن دو عدد را انجام می‌دهد. همانطور که قبلا اشاره شد، عدد بزرگتر را باید بر عدد کوچکتر تقسیم کنیم. ممکن است کاربر، اول عدد کوچکتر را وارد کند. در چنین مواقعی می بایست عددهای وارد شده را جابجا کنیم تا در عمل تقسیم مشکلی بوجود نیاید.

متد gcd هم کار محاسبه بزرگترین مقسوم‌علیه مشترک دو عدد را انجام می‌دهد. این متد با استفاده از تقسیم متوالی کار می‌کند.

در متد gcd یک شرط داریم که درصورت کوچکتر بود اولین عدد (a) در مقایسه با دومین عدد (b)، آنها را با استفاده از متد swap جابجا می‌کند. برای اطلاعات بیشتر در مورد کلمه کلیدی ref به اینجا مراجعه بفرمایید.

متغر rem برای نگهداری مقدار باقی‌مانده تقسیم‌ها مورد استفاده قرار می‌گیرد.

در متد gcd، یک حلقه while داریم. به این دلیل که نمی‌دانیم عمل تقسیم را دقیقا باید چندبار انجام دهیم، از حلقه while استفاده کرده‌ایم. اما می‌دانستیم که، تا زمانیکه باقیمانده تقسیم اولین عدد (a) بر دومین عدد (b) از صفر بزرگتر باشد، باید عمل تقسیم کردن را ادامه دهیم؛ بنابراین "شرط ادامه" حلقه را بصورت a%b>0 نوشتیم.

سه عبارت داخل حلقه، جابجایی‌های نشان داده شده در شکل را انجام می‌دهند.

یک برگ کاغذ و یک خودکار بردارید و تمام کارهایی که این برنامه انجام می‌دهد را موبه‌مو انجام دهید و تغییراتی که در متغیرها بوجود می‌آید را، در جدولی ثبت کنید. ستون‌های این جدول را هم‌نام مغیرهای موجود در برنامه قرار دهید. به این کار اصطلاحا trace (ردیابی)کردن برنامه می‌گوییم.