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

در این پست آموزشی از اوپن مایند، الگوریتم محاسبه بزرگترین مقسوم علیه مشترک دو عدد و پیاده سازی آن در زبان پایتون را به شما آموزش می دهیم.

مقدمه

در مدرسه و دانشگاه همه ما اصول ریاضیات را یاد گرفته ایم. در میان تمام مفاهیم پیچیده مثلثات و حساب، یک مفهوم که اغلب در برنامه نویسی استفاده می شود، مفهوم GCD یا Greatest Common Divisor است که در زبان فارسی به آن بزرگترین مقسوم علیه مشترک می گوییم.

مشابه تمام زبان های برنامه نویسی، پایتون نیز از امکان پیاده سازی برنامه ای را به ما می دهد که قادر خواهد بود GCD دو عدد داده شده توسط کاربر را پیدا کند؛ و در این مطلب آموزشی یاد خواهیم گرفت که چگونه این کار را انجام دهیم.

بیایید ببینیم که چگونه GCD را در پایتون پیاده سازی کنیم!

بزرگ‌ترین مقسوم‌علیه مشترک چیست؟

GCD مخفف Greatest Common Divisor است که یک معادله ریاضی برای یافتن بزرگترین عددی است که می تواند هر دو عدد داده شده توسط کاربر را تقسیم کند (تقسیم صحیح). گاهی اوقات این معادله به عنوان “بزرگترین عامل مشترک دو عدد” نیز شناخته می شود. به عنوان مثال، بزرگترین عامل مشترک برای اعداد ۲۰ و ۱۵ ، عدد ۵ است ، زیرا هر دو این اعداد را می توان بر ۵ تقسیم کرد.

این مفهوم را می توان به راحتی به مجموعه ای بیش از ۲ عدد نیز گسترش داد، در آن صورت GCD عددی خواهد بود، که تمام اعداد داده شده توسط کاربر را تقسیم می کند.

مفهوم GCD در تئوری اعداد کاربردهای گسترده ای دارد، خصوصاً در فناوری رمزگذاری رایج که RSA است. همچنین گاهی اوقات برای ساده سازی کسری که در یک معادله وجود دارد استفاده می شود.

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

پیاده سازی محاسبه GCD در پایتون

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

  • پیاده سازی بازگشتی
  • پیاده سازی غیربازگشتی با حلقه
  • پیاده سازی الگوریتم اقلیدس (موسوم به روش نردبانی یا تقسیمات متوالی)
  • تابع gcd از کتابخانه math در پایتون

 

بیایید ببینیم چگونه GCD را با استفاده از Recursion در پایتون پیدا کنیم.

محاسبه GCD در پایتون با الگوریتم بازگشتی

 

وقتی برنامه فوق اجرا شود، خروجی چیزی شبیه به این خواهد بود:

The gcd of 60 and 48 is : 12

 

همچنین می توانیم محاسبه GCD را با استفاده از حلقه ها پیاده سازی کنیم.

محاسبه GCD با حلقه ها

 

وقتی برنامه فوق اجرا شد ، خروجی به این شکل است:

The gcd of 60 and 48 is : 12

 

بیایید روی بعدی را ببینیم.

GCD با استفاده از الگوریتم اقلیدسی

 

خروجی برای کدهای بالا به این صورت است:

The gcd of 60 and 48 is : 12

 

در ادامه، چهارمین روش برای یافتن GCD در پایتون تابع کتابخانه ای ()math.gcd است که در ادامه بررسی می شود.

GCD با استفاده از کتابخانه math در پایتون

قبل از استفاده از تابع ()math.gcd برای محاسبه GCD اعداد در پایتون ، بیایید نگاهی به پارامترهای مختلف آن بیندازیم.

پارامترها

X: عدد صحیح غیر منفی است که gcd آن نیاز به محاسبه دارد.

Y: دومین عدد صحیح غیر منفی است که gcd آن باید محاسبه شود.

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

استثنائات: اگر در یک موقعیت خاص ، هر دو عدد وارد شده توسط کاربر صفر باشد، عملکرد تابع صفر خواهد بود. و اگر ورودی یک کاراکتر باشد، عملکرد تابع خطا را برمی گرداند.

 

اجازه دهید نمونه کدی را مشاهده کنیم.

خروجی برنامه فوق به این صورت خواهد بود:

The gcd of 60 and 48 is : 12

 

در نهایت ما با این روش چهارم به پایان این مطلب محاسبه GCD در پایتون می رسیم. امیدوارم مورد استفاده شما مخاطبین وبسایت اوپن مایند قرار گرفته باشد!

 

 

منبع اصلی ترجمه و آماده سازی این مطلب آموزشی:

How To Implement GCD In Python?

 

نظرتان را برای ما بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *