خانه ویکی

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

دو عدد نامنفی a, b داریم و به دنبال بزگرترین مقسوم علیه مشترک (ب.م.م) آهنها هستیم . در واقع ب.م.م بزرگترین عدد طبیعی ای است که هر دو عدد a, b بر آن بخش پذیرند و به صورت (a, b) در ریاضیات نمایش داده می شوند و در انگلیسی به نام GCD (greatest common divisor) شناخته می شوند . Gcd(a, b) = max k : { k N : k | a , k | b } عدد a را بر عدد b بخش پذیر گویند هر گاه عدد صحیحی مانند q چنان یافت شود که a = b * q بخش پذیری a بر b را به صورت b | a و آن را به یکی از صورت های زیر میخوانند . 1- عدد a عدد b را می شمارد 2- عدد b عدد a را عاد می کند 3- عدد b مقسوم علیهی از a است 4- عدد a مضربی از عدد b است و اگر عدد b مقسوم علیهی از عدد a نباشد آن را به صورت b | a نشان می دهند . وقتی که یکی از a, b صفر باشند و دیگری مخالف صفر باشد آن گاه ب.م.م آن ها طبق تعریف عددی است که مخالف صفر است ( max(a,b) ) و زمانی که 2 عدد صفر هستند ب.م.م آنها تعریف نشده است و می تواند هر عدد دلخواه بزگری باشد و معمولا میگوییم این مقدار صفر است (چرا؟) پس میتوان یک قانون ساده گذاشت : اگر یکی از اعداد صفر بود ب.م.م آن عدد دیگر است الگوریتم اقلیدس که در پایین به آن اشاره میکنیم کمک میکند تا بتوان بزرگتری مقسوم علیه مشترک a, b را در O(log(min(a,b))) بدست آورد

پیاده سازی

int gcd(int a,int b){ return (b == 0 ? a : gcd(b,a%b)); }

اثبات درستی

در ابتدا دقت کنید که با هر بار تکرار استدلال دوم از الگوریتم اقلیدسی ، عدد کاهش پیدا میکند پس از اونجایی که عه دو عدد طبیعی هستند این الگوریتم پایان پذیر است . برا اپبات درستی الگوریتم باید نشان دهیم که : gcd(a, b) = gcd (b, a mod b) به ازای تمام a, b هایی که a > 0 , b > 0 است . می خواهیم نشان دهیم که مقدار سمت چپمعادله بر مقدار سمت راست آن بخش پذیر است و برعکس. پس واضح است که مقدار سمت چپ با نقدار سمت راست برابر خواهد بود و با این میتوان الگوریتم اقلیدسی را اثبات کرد . فرض میکنیم d = gcd(a, b) پس d | a , d | b . حال بیایید باقی مانده تقسیم a بر b را این طور نشان دهیم : a mod b = a-b.(floor(a/b)) پس نتیجه مشود که d | (a mod b) و این بدان معنا است که : d | b d | (a mod b) حال از این قضیه استفاده میکنیم که به ازای هر 3 عدد p , q, r اگر p | q و p | r انگاه p | gcd(q,r) پس میتوان نتیجه گرفت که d = gcd (a, b) | gcd(b, a mod b) بنابر این میتوان نشان داد که سمت چپ معادله بر سمت راست آن بخش پذیر است و طرف دیگر آن ( برعکس ) را هم میتوان همین گونه پابت کرد .

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

پیچیدگی زمانی با استفاده از Lami’s theorem تقریب زده می شود که یک رابطه جذاب بین الگوریتم اقلیدسی و دنباله فیبوناتچی را توضیح میدهد . اگر a > b >= 1 و به ازای یک n دلخواه Fn > b باشد آن گاه الگوریتم اقلیدسی حداکثر n-2 بار اجرا می شود . همچنین میتوان نشان داد که بزرگترین کران برای این قضیه بهینه است . وقتی که b = Fn-1 , a = Fn باشد آنگاه برای محاسبه gcd(a, b) الگوریتم اقلیدسی دقیقا n-2 بار تکرار میشود . به بیانی دیگر اعداد متوالی در دنباله فیبوناتچی بدترین ورودی ها از نظر پیچیدگی زمانی هستند (چرا؟) پس فهمیدیم که حتی برای 2 عدد در دنباله فیبوناتچی که خیلی سریع رشد میکنند هم الگوریتم اقلیدس در O(log min(a,b) ) اجرا می شود .

کوچک ترین مضرب مشترک ( ک.م.م )

برای محاسبه ک.م.م ( LCM in English ) میتوان از ب.م.م استفاده کرد : Lcm(a, b) = (a * b) / gcd(a,b) مرتبه زمانی ک.م.م مانند مرتبه زمانی ب.م.م است