Exercicio

[fmario@ig.com.br]

Exercicio 5.73 do livro do Sedgewick, pagina 229.
 

 
Ele define o que eh uma arvore de fibonacci. Ate ai tudo bem. Mas qual e a 
pergunta do exercicio? Esta meio confuso... Ele diz: "Give the height and 
external path length of a Fibonacci tree of height n, as a function of N, 
the number of nodes in the tree".
 

 
Bom, dar a altura de uma arvore de altura n parece facil demais para ser 
verdade... Tentei entao calcular a altura da arvore em funcao de N, mas 
parece ser bem complicado. Tentei fazer o inverso, calcular N em funcao da 
altura da arvore. Chegei a recorrencia:
 

 
N(0) = 1, pois arvore de altura 0 tem so um no externo
 
N(1) = 3, pois arvore de altura 1 tem um no interno e dois externos 
(definicao dele)
 
N(h) = 1 + N(h-1) + N(h-2)
 

 
Essa recorrencia eh bem parecida com a dos numeros de Fibonacci. Eu tentei 
encontrar uma correspondencia mas nao consegui. Se conseguisse, poderia 
utilizar a ja manjada formulinha
 

 
F(n) = ((1 + sqrt(5))/2)^n - ((1 - sqrt(5))/2)^n)/sqrt(5)
 

 
para resolver a recorrencia. Poderia entao tentar pegar a funcao inversa, 
que seria o que o exercicio pede... Ela nao estaria definida em muitos 
pontos, entretanto, pois nao ha arvore de fibonacci com 17 nos, por 
exemplo.
 

 
Alguns valores que eu consegui:
 

 
N(2) = 5, N(3) = 9, N(4) = 15, N(5) = 25, N(6) = 41, N(7) = 67.
 

 
Quem conseguiu fazer o exercicio, por favor me ajude!
 

 
[]'s
 
Fernando 

_________________________________________________________
Oi! Você quer um iG-mail gratuito?
Então clique aqui: http://www.ig.com.br/paginas/assineigmail.html