Dê um algoritmo recursivo para encontrar mdc
, em que
e
são números inteiros não negativos, com base nestes fatos:
se
se
e
forem pares,
se
for par e
for ímpar e
.
Passo 1
Queremos um algoritmo recursivo para calcular
para inteiros não negativos
, usando as seguintes propriedades:
-
se . -
. - Se
e são pares então . - Se
é par e é ímpar então . - Caso restante, usamos subtração:
.
Passo 2
Implementamos o caso-base de zero:
se retornamos
;
se retornamos
.
se
se
Passo 3
Garantimos que
usando a simetria
Passo 4
Tratamos o caso em que
e
são pares:
Passo 5
Se
é par e
é ímpar, retiramos fator 2 de
:
Passo 6
Se
é ímpar e
é par, aplicamos a simetria do Passo 3 ou escrevemos diretamente
Passo 7
Caso contrário (
e
ímpares), subtraímos:
Resposta
Função mdc(a,b):
se (a \(=0\)) retorna b
se (b \(=0\)) retorna a
se (a > b) retorna mdc(b, a)
se (a é par) e (b é par) retorna 2 * mdc(a/2, b/2)
se (a é par) e (b é ímpar) retorna mdc(a/2, b)
se (a é ímpar) e (b é par) retorna mdc(a, b/2)
// aqui ambos são ímpares
retorna mdc(a, b - a)