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

©2024 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:

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 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 te same 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.

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 zakończ z wynikiem n ; f0 lub f1
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 If
End Function

Dim n As Integer

Open Cons For Input As #1
Input n
Close #1
Print fibo(n)
Print
End
Python (dodatek)
# Liczby Fibonacciego
# Data:   18.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------


def fibo(n):
    if n <= 1:
        return n
    else:
        return fibo(n-2)+fibo(n-1)


n = int(input())
print(fibo(n))
print()
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, n ∈ N.

Wyjście:

n-ta liczba ciągu Fibonacciego.

Elementy pomocnicze:

f0, f1, f : kolejne trzy liczby Fibonacciego, f0, f1, f ∈ C.

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 kroki 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: 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 (w Pythonie nie ma takiego ograniczenia).
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
Python (dodatek)
# Liczby Fibonacciego
# Data:   18.02.2024
# (C)2020 mgr Jerzy Wałaszek
# --------------------------

f0, f1, f = 0, 1, 1
n = int(input())
for i in range(n+1):
    if i > 1:
        f  = f0+f1
        f0 = f1
        f1 = f
    else:
        f = i
print(f)
Wynik: 
93
12200160415121876738
Wyniki (tylko Python): 
100
354224848179261915075

150
9969216677189303386214405760200

200
280571172992510140037611932413038677189525

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
©2024 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.