Série de Fibonacci

Publicado por Oberlan C. Romão (última atualização em 29/05/2010)

[ Hits: 6.016 ]

Homepage: http://twitter.com/oberlan

Download fib.cpp




Um dos grandes problemas de quem participa de algum campeonato de programação e tem que fazer o programa gerar respostas rápidas é fazer a série de Fibonacci de forma eficiente. Pensando nisso resolvi apresentar uma solução.

O programa usa programação dinâmica, ou seja, ele vai armazenado as soluções que são encontradas, o que acelera o calculo da série.

  



Esconder código-fonte

#include <iostream>

#define ll long long

#define MAX 200

using namespace std;

ll tab[MAX];

void ini_fibo(){
    for(int i=0; i<MAX; ++i)
        tab[i] = -1;

    tab[0] = 0;
    tab[1] = 1;
}

ll fibo(ll n){
    if(tab[n] != -1) return tab[n];
    ll i = 2;
    for(; i<=n; ++i)
        if(tab[i] == -1) break;

    for(; i<=n; ++i)
        tab[i] = tab[i-1] + tab[i-2];
    return tab[n];
}

int main(){
    ll n;

    cin >> n;
    ini_fibo();
    while (n){
        cout << "Fibonacci(" << n << ") = " << fibo(n) << endl;
        cin >> n;
    }

    return 0;
}






Scripts recomendados

Tabuada em C

Média do aluno

Crescimento populacional brasileiro

Convertendo dias para anos.

Diária Hotel


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts