Liczby Fibonacciego


Tematy pokrewne   Podrozdziały
Przedziały liczbowe i liczby
Liczby parzyste i nieparzyste
Liczby podzielne lub niepodzielne przez zadane podzielniki
Ciągi arytmetyczne
NWD – algorytm Euklidesa
Liczby względnie pierwsze
Najmniejsza wspólna wielokrotność
Odwrotność modulo – rozszerzony algorytm Euklidesa
Liczby pierwsze – generacja przez sprawdzanie podzielności
Liczby pierwsze – generacja sitem Eratostenesa
Liczby pierwsze – generacja sitem liniowym
Liczby pierwsze – generacja sitem Atkina-Bernsteina
Czynniki pierwsze – metoda próbnych dzieleń
Czynniki pierwsze – metoda Fermata
Pierwszość liczby naturalnej – algorytmy naiwne
Pierwszość liczby naturalnej – Chiński Test Pierwszości
Pierwszość liczby naturalnej – Małe Twierdzenie Fermata
Pierwszość liczby naturalnej – test Millera-Rabina
Liniowe generatory liczb pseudolosowych
Generator pseudolosowy Park-Miller
Generator pseudolosowy Mersenne Twister
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Liczby Fibonacciego
System liczbowy Fibonacciego
Całkowity pierwiastek kwadratowy
Potęgowanie macierzy a liczby Fibonacciego
  Rozwiązanie 1
Rozwiązanie 2

 

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.

 

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

Ważne:

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.

 

Lazarus
// Liczby Fibonacciego
// Data:   20.04.2008
// (C)2012 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.
Code::Blocks
// Liczby Fibonacciego
// Data:   20.04.2008
// (C)2012 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;
}
Free Basic
' Liczby Fibonacciego
' Data:   20.04.2008
' (C)2012 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

 

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). 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 K04...K08  
K04:     Jeśli i > 1, to idź do K06  
K05:     fi i następny obieg pętli K03  
K06:     ff0 + f1 ; obliczamy kolejną liczbę Fibonacciego
K07     f0f1 ; zapamiętujemy wyniki obliczeń pośrednich
K08:     f1f ; dla następnego obiegu pętli
K09: Pisz f  
K10: Zakończ  

 

Program

Ważne:

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.

 

Lazarus Code::Blocks Free Basic
// Liczby Fibonacciego
// Data:   21.04.2008
// (C)2012 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.
// Liczby Fibonacciego
// Data:   21.04.2008
// (C)2012 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;
}
' Liczby Fibonacciego
' Data:   21.04.2008
' (C)2012 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
 

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.