Algorítmo com formula de fibonacci

[guilhermek 0]

Boa tarde pessoal, estou com uma enorme dúvida com um problema que preciso resolver para a faculdade, o exercício é o seguinte:

 

20.) Elabore um algoritmo para mostrar a seqüência dos N primeiro números da série de Fibonacci:

 

1 1 2 3 5 8 13 21 34 55 89 ....

 

Sempre o próximo elemento é a soma dos dois anteriores, assim será: 144

 

 

como devo proceder, qual seria a forma, ou o jeito de se fazer este programa em C++, ja procurei na net mais nao entendi muito bem, alguem ai sabe como proceder neste problema??

 

 

att Guilherme

[_Isis_ 202]

O que você não entendeu? A geração da sequência é somar os dois números anteriores.

Dá p/ usar recursão, que é o pior jeito de fazer; usar um algoritmo iterativo ou direto usando um resultado encontrado por Binet, que envolve potenciação a n.

[IME-Renato 0]

segue por recorrencia em C :

int Fibo(int x){
	int resposta;
	switch(x){
	case 1:
		return 1;
		break;
	case 2:
		return 1;
		break;[
	default:
		resposta = Fibo(x-1)+Fibo(x-2);
		return resposta;

	}

}

ou entao você aplica a formula para demosntrala vai um certo conhecimento de recorrencia mas vou tentar mostra-la

F_n = F_n-1 + F_n-2

considere a equaçao:

X² = X + 1

onde: x₁ e x₂ sao as raizes temos que o termo geral da sequencia é dado por

F_n = Ax₁ⁿ + Bx₂ⁿ onde A e B sao constantes para descobrilas bas calculas F₁

[_Isis_ 202]

Recursão é o pior jeito de se calcular Fibonacci. você vai reduzir tudo a somas de 1, o que não é muito esperto de se fazer.

 

Resultado de Binet = [(1+sqrt(5))ⁿ - (1-sqrt(5))ⁿ] / 2ⁿ sqrt(5)

 

Também dá p/ calcular usando a razão áurea (conforme a sequência progride, a razão entre os termos se aproxima disso): rint( aur ⁿ / sqrt(5)) , com aur sendo a razão áurea (1 + sqrt(5))*1/2.