منبع اصلی نوشتار زیر در این لینک قرار دارد

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

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

مقدمه

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

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

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

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

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

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

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

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

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

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

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

 

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

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

 

# Python code to demonstrate naive 
# method to compute gcd ( recursion ) 
def hcfnaive(a,b): 
    if(b==0): 
        return a 
    else: 
        return hcfnaive(b,a%b) 
a = 60
b= 48
# prints 12 
print ("The gcd of 60 and 48 is : ",end="") 
print (hcfnaive(60,48))

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

The gcd of 60 and 48 is : 12

 

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

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

 

# Python code to demonstrate naive 
# method to compute gcd ( Loops ) 
 
def computeGCD(x, y): 
    if x > y: 
        small = y 
    else: 
        small = x 
    for i in range(1, small+1): 
        if((x % i == 0) and (y % i == 0)): 
            gcd = i     
    return gcd 
a = 60
b= 48
# prints 12 
print ("The gcd of 60 and 48 is : ",end="") 
print (computeGCD(60,48))

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

The gcd of 60 and 48 is : 12

 

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

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

 

# Python code to demonstrate naive 
# method to compute gcd ( Euclidean algo ) 
def computeGCD(x, y): 
   while(y): 
       x, y = y, x % y 
   return x 
a = 60
b= 48 
# prints 12 
print ("The gcd of 60 and 48 is : ",end="") 
print (computeGCD(60,48))

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

The gcd of 60 and 48 is : 12

 

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

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

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

Syntax: math.gcd( x,y)

پارامترها

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

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

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

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

 

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

# Python code to demonstrate gcd()
# method to compute gcd
import math
# prints 12
print ("The gcd of 60 and 48 is : ",end="")
print (math.gcd(60,48))

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

The gcd of 60 and 48 is : 12

 

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

 

 

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

How To Implement GCD In Python?

 

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