6

A versão não-recursiva está abaixo:

def mdc(a,b):
    while b !=0:
        resto = a % b
        a = b
        b = resto

    return a

print(mdc(50,2))

Uma tentativa recursiva seria:

def mdc(a, b):
    if b == 0:
        return a
    resto = a % b
    a = b
    b = resto
    return mdc(a, b)  

O que acham? Alguma outra solução?

0

4 Respostas 4

17

A solução não-recursiva poderia ser reescrita como:

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

print(mdc(70, 25)) # 5
    

Veja funcionando no Repl.it | Ideone | GitHub Gist

Já a versão recursiva poderia ser reescrita como:

def mdc(a, b):
    return a if not b else mdc(b, a % b)
    
print(mdc(70, 25)) # 5

Veja funcionando no Repl.it | Ideone | GitHub Gist

Mas a solução mais simples é a função nativa:

from fractions import gcd

print(gcd(70, 25)) # 5

Veja funcionando no Repl.it | Ideone | GitHub Gist


Obs: a partir do Python 3.5 a função fractions.gcd está deprecated, e na versão 3.9 ela foi removida, e nesse caso deve-se utilizar a função que está no módulo math:

from math import gcd

print(gcd(70, 25)) # 5

Um detalhe interessante desta função é que a partir do Python 3.9 ela aceita uma quantidade arbitrária de argumentos:

from math import gcd
# mais de 2 argumentos, somente a partir do Python 3.9    
print(gcd(70, 25, 100, 15, 90)) # 5
4

Olá, por aqui parece estar tudo correto.
Só uma pequena informação é que em python em vez de:

a = b
b = resto

Poder-se-ia escrever:

a,b = b,resto

E eu, pessoalmente, prefiro usar a versão recursiva, pois acho mais fácil de depurar.
E acho que não existe nenhuma outra maneira tão simples, como as apresentadas, de implementar este algoritmo.

2

Montei esse código pra essa situação, é possivel passar uma lista de numeros para facilitar quando realmente for usar a função.

def __mdc_(x,y):
    while(y):
        x,y=y,x%y
    return x

def mdc(nums):

    if len(nums) == 2:
        return __mdc_(nums[0], nums[1])
    else:
        mdc_val = __mdc_(nums[0], nums[1])
        nums[0] = mdc_val
        del nums[1]
        return mdc(nums)

>>> mdc([30, 54, 72])
>>> 6
-3
def mdc(a,b):
    if b == 0:
        return a
    else:
        return mdc(b, a%b)

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .