A maior rede de estudos do Brasil

Grátis
Estruturas_de_Dados_e_Algoritmos_em_C.erivanildo- Blog - conhecimentovaleouro.blogspot.com by @viniciusf666

Pré-visualização | Página 35 de 50

Pelo que, a versão 
iterativa é mais eficiente e simples de programar. 
4.4 Números de Fibonacci 
Um exemplo de cálculo recursivo mais complexo do que o cálculo do factorial é o cálculo 
dos números de Fibonacci, que são definidos pela seguinte relação de recorrência e cuja 
implementação recursiva se apresenta na Figura 4.7. 
 
°¯
°®
­
t�
 
 
 
 2n se 2),-nFibonacci( 1)-nFibonacci( 
1 n se 1, 
0 n se 0, 
 n)Fibonacci( 
 
 
Figura 4.7 - Função que calcula os números de Fibonacci de forma recursiva. 
A Figura 4.8 apresenta a árvore de recorrência do cálculo do Fibonacci de 5. 
 
FIBONACCI(5)
FIB(5) = FIB(4)+FIB(3)
FIBONACCI(4)
FIB(4) = FIB(3)+FIB(2)
FIBONACCI(3)
FIB(3) = FIB(2)+FIB(1)
FIBONACCI(3)
FIB(3) = FIB(2)+FIB(1)
FIBONACCI(1)
FIB(1) = 1
FIBONACCI(2)
FIB(2) = FIB(1)+FIB(0)
FIBONACCI(2)
FIB(2) = FIB(1)+FIB(0)
FIBONACCI(2)
FIB(2) = FIB(1)+FIB(0)
FIBONACCI(1)
FIB(1) = 1
FIBONACCI(1)
FIB(1) = 1
FIBONACCI(0)
FIB(0) = 0
FIBONACCI(1)
FIB(1) = 1
FIBONACCI(0)
FIB(0) = 0
FIBONACCI(1)
FIB(1) = 1
FIBONACCI(0)
FIB(0) = 0
 
Figura 4.8 - Visualização gráfica da invocação da função Fibonacci recursiva. 
Como se pode ver, esta solução é computacionalmente ineficiente, porque para calcular o 
Fibonacci de 5, calcula repetidamente alguns valores intermédios. Mais concretamente, 
duas vezes o Fibonacci de 3, três vezes o Fibonacci de 2, cinco vezes o Fibonacci de 1 e 
três vezes o Fibonacci de 0. Por outro lado, devido à dupla invocação recursiva o número 
de operações explode rapidamente. Como se pode ver na Figura 4.8, o cálculo do 
Fibonacci de 5 custa 7 adições. Para se calcular o Fibonacci de 6, temos que calcular o 
Fibonacci de 5 e o Fibonacci de 4, o que dá um total de 12 adições. O Fibonacci de 7 custa 
20 adições, o Fibonacci de 8 custa 33 adições. Ou seja, o número de adições quase que 
duplica quando se incrementa o argumento da função de uma unidade. Pelo que, o tempo 
de execução desta função é praticamente exponencial. 
unsigned int FIBONACCI (int N) 
{ 
 if (N <= 0) return 0; /* Fibonacci de 0 */
 if (N <= 2) return 1; /* Fibonacci de 1 e de 2 */
 return FIBONACCI (N-1) + FIBONACCI (N-2); /* Fibonacci de n > 2 */
} 
7 CAPÍTULO 4 : RECURSIVIDADE 
 
 
Uma forma de resolver problemas recursivos de maneira a evitar o cálculo repetido de 
valores consiste em calcular os valores de baixo para cima e utilizar um agregado para 
manter os valores entretanto calculados. Este método designa-se por programação 
dinâmica e reduz o tempo de cálculo à custa da utilização de mais memória para armazenar 
valores internos. Esta solução é apresentada na Figura 4.9, sendo o cálculo efectuado do 
Fibonacci de 0 até ao Fibonacci de N. Os três primeiros valores, ou seja, o Fibonacci de 0, 
de 1 e de 2, são colocados na inicialização do agregado. 
 
 
Figura 4.9 - Função que calcula os números de Fibonacci de forma dinâmica. 
Mas, se repararmos bem na solução dinâmica verificamos que de facto a cálculo do 
Fibonacci de N só precisa dos valores do Fibonacci de N-1 e do Fibonacci de N-2, pelo 
que, podemos substituir a utilização do agregado por apenas três variáveis simples. Uma 
para armazenar o valor a calcular, que designamos por PROXIMO, outra para armazenar o 
valor acabado de calcular, que designamos por ACTUAL e outra para armazenar o valor 
calculado anteriormente, que designamos por ANTERIOR. A Figura 4.10 apresenta esta 
versão iterativa. O valor inicial de ANTERIOR é 0 e corresponde ao Fibonacci de 0, o 
valor inicial de ACTUAL é 1 e corresponde ao Fibonacci de 1 e o valor de PROXIMO 
corresponde ao Fibonacci que se pretende calcular de forma iterada, e é igual à soma do 
ANTERIOR com o ACTUAL. 
 
 
 Figura 4.10 - Função que calcula os números de Fibonacci de forma iterativa. 
Esta solução iterativa é a melhor das três soluções. É a mais rápida e a que gasta menos 
memória. O tempo de execução desta solução é linear, ou seja, o cálculo do Fibonacci de 
2N custa aproximadamente o dobro do tempo do cálculo do Fibonacci de N. O maior 
número de Fibonacci que se consegue calcular em aritmética inteira de 32 bits é o Fibonacci 
de 47 que é igual a 2971215073. 
unsigned int FIBONACCI (int N) 
{ 
 int I; unsigned int ANTERIOR = 0, ACTUAL = 1, PROXIMO; 
 
 if (N <= 0) return 0; /* Fibonacci de 0 */
 if (N == 1) return 1; /* Fibonacci de 1 */
 
 for (I = 2; I <= N; I++) /* Fibonacci de n >= 2 */
 { 
 PROXIMO = ACTUAL + ANTERIOR; 
 ANTERIOR = ACTUAL; 
 ACTUAL = PROXIMO; 
 } 
 
 return PROXIMO; 
} 
unsigned int FIBONACCI (int N) 
{ 
 int I; unsigned int FIB[50] = {0,1,1}; 
 
 if (N <= 0) return 0; /* Fibonacci de 0 */
 if (N <= 2) return 1; /* Fibonacci de 1 e de 2 */
 
 for (I = 3; I <= N; I++) /* para calcular o Fibonacci de n > 2 */
 FIB[I] = FIB[I-1] + FIB[I-2]; 
 
 return FIB[N]; 
} 
PROGRAMAÇÃO ESTRUTURAS DE DADOS E ALGORITMOS EM C 8 
4.5 Cálculo dos coeficientes binomiais 
O coeficiente binomial C(n,k), que representa o número de combinações de n elementos a 
k elementos é dado pela seguinte expressão. 
 
k! k)!-(n
n!
 k) C(n, ˜ 
 
Em muitas situações, mesmo para valores finais representáveis em variáveis inteiras, os 
valores parcelares podem ficar corrompidos, uma vez que o factorial rapidamente dá 
overflow em aritmética inteira. Por exemplo, duas situações limites são o C(n,0) e o C(n,n), 
em que o número de combinações é igual a 1 (n!/n!). Pelo que, a utilização da definição 
para calcular C(n,k) está normalmente fora de questão e neste caso nem sequer podemos 
recorrer a aritmética real, devido à consequente perda de precisão. Uma forma de resolver 
o problema, passa por eliminar a necessidade do cálculo do factorial recorrendo a um 
processo iterativo, descoberto por Blaise Pascal e que é conhecido pelo Triângulo de 
Pascal. Como se pode ver na Figura 4.11, cada elemento com excepção dos elementos 
terminais de cada linha, ou seja C(n,0) e C(n,n), é calculado através da soma dos valores da 
linha anterior. Ou seja, C(n,k) = C(n-1,k) + C(n-1,k-1), com n>k>0. A Figura 4.11 
representa de forma gráfica o cálculo de C(5,3) que é igual a 10. Repare que existem valores 
que são usados duas vezes, o que significa que também vão ser calculados duas vezes. 
 
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
 
Figura 4.11 - Triângulo de Pascal. 
A função recursiva para calcular o coeficiente binomial, que se apresenta na Figura 4.12, 
invoca-se recursivamente duas vezes e tem como condições de paragem os elementos 
terminais, cujo valor é 1. A primeira condição de teste evita que a função entre num 
processo recursivo infinito, caso a função seja invocada para k menor do que n. 
 
 
Figura 4.12 - Função recursiva para calcular os coeficientes binomiais. 
 
 
unsigned int COMBINACOES (int N, int K) 
{ 
 if (K > N) return 0; /* invocação anormal (valor devolvido 0) */
 if ((K == 0) || (K == N)) return 1; /* condições de paragem */
 return COMBINACOES (N-1, K) + COMBINACOES (N-1, K-1); 
} 
9 CAPÍTULO 4 : RECURSIVIDADE 
 
 
Esta implementação é no entanto pouco prática para valores de n e k elevados, antes de 
mais porque, tal como no caso dos números de Fibonacci, repete o cálculo de certos 
valores e portanto, é computacionalmente ineficiente. Mas, o grande problema deste 
algoritmo é que devido à dupla invocação recursiva a invocação também explode 
rapidamente. 
 
A solução dinâmica, que se apresenta na Figura 4.13, implica a utilização de um agregado 
bidimensional para armazenar os coeficientes binomiais, à medida que estes são calculados. 
 
 
Figura 4.13 - Função dinâmica para calcular os coeficientes binomiais. 
Enquanto que a solução recursiva