Exercicio & Fibonacci

[fmario@ig.com.br]

Definicao da arvore de Fibonacci: A Fibonacci tree of height n > 2 is a 
binary tree with a Fibonacci tree of height n-1 in one subtree and a 
Fibonacci tree of height n-2 in the other subtree. A Fibonacci tree of 
height 0 is a single external node, and a Fibonacci tree of height 1 is a 
single internal node with two external children.
 

 
Bom, para comecar, veja que na primeira linha ele se confunde com o sinal... 
acho que eh n >= 2 e nao n > 2, nao teria sentido.
 
Alem disso, pela definicao, uma arvore de Fibonacci nao poderia ter 17 nos, 
por exemplo...
 

 
Outra coisa que eu percebi eh que, de fato, assim como na sequencia de 
Fibonacci, a razao entre dois termos consecutivos na sequencia que eu 
encontrei para o numero de nos eh aproximadamente o raio aureo phi, como era 
de se esperar, ja que ha uma relacao entre as duas sequencias.
 

 
Outra coisa esquisita dos exercicios da mesma pagina:
 

 
Definicao: A divide and conquer tree of N nodes is a binary tree with a root 
labeled N, a divide and conquer tree of floor(N/2) nodes in one subtree and 
a divide and conquer tree of ceil(N/2) nodes in the other subtree.
 

 
DCT = divide and conquer tree
 

 
Bom, o que eh uma DCT com N = 1? Seria uma arvore binaria com uma DCT como 
subarvore esquerda, com N = 0, pois floor(1/2) = 0, e uma DCT como subarvore 
direita, com N = 1, pois ceil(1/2) = 1. Isso seria, no minimo, uma arvore 
infinita, certo? ;)
 

 
Falta a base da recursao, eu acho... Mas e ai? Nao consegui definir uma base 
plausivel... Por exemplo, nao consigo montar uma dessas arvores com N = 2, 
de jeito nenhum... Ja inclusive tentei ver N como o numero de nos internos 
apenas, mas mesmo assim...
 

 
[]'s
 
Fernando 

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