مثال 31 پایتون – برنامه ای به پایتون بنویسید که بزرگ‌ترین مقسوم‌علیه مشترک یا GCD دو عدد صحیح مثبت را محاسبه کند.

دیدگاه‌ خود را بنویسید / آموزش برنامه نویسی پایتون / از Meghdad Alibakhshi

کد برنامه

def calculate_gcd(x, y):  
    result = 1  
    if x % y == 0:
        return y
    for k in range(int(y / 2), 0, -1):
        if x % k == 0 and y % k == 0:
            result = k
            break
    return result
print("GCD of 15 &amp; 18 =", calculate_gcd(15, 18))
print("GCD of 2 &amp; 5 =", calculate_gcd(2, 5))
print("GCD of 254 &amp; 365 =", calculate_gcd(254, 365))

def calculate_gcd(x, y):

result = 1

if x % y == 0:

return y

for k in range(int(y / 2), 0, -1):

if x % k == 0 and y % k == 0:

result = k

break

return result

print("GCD of 15 & 18 =", calculate_gcd(15, 18))

print("GCD of 2 & 5 =", calculate_gcd(2, 5))

print("GCD of 254 & 365 =", calculate_gcd(254, 365))

توضیح برنامه

این کد یک تابع به نام calculate_gcd ایجاد می‌کند که جی‌سی‌دی (GCD) یا بزرگترین مقسوم علیه عدد مشترک بین دو عدد را محاسبه می‌کند.

تابع calculate_gcd دو آرگومان می‌پذیرد، x و y، که عددهایی هستند که می‌خواهیم جی‌سی‌دی آنها را محاسبه کنیم.

اگر باقی‌ماندهٔ تقسیم x به y صفر باشد (یعنی x بر y بخش‌پذیر باشد)، تابع به طور مستقیم مقدار y را به عنوان جواب برمی‌گرداند چرا که جواب نهایی در این حالت جی‌سی‌دی برابر با y است.
در غیر این صورت، تابع یک حلقه for از int(y / 2) تا 1 اجرا می‌کند. این حلقه می‌خواهد بزرگترین مقسوم علیه مشترک بین x و y را پیدا کند. این حلقه به ازای هر عدد k در این محدوده، بررسی می‌کند که آیا x و y هر دو بر k بخش‌پذیر هستند یا نه. اگر هر دو بر k بخش‌پذیر باشند، k را به عنوان مقدار جی‌سی‌دی پیدا کرده و آن را به عنوان جواب برمی‌گرداند. سپس از حلقه خارج می‌شود.
اگر حلقه به پایان برسد و هیچ مقداری برای k پیدا نشود (یعنی هیچ عددی که همزمان مقسوم علیهٔ x و y باشد پیدا نشود)، تابع به عنوان جواب مقدار پیش‌فرض 1 را بر می گرداند.

سپس، سه نمونه جی‌سی‌دی با ورودی‌های مختلف از تابع فراخوانی شده و نتایج در خروجی چاپ می‌شوند:

جی‌سی‌دی عدد 15 و 18 برابر با 3 است.
جی‌سی‌دی عدد 2 و 5 برابر با 1 است.
جی‌سی‌دی عدد 254 و 365 برابر با 1 است.

راه حل دوم

def calculate_gcd(number1, number2):
    remainder = number1 % number2
    while remainder:
        number1 = number2
        number2 = remainder
        remainder = number1 % number2
    return number2

def calculate_gcd(number1, number2):

remainder = number1 % number2

while remainder:

number1 = number2

number2 = remainder

remainder = number1 % number2

return number2

توضیح راه حل دوم

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

ابتدا باقی‌مانده عدد number1 تقسیم بر number2 را محاسبه می‌کند و در متغیر remainder ذخیره می‌کند.
سپس یک حلقه while شروع می‌شود که تا زمانی که باقی‌مانده ناصفر باشد، ادامه دارد.
در هر مرحله حلقه، number1 به number2 و number2 به remainder نسبت داده می‌شوند.
باقی‌مانده جدید عبارتند از باقی‌مانده قبلی تقسیم بر number2.
این فرآیند تا زمانی که باقی‌مانده صفر شود، ادامه دارد.
در انتها، مقدار غیرصفری در number2 که GCD است، برگردانده می‌شود.

از این تابع می‌توانید برای محاسبه GCD دو عدداستفاده کنید. به عنوان مثال:

result = calculate_gcd(12, 18)
print(result)  # اینجا خروجی 6 است.

1 2	result = calculate_gcd(12, 18) print(result) # اینجا خروجی 6 است.

در این مثال، مقدار بازگشتی تابع GCD دو عدد 12 و 18 عدد 6 است.

راه حل سوم

from functools import reduce
from math import gcd as _gcd
def calculate_gcd(numbers):  
    return reduce(_gcd, numbers)  
numbers = [336, 360]
print("GCD of", ','.join(str(e) for e in numbers))
print(calculate_gcd(numbers))  
numbers = [24, 30, 36]
print("GCD of", ','.join(str(e) for e in numbers))
print(calculate_gcd(numbers))

from functools import reduce

from math import gcd as _gcd

def calculate_gcd(numbers):

return reduce(_gcd, numbers)

numbers = [336, 360]

print("GCD of", ','.join(str(e) for e in numbers))

print(calculate_gcd(numbers))

numbers = [24, 30, 36]

print("GCD of", ','.join(str(e) for e in numbers))

print(calculate_gcd(numbers))

توضیح راه حل سوم

این کد پایتون یک تابع به نام calculate_gcd ایجاد می‌کند که با استفاده از reduce و math.gcd محاسبه‌ی (GCD) بین تمام عناصر یک لیست اعداد را انجام می‌دهد.

توضیحات خط به خط کد:

ابتدا دو ماژول، reduce و gcd از ماژول‌های مورد نیاز به کد اضافه می‌شوند.
تابع calculate_gcd تعریف می‌شود که یک ورودی به نام numbers دارد. این ورودی لیستی از اعداد صحیح را نمایان می‌کند.
تابع calculate_gcd از تابع reduce استفاده می‌کند تا با کم کردن تمام اعداد لیست با یکدیگر و با استفاده از تابع gcd از ماژول math، می تواند (GCD) را محاسبه کند.
دو لیست اعداد به عنوان نمونه‌ها تعریف می‌شوند: numbers = [336, 360] و numbers = [24, 30, 36].
برای هر نمونه از لیست numbers، متنی تازه با استفاده از تابع join و نمایش اعداد به عنوان یک رشته تولید می‌شود. سپس تابع calculate_gcd با استفاده از لیست اعداد به عنوان ورودی فراخوانی می‌شود.
خروجی محاسبه شده GCD به همراه متن تعیین شده نمایش داده می‌شود.

نتایج خروجی:

برای لیست [336, 360]:

GCD این دو عدد برابر با 24 است.

برای لیست [24, 30, 36]:

GCD این سه عدد برابر با 6 است.

Meghdad Alibakhshi

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