"A good algorithm is like a sharp knife:
it does what it is supposed to do with a minimum amount of applied effort.
Using the wrong algorithm to solve a problem
is like trying to cut a steak with a screwdriver:
you may eventually get a digestible result,
but you will expend considerably more effort than necessary,
and the result is unlikely to be aesthetically pleasing."
--Th. Cormen, Ch. Leiserson, R. Rivest,
Introduction to Algorithms
�
Suponha que m e n s�o n�meros inteiros. Dizemos que n divide m se n > 0 e m % n == 0. Note que,
m % n == 0 se e somente se n > 0 e m = kn para algum inteiro k.
O máximo divisor comum de dois inteiros m e n � o maior inteiro que divide ambos:
mdc(m,n) = max{ k | k� claro que se m == n == 0, então o máximo não faz sentido. Assim, estaremos sempre supondo que pelo menos um dos números dados � não nulo.divide me kdivide n }.
PROBLEMA: Dados inteiros m e n determinar o máximo dividor comum de m e n (mdc(m,n)).
Vamos examinar dois algoritmos para o problema: um óbvio e lento e outro sofisticado e bem mais rápido.
Vamos começar com um algoritmo simples e óbvio:
#define min(m,n) ((m) < (n) ? (m) : (n)) long mdc(long m, long n) { int candidato; candidato = min(abs(m),abs(n)); while (m % candidato != 0 || n % candidato != 0) /* 1 */ candidato--; return candidato; }
Invariante e correção. Para compreender o funcionamento da
função,
basta verificar que
no início de cada repetição do while,
no ponto /* 1 */
, vale a seguinte propriedade
m % t != 0 ou n % t != 0 para todo t, t >= candidato.Esta propriedade, que pode ser demonstrada por indução (confira!), é dita um invariante do comando
while
. Deste invariante podemos observar facilmente a
correção da função (correção da função = a função funciona).
Consumo de tempo. Quantas iterações do while
essa
função faz? Em outras palavras, quantas vezes o comando
"candidato--
" é executado? A resposta é
min(m,n)-1 no pior caso.
(Na presente discussão estamos supondo que m >= 0 e n >= 0.) Neste caso costuma-se dizer que a quantidade de tempo consumida pelo algoritmo, no pior caso, é proporcional a min(m,n), ou ainda, que o tempo gasto pelo algoritmo é da ordem de min(m,n). [A abreviação de "ordem x" é O(x).] Isto significa que o número de operações feitas pela função cresce (no ior caso) como uma função linear de min(m,n).
Por exemplo, para a chamada mdc(317811,514229) a função executará 317811 - 1 iterações, pois mdc(317811,514229) == 1 . Ou seja, os inteiros 317811 e 514229 são relativamente primos.
&EACUTE; possível resolver o problema fazendo menos operações (isto é, consumindo uma quantidade de tempo menor)? A resposta é SIM.
mdc(m,0) == m;
mdc(m,n) == mdc(n, m % n), para n > 0.
Assim, por exemplo,
mdc(12,18) == mdc(18,12) == mdc(12,6) == mdc(6,0) == 6.
A correção da recorrência proposta por Euclides é baseada no seguinte teorema.
Teorema 1 Seja m um inteiro não-negativo e n um inteiro positivo. Para cads inteiro positivo d tem-se que(m % d == 0) e (n % d == 0) se e somente se (n % d == 0) e ((m % n) % d == 0).
Exercício: Prove o teorema 1.
Eis a implementação recursiva do algoritmo de Euclides para determinar mdc(m,n).
long euclides_r(long m, long n) { int i; if (n==0) return m; return euclides_r (n, m % n); }
A seqüência abaixo ilustra as chamadas recursivas do algoritmo de Euclides para determinar o mdc de 317811 e 514229:
mdc(317811,514229) mdc(514229,317811) mdc(317811,196418) mdc(196418,121393) mdc(121393,75025) mdc(75025,46368) mdc(46368,28657) mdc(28657,17711) mdc(17711,10946) mdc(10946,6765) mdc(6765,4181) mdc(4181,2584) mdc(2584,1597) mdc(1597,987) mdc(987,610) mdc(610,377) mdc(377,233) mdc(233,144) mdc(144,89) mdc(89,55) mdc(55,34) mdc(34,21) mdc(21,13) mdc(13,8) mdc(8,5) mdc(5,3) mdc(3,2) mdc(2,1) mdc(1,0) mdc de 317811 e 514229 e' 1.
Quanto tempo o algoritmo leva para parar? Este tempo é certamente
proporcional ao número de chamadas recursivas. Suponha que a função
euclides_r
faz k chamadas recursivas e que no início da
1a. chamada ao algoritmo tem-se que 0 < n <= m.
Sejam
(m,n) == (m0,n0), (m1,n1), (m2,n2), ... , (mk,nk) == (mdc(m,n),0),
os valores do par de parâmetros (m,n) no início de cada uma das chamadas da função. Por exemplo, para m==514229 e n==317811 tem-se
(m0,n0) == (514229,317811), (m1,n1) == (317811,196418), ... , (m27,n27) == (1,0),
Estimaremos o valor de k em função de m e n. Note que mi+1 == ni e ni+1 == mi % ni para i=1,2,...,k. Note ainda que para inteiros a e b, 0 < b <= a vale que
a % b < a/2 (verifique!).
Desta forma tem-se que
m2 == n1 == m0 % n0 == m % n < m/21
m4 == n3 == m2 % n2 < m2/2 < m/4 == m/22
m6 == n5 == m4 % n4 < m4/2 < m/8 == m/23
m8 == n7 == m6 % n6 < m6/2 < m/16 == m/24
m10 == n9 == m8 % n8 < m8/2 < m/32 == m/25
...
...
...
Percebe-se que depois de cada 2 chamadas recursivas o valor do primeiro parâmetro cai de pelo menos metade. Assim, quando k é tal que 2k/2 <= m < 2(k/2)+1 o valor de mk é menor que m/2k/2 == 1 e o algoritmo pára depois de no máximo mais uma chamada recursiva. Logo, o número k de chamadas recursivas é limitado por
2 log2(m) + 1 ,
quando 0 < n <= m e por
2 log2(m) + 2 ,
quando 0 < m < n, o que é muito melhor que as min(m,n)
iterações do algoritmo óbvio. Para o exemplo acima, onde
m==317811 e n==514229,
2 log2(m) + 2 == 2 * 18 + 2 == 38 e o número
de chamadas recursivas por euclides_r(317811,514229)
feitas foram 28.
t | (int) log(t) |
4 | 2 |
5 | 2 |
6 | 2 |
10 | 3 |
64 | 6 |
100 | 6 |
128 | 7 |
1000 | 9 |
1024 | 10 |
1000000 | 19 |
Resumindo, a quantidade de tempo consumida pelo algoritmo de Euclides é, no pior caso, proporcional a log (min(m,n))
Os 10 primeiros números da seqüência de Fibonacci são:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
Os números de Fibonacci são definidos (ou podem ser calculados) pela seguinte função recursiva:
long fibonacci(long n) { if (n == 0) return 0; if (n == 1) return 1; return fibonacci(n-1) + fibonacci(n-2); }
Os números de Fibonacci estão intimamente relacionados com o algoritmo de Euclides, como mostra o exercício abaixo.
Exercício:
Se m > n >= 0 e se a chamada euclides_r(m,n)
faz
k >=1 chamadas recursivas, então m >= fibonacci(k+2) e
n >= fibonacci(k+1).
[Sugestao: demonstre por indução em k.]
Uma conseqüência imediata deste exercício é
Para todo inteiro k > 0, se m > n >= 0 e n <
fibonacci(k+1), então a chamada euclides_r(m,n)
faz
menos de k chamadas recursivas.
Por exemplo, fibonacci(28) == 317811 e fibonacci(29) = 514229 e a chamada euclides_r(514229,317811) faz 27 chamadas recursivas. Na verdade, números de Fibonacci consecutivos são os que dão mais trabalho para o algoritmo de Euclides.
Exercício:
A chamada euclides_r(fibonacci(k+1),fibonacci(k))
faz
k-1 chamadas recursivas.
[Sugestao: demonstre por indução em k.]
Estes exercícios se referem à versão limpa de buscabinaria descrita na seção anterior.
mdc
faz um número de iterações (do comando
while
) maior ou igual ao feito (pelo
comando do ... while
) pela função euclides_i
abaixo.
long euclides_i(long m, long n) { long r; do { r = m % n; m = n; n = r; } while (r != 0); return m; }
7 % -3
?
Qual � o valor que o computador devolve?