Module: زیربرنامه های (پایتون): رویه ها و توابع - 2


Problem

4/8

الگوریتم اقلیدس

Theory Click to read/hide

الگوریتم اقلیدس

الگوریتم اقلیدس — کارآمد BC" title="Algorithm">الگوریتم برای ​​یافتن بزرگترین مقسوم علیه مشترک  دو اعداد صحیح (یا عمومی خطوط). نام الگوریتم برگرفته از یونانی ریاضی اقلیدس (قرن سوم قبل از میلاد )، که اولین بار آن را به سبک VII و X کتاب «آغازها". این یکی از قدیمی ترین الگوریتم های عددی است که امروزه مورد استفاده قرار می گیرد.

ریاضی را به خاطر بسپارید.

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

به عنوان مثال، اعداد 12 و 18 مقسوم علیه های مشترک دارند: 2، 3، 6. بزرگترین مقسوم علیه مشترک 6 است. به صورت زیر نوشته می شود: gcd(12، 18) = 6

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


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

Problem

یک تابع بنویسید که gcd دو عدد را محاسبه کند.


ورودی
رشته ورودی شامل دو عدد طبیعی است که با فاصله – a و b 

Impprint
برنامه باید یک عدد طبیعی صادر کند: GCD اعداد داده شده.

 

نمونه‌ها
<سر> <بدن>
# ورودی خروجی
1 14 21 7


time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
Python
Write the program below 
a, b = map(int, input().split())
print(NOD(a,b))

     

Program check result

To check the solution of the problem, you need to register or log in!