الگوریتم اقلیدس: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Moniri1024 (بحث | مشارکت‌ها) بدون خلاصۀ ویرایش |
به نسخهٔ 13726007 ویرایش 188.245.124.156 واگردانده شد: حذف مطالب اصلی مقاله. (توینکل) |
||
خط ۱:
[[پرونده:Euclidean_algorithm_252_105_animation_flipped.gif|چپ|انگشتی|نمایش مراحل الگوریتم اقلیدس برای به دست آوردن ب.م.م. اعداد ۲۵۲ و ۱۰۵]]
'''الگوریتم اقلیدس''' یک [[الگوریتم]] برای محاسبهٔ [[بزرگترین مقسوم علیه مشترک]] (ب.م.م.) است که اولین بار توسط [[اقلیدس]] در کتاب [[اصول اقلیدس (کتاب)|اصول اقلیدس]] شرح داده شده است. در این روش، برای محاسبهٔ ب.م.م. دو عدد x و y که به صورت <math>gcd(x,y)</math> نمایش داده می‌شود، چنین عمل می‌شود (فرض بر این است که x از y بزرگتر است، اگر چه در حالت برعکس نیز، صرفاً با تغییر نام x و y این روش قابل استفاده خواهد بود):
# از x به اندازهٔ y کم کن، و مقدار جدید را به جای x جایگذاری کن
# قدم بالا را آن قدر تکرار کن تا x از y کوچک‌تر شود
# جای x و y را عوض کن و قدم‌ها بالا را تکرار کن، تا وقتی که مقدار x صفر شود؛ در این حالت، مقدار y برابر با ب.م.م. دو عدد x و y خواهد بود.
اگر ب.م.م دو عدد برابر با یک شود ان دو عدد نسبت به هم اول هستند که با آن متباین گفته می شود.
راه های دیگری برای بدست اوردن (ب م م) است که شرح می دهم .
1- اگر عدد کوچک تر بر عدد بزرگ تر تقسیم شود و باقی مانده صفر صفر شود عدد کوچک تر (ب م م) است .
2- اگر هر دو عدد اعداد اول بودند (ب م م) آنها برابر با یک است .
3- اگر هر دو عدد متوالی بودند باز هم برابر با یک است .
به عنوان نمونه، اگر x برابر ۷۰ و y برابر ۲۵ باشد، مراحل کار چنین خواهد بود:
ب.م.م.(۲۵و۷۰) ← ب.م.م.(۲۵و۴۵) ← ب.م.م.(۲۵و۲۰) ← ب.م.م.(۲۰و۲۵){{سخ}}
← ب.م.م.(۲۰و۵) ← ب.م.م.(۵و۲۰) ← ب.م.م.(۵و۱۵) ← ب.م.م.(۵و۱۰){{سخ}}
← ب.م.م.(۵و۵) ← ب.م.م.(۵و۰) ← ب.م.م. = ۵
'''مثالی از این الگوریتم به زبان سی'''
<source lang="c">
int gcd(int x, int y){
if (y == 0) {
return x;
} else {
return gcd(y, x % y);
}
}
</source>
== منابع ==
* [http://mathworld.wolfram.com/EuclideanAlgorithm.html الگوریتم اقلیدس در Wolfram MathWorld]
{{رایانه-خرد}}
{{ویکی‌انبار-رده|Euclidean algorithm}}
[[رده:
[[رده:اقلیدس]]
[[رده:
| |||