Блог

Главная - Вопросы по программированию - Проблема с использованием алгоритма Евклида в рекурсивной функции

Проблема с использованием алгоритма Евклида в рекурсивной функции

#python #recursion

#python #рекурсия

Вопрос:

Я начинающий ученик и уже некоторое время просматриваю этот код на PythonTutor, и я получаю правильное значение для ‘final’ за 27 шагов, но, похоже, не могу понять, как заставить цикл while прекратить выполнение и вычисление остатков. Как я могу получить возврат из цикла if, чтобы он стал конечным результатом программы? В данном случае мы используем алгоритм Евклида для вычисления.

 def gcdRecur(a, b):
    '''
    a, b: positive integers
    
    returns: a positive integer, the greatest common divisor of a amp; b.
    '''
final=''    
high=max(a,b)
    result=min(a,b)
    while high%result>0:
        result-=1
        return result*gcdRecur(b,(a%b))
    if high%result==0:
        final=result
        return final
a=1071 
b=462
final_ans=gcdRecur(a,b)
print(final_ans)

Комментарии:

1. Разве это не должно быть просто return gcdRecur(b,(a%b)) ?

2. зачем размещать () вокруг (a%b) ? Какая польза while , это просто if замаскированный

3. Кроме того, вы можете просто использовать if вместо while , и должны использовать значения min и max вместо original a и b в рекурсивном вызове.

Ответ №1:

Я думаю, что ваши провода пересеклись по Евклиду. Если вы настаиваете на том, чтобы входные данные были целыми положительными числами (т. Е. Не 0 и не отрицательными), вы можете использовать алгоритм Евклида на основе вычитания:

 def gcdRecur(a, b):
    '''
    a, b: positive integers
    returns: a positive integer, the greatest common divisor of a amp; b.
    '''

    if a == b:
        return a

    if a > b:
        a -= b
    else:
        b -= a

    return gcdRecur(a, b)

и избегайте min() , max() и modulus ( % ) . Если вы используете модульный вариант алгоритма Евклида, то вам не требуется столь жестких ограничений на входные значения, и это может быть выражено рекурсивно как просто:

 def gcdRecur(a, b):
    return a if not b else gcdRecur(b, a % b)