Witam, potrzebuję pomocy z przyśpieszeniem algorytmu, chodzi o wyznaczanie liczby z ciągu fibonacciego z przedziału 0<n<100000.
Zrobiłem to na stringach i później każdą pojedyńczą "litere" zamieniałem na cyfrę i dodawałem. Działa, tylko że nie w takim czasie jaki mi potrzeba. Co można by zmienić? Sam algorytm wyznaczania tej liczby? (macierz na przykład) czy bardziej chodzi o sam kod?
Kod próbowałem zrobić na klasach i pogmatwałem przy tej zmiennej "wynik", ale mam to samo również w funkcjach normalnych.
#include <iostream>
#define Znak(b) (char(b+48))
#define Cyfra(a) (int(a-48))
using namespace std;
class Fib
{
string wartosc="";
string wynik="";
public:
Fib (string w): wartosc(w) {};
void wyswietl()
{
cout<<wartosc<<endl;
}
void dlugosc()
{
cout<<this->wartosc.length()<<endl;
}
Fib operator+(Fib &l)
{
int i;
int Pomocnicza = 0;
while( (this->wartosc).length() != (l.wartosc).length() )
{
if( (this->wartosc).length() > (l.wartosc).length() )
{
l.wartosc = "0" + l.wartosc;
}
else this->wartosc = "0" + this->wartosc;
}
int Pom;
for(i = ((this->wartosc).length())-1; i >= 0; i-- )
{
Pom = Cyfra((this->wartosc)[i]) + Cyfra((l.wartosc)[i]) + Pomocnicza;
wynik = Znak( Pom % 10 ) + wynik;
Pomocnicza = (Pom/10);
}
if( Pomocnicza != 0 ) wynik = Znak( Pomocnicza ) + wynik;
return Fib(wynik);
}
};
int main()
{
Fib f0("0");
Fib f1("1");
Fib fn("0");
int i,N;
cin>>N;
if( N < 2 )
{
if( N == 0 ) fn = f0;
else fn = f1;
}
else
{
for( i = 2; i <= N; i++ )
{
fn = f1+f0;
f0 = f1;
f1 = fn;
}
}
fn.wyswietl();
}