Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Liczby Fibonacciego

SPIS TREŚCI
Podrozdziały

Problem

Należy obliczyć 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:

F 0 = 0
F 1 = 1
F i  = F i-2 + F i-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 1

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 ( 2 n  ). Dla dużych n czas obliczeń może sięgać miliardów ... miliardów tysiącleci.

Algorytm generacji liczb Fibonacciego metodą rekurencyjną

Wejście:

n  –   numer liczby ciągu Fibonacciego do wyliczenia, nN.

Wyjście:

n-ta liczba ciągu Fibonacciego.

Lista kroków funkcji Fibo ( n  )

K01: Jeśli n  ≤ 1,
to zakończ z wynikiem n
f 0  lub f 1
K02: Zakończ z wynikiem:
    Fibo ( n  - 2 ) = Fibo ( n  - 1 )
dwa wywołania rekurencyjne

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

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.
Pascal
// Liczby Fibonacciego
// Data:   20.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program fibnum;

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.
C++
// Liczby Fibonacciego
// Data:   20.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#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;
}
Basic
' Liczby Fibonacciego
' Data:   20.04.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Function fibo ( Byval n As Integer ) As Ulongint
  If n <= 1 Then fibo = n: Else fibo = fibo ( n - 2 ) + fibo ( n - 1 )
End Function

Dim n As Integer

Open Cons For Input As #1

Input n

Close #1

Print fibo ( n )
Print

End
Wynik:
25
75025
Na początek:  podrozdziału   strony 

Rozwiązanie 2

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  ). Jeszcze lepsze rozwiązanie podajemy w rozdziale dotyczącym potęgowania macierzy.

Algorytm generacji liczb Fibonacciego metodą iteracyjną

Wejście:

n  –   numer liczby ciągu Fibonacciego do wyliczenia, nN.

Wyjście:

n-ta liczba ciągu Fibonacciego.

Zmienne pomocnicze:

f 0, f 1, f  –  kolejne trzy liczby Fibonacciego, f 0, f 1, fC.

Lista kroków:

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

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

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.
Pascal
// Liczby Fibonacciego
// Data:   21.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program fibnum;

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.
   C++
// Liczby Fibonacciego
// Data:   21.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#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;
}
   Basic
' Liczby Fibonacciego
' Data:   21.04.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

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
  End If
Next
Print f
End
Wynik:
93
12200160415121876738
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.