GCD с использованием алгоритма Евклида

Ниже приведена проблема, взятая из здесь .

  

Вопрос 10: GCD *

     

Наибольший общий делитель двух натуральных чисел a и b является наибольшим целым числом, которое равномерно делит оба числа (без остатка). Евклид, греческий математик в 300 г. до н.э., понял, что наибольший общий делитель а и Ь является одним из следующих:

     

меньшее значение, если оно равномерно делит большее значение, ИЛИ   наибольший общий делитель меньшего значения и остаток от большего значения, деленный на меньшее значение   Другими словами, если a больше b и a не делится на b, то

     

gcd(a, b) == gcd(b, a % b)

     

Запись функции gcd рекурсивно с использованием алгоритма Евклида.

def gcd(a, b):
    """Returns the greatest common divisor of a and b.
    Should be implemented using recursion.

    >>> gcd(34, 19)
    1
    >>> gcd(39, 91)
    13
    >>> gcd(20, 30)
    10
    >>> gcd(40, 40)
    40
    """
    "*** YOUR CODE HERE ***"

Решение:

def gcd(a, b):
    """Returns the greatest common divisor of a and b.
    Should be implemented using recursion.

    >>> gcd(34, 19)
    1
    >>> gcd(39, 91)
    13
    >>> gcd(20, 30)
    10
    >>> gcd(40, 40)
    40
    """
    if b > a:
        if b % a == 0:
            return a
        else:
            return gcd(b % a, a)
    else:
        if a % b == 0:
            return b
        else:
            return gcd(b, a % b)        

Как я могу улучшить этот вложенный блок if?

11 голосов | спросил overexchange 2 J000000Thursday15 2015, 05:35:22

3 ответа


13

Одна из приятных вещей с рекурсией заключается в том, что вы можете использовать ее для обработки аргументов.

Если у вас есть условие для обработки условия b > a, вы можете вместо этого использовать рекурсию .....

def gcd(a, b):
    """Returns the greatest common divisor of a and b.
    Should be implemented using recursion.

    >>> gcd(34, 19)
    1
    >>> gcd(39, 91)
    13
    >>> gcd(20, 30)
    10
    >>> gcd(40, 40)
    40
    """
    if b > a:
        return gcd(b, a)

    if a % b == 0:
        return b

    return gcd(b, a % b)        
ответил rolfl 2 J000000Thursday15 2015, 06:01:44
9

Это немного неуместно, но вы можете легко улучшить свой код, удалив рекурсию.

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

Некоторые могут утверждать, что это уменьшает читаемость, но с именем gcd, мне трудно поверить, особенно учитывая тот факт, что евклидова алгоритм довольно популярен.

ответил Confuse 3 SatEurope/Moscow2016-12-03T13:11:06+03:00Europe/Moscow12bEurope/MoscowSat, 03 Dec 2016 13:11:06 +0300 2016, 13:11:06
2

Начиная с версии 3.5 Python, мы можем использовать функцию math.gcd(a, b) из math. Таким образом, вместо создания вложенного, если мы можем использовать эту функцию.

Из документации :

  

math.gcd (a, b)
  Возвращает наибольший общий делитель целых чисел a   и b. Если либо a, либо b отличны от нуля, то значение gcd (a, b) является   наибольшее положительное целое число, разделяющее как a, так и b. gcd (0, 0) возвращает   0.

math.gcd(a, b) реализовано как :

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a
ответил Ram Chandra Giri 9 +03002017-10-09T15:38:33+03:00312017bEurope/MoscowMon, 09 Oct 2017 15:38:33 +0300 2017, 15:38:33

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

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132