Algoritmo da Sequência de Fibonacci

Esta sequência de números criada pelo italiano Fibonacci (ou Leonardo de Pisa, como era seu nome usual) é bem engraçada, pois ela representa várias coisas em termos da natureza, anatomia humana e geometria. Os antigos indianos e incas já conheciam esta sequencia, e as usavam principalmente na arquitetura e agricultura.

O termo de determinada posição será sempre a soma dos dois termos anteriores, portanto seguimos para ela a seguinte fórmula:

Os dois primeiros elementos serão sempre 0 e 1, e a partir daí a fórmula é aplicada:

Se considerarmos esta sequencia como uma equacao algébrica, veremos que ela possui sempre uma única solução que consiste na fórmula de Binet.

Este é conhecido como a proporção áurea, e está presente em diversas coisas. No pentagrama, na disposição das sementes de girassol, no número de folhas das árvores, no crescimento das populações de abelha, nas notas musicais das sinfonias, no DNA e no corpo humano nas seguintes medidas fornecidas por Leonardo da Vinci.

• A altura do corpo humano e a medida do umbigo até o chão;
• A altura do crânio e a medida da mandíbula até o alto da cabeça;
• A medida da cintura até a cabeça e o tamanho do tórax;
• A medida do ombro à ponta do dedo e a medida do cotovelo à ponta do dedo;
• O tamanho dos dedos e a medida da dobra central até a ponta;
• A medida da dobra central até a ponta dividido e da segunda dobra até a ponta;
• A medida do seu quadril ao chão e a medida do seu joelho até ao chão;
• A medida do cotovelo até o pulso e a medida do seu pé.

O seguinte algoritmo em Pascal calcula quantos termos da sequencia de Fibonacci forem pedidos.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

program fibonacci (input,output);
 
var
	i,n,ni,ni1,ni2:longint;
 
begin
 
	write('Quantos termos de Fibonacci você quer calcular? ');
	read(n);
	ni:=1;
	ni1:=1;
	ni2:=0;
 
	for i:=1 to n do
		begin
			write(ni,' ');
			ni:=ni1+ni2;
			ni2:=ni1;
			ni1:=ni;
		end;
 
end.

Devido a um overflow, este algoritmo só funciona até o termo 47:

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903