Dê um algoritmo recursivo para encontrar mdc (a, b), em que a e b são números inteiros não negativos, com base nestes fatos: \operatorname{mdc}(a, b)=\operatorname{mdc}(b, a) se a>b, \operatorname{mdc}(0, b) =b, \operatorname{mdc}(a, b)=2 \operatorname{mdc}(a / 2, b / 2) se a e b forem pares, \operatorname{mdc}(a, b)=\operatorname{mdc}(a / 2, b) se a for par e b for ímpar e \operatorname{mdc}(a, b)=\operatorname{mdc}(a, b-a).

Passo 1

Queremos um algoritmo recursivo para calcular \mathrm{mdc}(a,b) para inteiros não negativos a,b, usando as seguintes propriedades:
  1. \mathrm{mdc}(a,b)=\mathrm{mdc}(b,a) se a>b.
  2. \mathrm{mdc}(0,b)=b.
  3. Se a e b são pares então \mathrm{mdc}(a,b)=2\;\mathrm{mdc}(a/2,b/2).
  4. Se a é par e b é ímpar então \mathrm{mdc}(a,b)=\mathrm{mdc}(a/2,b).
  5. Caso restante, usamos subtração: \mathrm{mdc}(a,b)=\mathrm{mdc}(a,b-a).

Passo 2

Implementamos o caso-base de zero:
se a=0 retornamos b;
se b=0 retornamos a.

Passo 3

Garantimos que a\le b usando a simetria
\mathrm{mdc}(a,b)=\mathrm{mdc}(b,a)\quad\text{se }a>b.

Passo 4

Tratamos o caso em que a e b são pares:
\mathrm{mdc}(a,b)=2\;\mathrm{mdc}\bigl(a/2,b/2\bigr).

Passo 5

Se a é par e b é ímpar, retiramos fator 2 de a:
\mathrm{mdc}(a,b)=\mathrm{mdc}\bigl(a/2,b\bigr).

Passo 6

Se a é ímpar e b é par, aplicamos a simetria do Passo 3 ou escrevemos diretamente
\mathrm{mdc}(a,b)=\mathrm{mdc}\bigl(a,b/2\bigr).

Passo 7

Caso contrário ( a e b ímpares), subtraímos:
\mathrm{mdc}(a,b)=\mathrm{mdc}\bigl(a,b-a\bigr).

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)

Exercícios de Livros Relacionados