Python

Задача на питоне

Даны два целых числа A>0 и B>0 , найти наибольший общий делитель.
МШ
Максим Шувалов
89
Вот я ввёл два числа в алгоритм, приведённый выше, а мне говорят:
 Traceback (most recent call last):

  File "/home/main.py", line 113, in 

    print("НОД(", a, ",", b, ") =", gcd(a, b))

  File "/home/main.py", line 108, in gcd

    return gcd(b, a % b)

  File "/home/main.py", line 108, in gcd

    return gcd(b, a % b)

  File "/home/main.py", line 108, in gcd

    return gcd(b, a % b)

  [Previous line repeated 995 more times]

  File "/home/main.py", line 106, in gcd

    if b == 0:

RecursionError: maximum recursion depth exceeded in comparison
Числа были такие:
 a = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

b = 26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626
При том, что библиотечная функция math.gcd на них отрабатывает нормально, gcd = 1.

Почему так? Потому что не надо делать рекурсию, когда она не нужна. Реализация с циклом и пишется короче, и отрабатывает быстрее, и не падает по переполнению стека:
 def gcd(a, b):

    while b != 0: a, b = b, a % b

    return a
И вся обычная кухня с вводом-выводом чиселок:
 a = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

b = 26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626

print("НОД(", a, ",", b, ") =", gcd(a, b))
Bulat Painter
Bulat Painter
54 053
Лучший ответ
from math import gcd
A, B = map(int, input('A B: ').split())
print(gcd(A, B))
Красивый Принц
Красивый Принц
66 572
Юрий Кудрявцев Ничего себе, так ты не только калькулятором владеешь, так еще и в тупую умеешь использовать функции питона? Жалко что алгоритм евклида тебе никогда не понять
Красивый Принц Ну надо же: бывают же такие психически больные скоты - всё гадят и гадят в чужих ответах! А всё почему? Да потому что делать больше ничего не умеют и вообще по жизни - никто!
С рекурсивной функцией реализации метода Евклида чтобы программа работала без ошибок лучше её сделать так:
 from sys import setrecursionlimit 

setrecursionlimit(300000); s = 'Неправильный ввод' 

def gcd(x, y): z = x % y; return gcd(y, z) if z else y 

while True: 

    try: 

	A, B = map(int, input('A B: ').split()) 

	if A < 1 or B < 1: print(s) 

	print('GCD(A,B) = ', gcd(A, B)) 

    except: print(s)
Но я что-то тоже почему-то не думаю, что рекурсия здесь - лучшее решение. По-моему с итерационным циклом while всё таки лучше...
Для нахождения наибольшего общего делителя (НОД) двух целых чисел можно использовать алгоритм Евклида. Алгоритм заключается в том, что из большего числа вычитается меньшее до тех пор, пока они не станут равными. Затем полученное число (которое равно искомому НОД) ищется рекурсивно для двух меньших чисел. Процесс продолжается до тех пор, пока одно из чисел не станет равным нулю.

Пример кода на Python:
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)

# пример использования функции
a = 24
b = 16
print("НОД(", a, ",", b, ") =", gcd(a, b))

В этом примере функция "gcd" рекурсивно находит наибольший общий делитель для двух чисел "a" и "b". Если второе число равно нулю, то функция возвращает первое число. В противном случае, функция вызывает саму себя с аргументами "b" и остатком от деления "a" на "b".

В конце примера функция "gcd" вызывается с аргументами 24 и 16, и на экран выводится значение НОД, равное 8.
Нурлан Уразгалиев
Нурлан Уразгалиев
1 323
Bulat Painter Не работает на моих данных.
 Traceback (most recent call last):

  File "/home/main.py", line 113, in 

    print("НОД(", a, ",", b, ") =", gcd(a, b))

  File "/home/main.py", line 108, in gcd

    return gcd(b, a % b)

  File "/home/main.py", line 108, in gcd

    return gcd(b, a % b)

  File "/home/main.py", line 108, in gcd

    return gcd(b, a % b)

  [Previous line repeated 995 more times]

  File "/home/main.py", line 106, in gcd

    if b == 0:

RecursionError: maximum recursion depth exceeded in comparison

Похожие вопросы