Liczby Fibonacciego

Liczby Fibonacciego

Problem

Wyznaczyć n-ty wyraz ciągu Fibonacciego.

 

 

Leonardo Fibonacci był włoskim matematykiem żyjącym w latach od 1175 do 1250. Jest on autorem specyficznego ciągu liczbowego, który pojawia się w wielu zastosowaniach informatycznych (i nie tylko). Wyrazy ciągu Fibonacciego definiujemy rekurencyjnie w sposób następujący:

 

f0 = 0
f1 = 1
fi = fi-2 + fi-1, dla i > 1

 

Oto kilka pierwszych wyrazów ciągu Fibonacciego:

 

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

 

Rozwiązanie pierwsze

Rozwiązanie opieramy bezpośrednio na definicji wykorzystując wywołania rekurencyjne. Jest to bardzo złe rozwiązanie (podajemy je tylko ze względów dydaktycznych), ponieważ algorytm wielokrotnie oblicza wyrazy ciągu, co w efekcie prowadzi do wykładniczej klasy złożoności obliczeniowej O(2n). Dla dużych n czas obliczeń może sięgać miliardów ... miliardów tysiącleci.

 

037 Algorytm generacji liczb Fibonacciego metodą rekurencyjną

Wejście
n  -   numer liczby ciągu Fibonacciego do wyliczenia, n ∈N
Wyjście:

n-ta liczba ciągu Fibonacciego

Lista kroków funkcji Fibo(n)
K01: Jeśli n ≤ 1, to zwróć n i zakończ ; f0 lub f1
K02: Zwróć Fibo(n - 2) + Fibo(n - 1) i zakończ ; dwa wywołania rekurencyjne

 

Program 041

 

W pierwszym wierszu program odczytuje n - numer liczby Fibonacciego do wyliczenia. W następnym wierszu program wypisuje wartość n-tej liczby Fibonacciego. Z uwagi na wykładniczą klasę złożoności obliczeniowej czas obliczeń szybko rośnie, zatem nie podawaj zbyt dużych n (<45), inaczej nie doczekasz się wyniku lub komputer zgłosi przepełnienie pamięci.

 

Free Pascal Dev-C++

// Liczby Fibonacciego

program prg;

function fibo(n : integer) : longword;

begin

if n <= 1 then fibo := n

else fibo := fibo(n - 2) + fibo(n - 1);

end;

var n : integer;

begin

readln(n);

writeln(fibo(n));

writeln;

end.

// Liczby Fibonacciego

#include <iostream>

using namespace std;

unsigned long fibo(int n)

{

if(n <= 1) return n;

else return fibo(n - 2) + fibo(n - 1);

}

int main()

{

int n;

cin >> n;

cout << fibo(n) << "\n\n";

return 0;

}

 

Free Basic

' Liczby Fibonacciego

Declare Function fibo(Byval n As Integer) As Ulongint

Dim n As Integer

Input n

Print fibo(n)

Print

End

Function fibo(Byval n As Integer) As Ulongint

If n <= 1 Then fibo = n: Else fibo = fibo(n - 2) + fibo(n - 1)

End Function

 

Zawartość okna konsoli
25
75025

 

Rozwiązanie drugie

Poprzednie rozwiązanie jest bardzo proste. Niestety wywołania rekurencyjne powodują, iż komputer wielokrotnie oblicza te same liczby Fibonacciego. W ramach ćwiczeń proponuję dodać w wywołaniu funkcji Fibo() licznik, który zwiększa swój stan o 1 przy każdym wywołaniu. Na końcu programu, oprócz wartości Fibo(n), wyświetlamy również stan licznika - da nam to pojęcie o ilości wywołań rekurencyjnych.

Drugie rozwiązanie wykorzystuje zasadę programowania dynamicznego (ang. dynamic programming). Polega ona na tym, iż rozwiązanie wyższego poziomu obliczamy z rozwiązań otrzymanych na poziomie niższym, które odpowiednio zapamiętujemy. Dzięki temu podejściu program nie musi liczyć wszystkich składników od początku, wykorzystuje wyniki poprzednich obliczeń. W efekcie klasa złożoności obliczeniowej algorytmu spadnie do O(n).

 

038 Algorytm generacji liczb Fibonacciego metodą iteracyjną

Wejście
n  -   numer liczby ciągu Fibonacciego do wyliczenia, n ∈N
Wyjście:

n-ta liczba ciągu Fibonacciego

Lista kroków:
K01: f0 ← 0 ; pierwsza lub fi-2 liczba Fibonacciego
K02: f1 ← 1 ; druga lub fi-1 liczba Fibonacciego
K03: Dla i = 0,1,...,n: wykonuj K04...K08  
K04:     Jeśli i > 1, to idź do K06  
K05:     f ← i i następny obieg pętli K03  
K06:     f ← f0 + f1 ; obliczamy kolejną liczbę Fibonacciego
K07     f0 ← f1 ; zapamiętujemy wyniki obliczeń pośrednich
K08:     f1 ← f ; dla następnego obiegu pętli
K09: Pisz f  
K10: Koniec  

 

Program 042

 

Program odczytuje z pierwszego wiersza numer n liczby Fibonacciego, a w następnym wierszu wyświetla jej wartość. Z uwagi na ograniczony zakres liczb 64 bitowych, program wylicza dokładnie maksymalnie 93-cią liczbę ciągu Fibonacciego.

 

Free Pascal Dev-C++ Free Basic

// Liczby Fibonacciego

program prg;

var f,f0,f1 : qword;

i,n : integer;

begin

f0 := 0;

f1 := 1;

readln(n);

for i := 0 to n do

if i > 1 then

begin

f := f0 + f1;

f0 := f1;

f1 := f;

end

else f := i;

writeln(f);

end.

// Liczby Fibonacciego

#include <iostream>

using namespace std;

int main()

{

unsigned long long f,f0,f1;

int i,n;

f0 = 0;

f1 = 1;

cin >> n;

for(i = 0; i <= n; i++)

if(i > 1)

{

f = f0 + f1;

f0 = f1;

f1 = f;

}

else f = i;

cout << f << endl;

return 0;

}

' Liczby Fibonacciego

Dim As Ulongint f,f0,f1

Dim As Integer i,n

f0 = 0

f1 = 1

Input n

For i = 0 To n

If i > 1 Then

f = f0 + f1

f0 = f1

f1 = f

Else

f = i

Endif

Next

Print f

End

 

Zawartość okna konsoli
93
12200160415121876738

 

Rozwiązanie trzecie

Jeśli do wyliczania liczb Fibonacciego zastosujemy standardowe typy danych, to największą możliwą do wyznaczenia liczbą jest f93 = 12200160415121876738. Trzecie rozwiązanie przełamuje tę barierę umożliwiając dokładne wyliczenie w zasadzie dowolnej liczby ciągu Fibonacciego. W programie stosujemy własną procedurę dodawania opartą o znane reguły arytmetyki szkolnej. Liczby przechowywane są w postaci cyfr dziesiętnych w łańcuchach znakowych. Dzięki temu nie ma ograniczenia na długość przetwarzanych liczb (oczywiście w rozsądnych granicach - łańcuchy muszą się mieścić w pamięci). Program można w prosty sposób przerobić tak, aby generował kolejne liczby Fibonacciego do pliku na dysku twardym komputera.

 

Program 043

 

Program odczytuje z pierwszego wiersza numer n liczby Fibonacciego, a w następnym wierszu wyświetla jej wartość. Liczba n może być duża, np. 100000, lecz wtedy należy się liczyć z dosyć długim czasem obliczeń - ze względu na ilość cyfr algorytm posiada złożoność kwadratową.

 

Free Pascal Dev-C++

// Liczby Fibonacciego

program prg;

procedure Dodaj(var a,b,c : ANSIstring);

var

ia,ib,p,s : longword;

begin

ia := length(a); ib := length(b);

c := ''; p := 0;

repeat

s := 0;

if ia > 0 then

begin

s := ord(a[ia]) - 48; dec(ia);

end;

if ib > 0 then

begin

s := s + ord(b[ib]) - 48; dec(ib);

end;

s := s + p;

if s > 9 then

begin

p := 1; dec(s,10);

end

else p := 0;

c := char(s + 48) + c;

until (ia = 0) and (ib = 0) and (p = 0)

end;

var f,f0,f1 : ANSIstring;

n,i : longword;

begin

readln(n);

f0 := '0'; f1 := '1'; i := 0;

while i <= n do

begin

if i <= 1 then f := char(i + 48)

else

begin

Dodaj(f0,f1,f); f0 := f1; f1 := f;

end;

inc(i);

end;

writeln(f);

end.

// Liczby Fibonacciego

#include <iostream>

#include <string>

using namespace std;

void Dodaj(string &a, string &b, string &c)

{

int ia,ib,p,s;

ia = a.length()-1; ib = b.length()-1;

c = ""; p = 0;

do

{

s = 0;

if(ia >= 0) s = a[ia--] - 48;

if(ib >= 0) s += b[ib--] - 48;

s += p;

if(s > 9)

{

p = 1; s -= 10;

}

else p = 0;

c = (char)(s + 48) + c;

} while((ia >= 0) || (ib >= 0) || (p != 0));

}

int main()

{

string f,f0,f1;

int n,i;

cin >> n;

f0 = "0"; f1 = "1";

for(i = 0; i <= n; i++)

{

if(i <= 1) f = (char)(i + 48);

else

{

Dodaj(f0,f1,f); f0 = f1; f1 = f;

}

}

cout << f << endl;

return 0;

}

 

Free Basic

Declare Sub Dodaj(Byref a As String, Byref b As String, Byref c As String)

Dim As String f,f0,f1

Dim As Integer n,i

Input n

f0 = "0": f1 = "1"

For i = 0 To n

If i <= 1 Then

f = Chr(i + 48)

Else

Dodaj(f0,f1,f): f0 = f1: f1 = f

Endif

Next

Print f

End

Sub Dodaj(Byref a As String, Byref b As String, Byref c As String)

Dim As Uinteger ia,ib,p,s

ia = Len(a): ib = Len(b)

c = "": p = 0

Do

s = 0

If ia > 0 Then

s = Asc(a,ia) - 48: ia -= 1

Endif

If ib > 0 Then

s += Asc(b,ib) - 48: ib -= 1

Endif

s += p

If s > 9 Then

p = 1: s -= 10

Else

p = 0

Endif

c = Chr(s + 48) + c

Loop Until (ia = 0) And (ib = 0) And (p = 0)

End Sub

 

Zawartość okna konsoli
15555
28396125456162255684573971100001652636115436459474169151612267851750841247039122
02533022171447213419402574422126125831128174983433773172378455498428334260040144
95955110534959166114790813693617706031014379891390932954204247262494358878064566
65190643461209526899492742586519800542482868803405434648392601917132888018892315
44270121139273934445081552948666999404771407839116294586948584077543146010535513
26098060297969136252830722423448118263633711102241629720535932027338619654580179
94360625761381148076050563589532503559213869130970507490005674278030687195873318
86147619751145086431070363028596409881157775197432209754323814376188966148125553
83559880724437665436794350951548439966020787541576377582135828377285936125377387
73991735838565355804696823690357542922257550043432625370689751752007143699255847
56649968269341337913347084080506549838126247082330749946259676055134321045801819
97322475099516375267322297475688672975379668185474641963662430725789290949980909
92019655686800152733974465136083621907021525266920440675983476344441893280008801
75734127153190485965980120335904290353199060983405750117790077170859822589322130
38898456942656051723048759457551863822788978248578043706183504941996768368877537
11603196694175053370692959034805540186302987765218849093383014649510289650528618
79854042514712297106268565334855672048366636854279421836007386636374075016778180
60817458902011347747730120602683170051536315269306476866923781530265433651559737
25281734428435990296946064483907753779207519972621393680884311108944227703846370
15525074343019389684203380169751074380962739042318883714358521017644854561680871
64205726120173281908747956281167721162322209555044822232661887251068061626601910
32126706814786136335159297681076888054833753834854465906057746554831996475739884
03162402623334306790489724454360420619316771212011304930062483298095062911074104
57572705120182920183659431272254889621869768935822123171418171367813344437134990
86430356951684336147577187373962688584625441718958840362935729895153320538416698
00660462002411226813961950031836660112367095730045896908953988737224373437682587
15532346269977825724030722883112166468848982903650797899350331599711027777573601
35815714095284730120567780357380061534482522763565951571194468708524326066874949
84304002675813923345046796939359843116429219923048063988968761323637613379466523
21119449685328145849482976894655026268103128229258886431494804451410284095165643
29408998551105961559222669076706172225219714580869951496550489411835134305617035
17500304059910331237118646679814241987731741300470507430583222597326488569349519
53184432032704078397672920975463479295440677650204071339527120550874927952240514
77627115173128747845833424532516267164243654541797012504941120627230131472827174
85061215441360115655012108332466103080508972862764103259841193723080566469973083
91028022065303489934847000326182236777540186786058205938264898947632773198211153
47883772099339137775147835127600105962905748301440711348321877007238719713277259
93733881717434133446201285468683908292559729783795757625553915042396217993107942
60103484271230190675214190421260916656301649279824013200161897398822491368789184
27962351415105583588704766791601791433419387915517399523568516522488626623769460
931441793552937075794471741220370346795984392237570

Wyszukiwarka