به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
ارسال شده ۱۱ مرداد ۱۴۰۰ در مطالب ریاضی توسط Math.Al (602 امتیاز)
ویرایش شده ۱۱ مرداد ۱۴۰۰ توسط Math.Al
23 بازدید

به نام خدا

الگوریتم اقلیدس: روشی موسوم به روش نردبانی برای یافتن بزرگ‌ترین مقسوم‌علیه مشترک (ب. م. م) دو عدد است. ساده‌ترین نسخۀ الگوریتم اقلیدس، بر این واقعیت استوار است که ب. م. م دو عدد، با ب. م. م عدد کوچک‌تر و تفاضل آن دو عدد، یکسان است.


نسخۀ سادۀ الگوریتم اقلیدس:

در نسخۀ سادۀ الگوریتم اقلیدس، برای به‌دست آوردن ب. م. م دو عدد مثلاً $a$ و $b$ ($a>b$)، ابتدا $b$ را از $a$ کم می‌کنیم و حاصل مثلاً برابر با عددی مثل $ c$ می‌شود: $a-b=c$. سپس حاصل (یعنی $c$) را از $b$ کم می‌کنیم و حاصل برابر با عدد دیگر مثل $d$ می‌شود: $b-c=d$. و بعد $d$ را از $c$ کم می‌کنیم و حاصل برابر با عدد دیگری مثل $e$ می‌شود: $c-d=e$ و این عمل را تا جایی که تفاضل صفر شود ادامه می‌دهیم، حاصل آخرین تفاضل غیرصفر، برابر با ب. م. م $a$ و $b$ است.

برای مثال، یافتن ب. م. م دو عددِ $585$ و $442$ با استفاده از نسخۀ سادۀ الگوریتم اقلیدس به‌این شکل است:

$$585-442=143$$

$$442-143=299$$

$$299-143=156$$

$$156-143=13$$

$$143-13=130$$

$$130-13=117$$

$$117-13=104$$

$$104-13=91$$

$$91-13=78$$

$$78-13=65$$

$$65-13=52$$

$$52-13=39$$

$$39-13=26$$

$$26-13=13$$

$$13-13=0$$

پس ب. م. م برابر با $13$ است.


نسخۀ استاندارد الگوریتم اقلیدس:

در نسخۀ استاندارد الگوریتم اقلیدس، برای به‌دست آوردن ب. م. م دو عدد مثلاً $a$ و $b$ ($a>b$)، ابتدا $a$ را بر $b$ تقسیم می‌کنیم و خارج قسمت و باقی‌ماندۀ آن به‌ترتیب برابر با اعدادی مثل $c$ و $d$ می‌شود. سپس $b$ را بر باقی‌ماندۀ تقسیم قبل (یعنی $d$) تقسیم می‌کنیم و خارج قسمت و باقی‌ماندۀ آن به‌ترتیب برابر با اعدادی مثل $e$ و $f$ می‌شود. سپس $d$ را بر $f$ تقسیم می‌کنیم و خارج قسمت و باقی‌ماندۀ آن به‌ترتیب برابر با اعدادی مثل $g$ و $h$ می‌شود و این عمل را تا جایی که باقی‌مانده صفر شود ادامه می‌دهیم، آخرین باقی‌مانده غیرصفر، برابر با ب. م. م $a$ و $b$ است.

برای مثال، یافتن ب. م. م دو عددِ $585$ و $442$ با استفاده از نسخۀ استاندارد الگوریتم اقلیدس به‌این شکل است:

$$ \frac{585}{442}=1,(باقی‌مانده:143)$$

$$ \frac{442}{143}=3,(باقی‌مانده:13) $$

$$ \frac{143}{13}=11,(باقی‌مانده:0) $$

پس ب. م. م برابر با $13$ است.


حمایت مالی

کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...