RE: Exercicio

[Yoshiharu Kohayakawa <yoshi@ime.usp.br>]

fmario@ig.com.br wrote (on Thursday, 12 Apr 2001, at 23:14:43 -0300):
 > 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. 

Somando 1 dos dois lados da recorrencia que voce encontrou, obtemos

N(h) + 1 = (N(h-1) + 1) + (N(h-2) + 1)

Ponha M(h) = N(h) + 1.  Entao, temos

  M(0) = 2, M(1) = 4, 

e

  M(h) = M(h-1) + M(h-2), 

para todo h > 1.  Uma verificacao simples mostra que M(h) = 2*F(h+2) é a
solucao da recorrencia acima (F(0) = 0, F(1) = 1, F(h) = F(h-1) + F(h-2) para
todo h > 1).  Assim, N(h) = 2*F(h+2) - 1.

 >                                                 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. 

Infelizmente, estou sem o Sedgewick aqui.  Qual é a definicao de árvore de
Fibonacci que ele apresenta?  Y.

 > 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