الگوریتم اقلیدسی چگونه کار می کند – با مثال های کد در Go

الگوریتم اقلیدسی روشی شناخته شده و کارآمد برای یافتن بزرگترین مقسوم علیه مشترک (GCD) دو عدد صحیح است. GCD بزرگترین عددی است که می تواند هر دو عدد صحیح را بدون باقی ماندن تقسیم کند.

نام این الگوریتم از نام ریاضیدان یونان باستان اقلیدس گرفته شده است که در حدود ۳۰۰ سال قبل از میلاد مسیح آن را در کتاب "Elements" خود ارائه کرد.

شما می توانید از این الگوریتم برای حل معادلات دیوفانتین ، برای مقابله با کوتاه ترین مسئله بردار که اساس رمزنگاری مبتنی بر شبکه است و همچنین برای تشخیص الگوهای رایج پیکسل ها در تصاویر استفاده کنید. این، در میان چیزهای دیگر، برای بهینه سازی فرآیندهای رندر و تشخیص اشیاء مختلف در تصاویر اعمال می شود.

الگوریتم اقلیدسی چگونه کار می کند؟

در اینجا توضیح گام به گام نحوه عملکرد الگوریتم اقلیدسی آورده شده است:

با دو عدد صحیح مثبت a و b شروع کنید که a >= b. اگر a < b، به سادگی مقادیر آنها را عوض کنید. توجه داشته باشید که این برای یک نمایش ریاضی راحت است، زیرا پیاده سازی برای <b نیز کار می کند.

a را بر b تقسیم کنید و باقیمانده r را پیدا کنید (از عملیات مدول که به صورت % b نشان داده شده است استفاده کنید). اگر r 0 باشد، GCD b است و الگوریتم خاتمه می یابد.

اگر r 0 نیست، a را روی b و b را روی r قرار دهید. سپس، مرحله ۲ را تکرار کنید.

الگوریتم تا زمانی که باقیمانده ۰ شود به تکرار ادامه می‌دهد. در آن نقطه، آخرین باقیمانده غیر صفر GCD دو عدد اصلی است.

الگوریتم اقلیدسی کار می کند زیرا GCD دو عدد بدون تغییر باقی می ماند هنگامی که عدد بزرگتر با باقیمانده آن در هنگام تقسیم بر عدد کوچکتر جایگزین می شود.

نمونه ای از الگوریتم اقلیدسی

در اینجا یک مثال برای نشان دادن الگوریتم آورده شده است:

بیایید GCD 30 و ۹ را پیدا کنیم:

a = 30، b = 9

باقیمانده را محاسبه کنید: r = a % b = 30 % 9 = 3 (از آنجایی که ۳ ۰ نیست، به مرحله ۳ ادامه دهید)

مقادیر را به روز کنید: a = 9، b = 3

باقیمانده جدید را محاسبه کنید: r = a % b = 9 % 3 = 0 (r اکنون ۰ است)

GCD 30 و ۹ ۳ است.

چرا الگوریتم اقلیدسی کار می کند؟

بزرگترین مقسوم علیه مشترک دو عدد صحیح بزرگترین عدد صحیح مثبت است که هر دو را بدون باقی ماندن تقسیم می کند. پس الگوریتم بر اساس ویژگی کلیدی زیر است:

اگر a و b دو عدد صحیح باشند، آنگاه GCD a و b همان GCD b و a % b است که % نشان دهنده عملگر مدول است (باقیمانده پس از تقسیم).

از نظر ریاضی، ویژگی کلیدی الگوریتم را می توان با استفاده از الگوریتم تقسیم توجیه کرد:

بگذارید a و b دو عدد صحیح مثبت باشند، به طوری که a >= b . می توانیم الگوریتم تقسیم را به صورت زیر بنویسیم:

a = bq + r که q ضریب و r باقیمانده است.

حال، اجازه دهید d یک مقسوم علیه مشترک a و b باشد. سپس، a = d * m1 و b = d * m2 برای برخی از اعداد صحیح m1 و m2 . می توانیم الگوریتم تقسیم را به صورت زیر بازنویسی کنیم:

d * m1 = (d * m2) * q + r .

با تنظیم مجدد معادله، به دست می آوریم:

r = d * (m1 - m2 * q) .

از آنجایی که d ضریب a و b است و r می توان مضرب d نیز نوشت، می توانیم نتیجه بگیریم که d نیز مقسوم علیه r است. این بدان معنی است که GCD a و b نیز مقسوم علیه r است. پس ، می توانیم b با r جایگزین کنیم و با استفاده از این الگوریتم به یافتن GCD ادامه دهیم تا زمانی که b به ۰ تبدیل شود.

الگوریتم اقلیدسی به دلیل کارایی و سادگی بسیار مفید است و پیاده سازی آن را در الگوریتم های کامپیوتری و زبان های برنامه نویسی آسان می کند.

بیشتر بخوانید

افکار ادوبی در مورد اخلاقیات تصاویر تولید شده توسط هوش مصنوعی (و پرداخت هزینه به مشارکت کنندگان آن برای آنها)

بیایید چند روش مختلف برای پیاده سازی آن در Go ببینیم:

پیاده سازی بازگشتی الگوریتم اقلیدسی در Go

این پیاده سازی الگوریتم اقلیدسی در Golang یک نسخه بازگشتی است که GCD دو عدد صحیح را پیدا می کند. بیایید مرحله به مرحله آن را مرور کنیم:

تابع به صورت GCD(a, b int) int تعریف می شود. دو عدد ورودی a و b را می گیرد و یک خروجی عدد صحیح را برمی گرداند.

حالت پایه بازگشت با if b == 0 تحلیل می شود. اگر b 0 باشد، تابع مقدار a را به عنوان GCD برمی‌گرداند.

اگر b 0 نباشد، یک متغیر موقت tmp ایجاد می شود و مقدار a به آن اختصاص می یابد. این متغیر موقت برای ذخیره مقدار a قبل از به روز رسانی مقدار آن در مرحله بعد استفاده می شود.

مقادیر a و b به صورت زیر به روز می شوند:

a به مقدار فعلی b اختصاص می یابد.

وقتی tmp (مقدار قبلی a ) بر مقدار جدید a (که قبل از به روز رسانی b بود) به b مقدار باقیمانده اختصاص می یابد.

تابع خود را به صورت بازگشتی با مقادیر به روز شده a و b به عنوان ورودی فراخوانی می کند، return GCD(a, b) .

الگوریتم به فراخوانی بازگشتی خود ادامه می‌دهد تا زمانی که به حالت پایه برسد، یعنی b تبدیل به ۰ شود. در این مرحله، تابع GCD را برمی‌گرداند که مقدار a است.

 // Recursive approach: func GCD(a, b int) int { if b == 0 { return a } tmp := a a = b b = tmp % a return GCD(a, b) }

برای مثال، فرض کنید می‌خواهیم GCD 56 و ۴۸ را پیدا کنیم:

تماس اول: GCD (56, 48)

از آنجایی که b (48) 0 نیست، a و b را به روز کنید:

a می شود ۴۸

b می شود ۵۶ % ۴۸ = ۸

تابع خود را با مقادیر جدید فراخوانی می کند: GCD(48, 8)

تماس دوم: GCD (48, 8)

از آنجایی که b (8) 0 نیست، a و b را به روز کنید:

a می شود ۸

b می شود ۴۸ % ۸ = ۰

تابع خود را با مقادیر جدید فراخوانی می کند: GCD(8, 0)

تماس سوم: GCD(8, 0)

حال، b (0) 0 است، پس تابع a (8) را به عنوان GCD برمی گرداند.

اجرای تکراری الگوریتم اقلیدسی در Go

این پیاده سازی الگوریتم اقلیدسی در Golang یک نسخه تکراری با استفاده از یک حلقه برای یافتن GCD دو عدد صحیح است. بیایید گام به گام کد را مرور کنیم:

تابع به صورت GCD(a, b int) int تعریف می شود. دو عدد ورودی a و b را می گیرد و یک خروجی عدد صحیح را برمی گرداند.

یک حلقه برای تکرار استفاده می شود تا زمانی که b برابر با ۰ نباشد. شرط حلقه b != 0 است. توجه داشته باشید که این for ساخت حلقه در Go اساساً یک حلقه while در بسیاری از زبان‌های دیگر است.

در داخل حلقه، مقادیر a و b به طور همزمان با استفاده از یک انتساب چندگانه به روز می شوند: a, b = b, a%b . این خط کارهای زیر را انجام می دهد:

a به مقدار فعلی b اختصاص می یابد.

وقتی a بر b تقسیم شود، مقدار باقیمانده به b اختصاص می یابد.

هنگامی که حلقه خارج می شود (یعنی b تبدیل به ۰ می شود)، مقدار a به عنوان GCD برگردانده می شود.

الگوریتم تا زمانی تکرار می شود که باقیمانده ( b ) 0 شود، در این نقطه GCD آخرین باقیمانده غیر صفر است که مقدار a است.

 func GCD(a, b int) int { for b != 0 { a, b = b, a%b } return a }

به عنوان مثال، فرض کنید قصد داریم GCD 100 و ۶۴ را پیدا کنیم:

a را ۱۰۰ و b را ۶۴ مقداردهی کنید. شرایط حلقه را تحلیل کنید: b (64) 0 نیست.