Série de Fibonacci

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

[ Hits: 6.015 ]

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

Caixa de Supermecado Versao 1

fibonacci

C --> Calculadora de equações de 2º grau explicada.

Bits trocados

Cálculo de Determinantes


  

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