الگوریتم اقلیدس روشی موسوم به روش نردبانی یا تقسیمات متوالی برای یافتن بزرگترین مقسوم علیه مشترک (ب.م.م) دو عدد است.
بزرگترین مقسوم علیه مشترک دو عدد a و b را بهصورت نشان میدهند. برای محاسبه عدد بزرگتر را بر عدد کوچکتر تقسیم می کنیم؛ اگر باقیمانده صفر بود، پس عدد کوچکتر همان ب.م.م دو عدد است؛ وگرنه عدد کوچکتر را بر باقیمانده تقسیم قبلی تقسیم میکنیم و این فرایند را تا جایی پیش میبریم تا به باقی مانده صفر برسیم.
مثال: برای محاسبهٔ عدد بزرگتر یعنی ۱۸ را بر ۱۲ تقسیم میکنیم و سپس ۱۲ را بر باقی ماندهٔ تقسیم قبل (باقیمانده ۱۸ تقسیم بر ۱۲ مساوی با ۶ است) تقسیم میکنیم. ۱۲ تقسیم بر ۶ باقیمانده صفر دارد؛ بنابراین .
برای این که ثابت کنیم چرا با الگوریتم فوق ب.م.م بهدست میآید، به لم زیر توجه کنید:
لم: اگر آنگاه
اثبات: فرض میکنیم و . پس
شبه کد الگوریتم اقلیدسی:
procedure gcd(a,b:positive integers)
x:=a
y:=b
while y≠۰
r:=x mod y
x:=y
y:=r
return x{gcd(a,b)is x}
الگوریتم اقلیدسی از تقسیمهایی از مرتبهٔ O(log b) برای پیدا کردن بزرگترین مقسوم علیههای مشترک اعداد صحیح a و b استفاده میکند که در آن a≥b است.
وقتی الگوریتم اقلیدسی در پیدا کردن a≥b, gcd(a,b) به کار گرفته میشود دنبالهٔ تساویهای زیر (که در آن a=R0 و b=R1) به دست میآید.
R0=R1q1+R2 0≤R2
.
.
Rn-2=Rn-1qn-1+Rn 0≤Rn>Rn-1
Rn-1=Rnqn
در بهدست آوردن n , Rn=gcd(a,b) تقسیم بهکار رفتهاست. دقت کنید که خارج قسمتهای q1,q2,q3,...qn-1 حداقل ۱ هستند. به علاوه qn≥۲ چون Rn
Rn-1≥2Rn≥2F2=F3
Rn-2≥Rn-1+Rn≥F3+F2=F4
.
.
.
R2≥R3+R4≥Fn-1+Fn-2=Fn
b=R1≥R2+R3≥Fn+Fn-1=Fn+1
بنابراین، در استفاده از الگوریتم اقلیدسی برای پیدا کردن gcd(a,b) با n , a≥b تقسیم بهکار میرود، آنگاه b≥Fn+1.
در ویکیانبار پروندههایی دربارهٔ الگوریتم اقلیدس موجود است. |
This article uses material from the Wikipedia فارسی article الگوریتم اقلیدس, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). محتوا تحت CC BY-SA 4.0 در دسترس است مگر خلافش ذکر شده باشد. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki فارسی (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.