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
Tematy pomocnicze

Problem

Należy wyznaczyć szybko n-tą liczbę ciągu liczbowego Fibonacciego

Rozwiazanie

Przypomnijmy, liczby Fibonacciego tworzą ciąg rekurencyjny:

F 0 = 0
F 1 = 1
F n = F n-2 + F n-1, dla n > 1.

Ciąg ten jest następujący:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 ...

Za wyjątkiem pierwszych dwóch każda kolejna liczba Fibonacciego powstaje jako suma dwóch poprzednich. Liczby te posiadają dosyć duże znaczenie w różnych dziedzinach nauki, również w informatyce. Algorytm rekurencyjny obliczania liczb Fibonacciego posiada wykładniczą klasę złożoności obliczeniowej i nie nadaje się do poważniejszych zastosowań. Algorytm wykorzystujący programowanie dynamiczne ma już liniową klasę złożoności obliczeniowej. Zachodzi pytanie, czy nie istnieje lepszy sposób wyznaczania wartości tych liczb. Otóż istnieje i wykorzystuje potęgowanie macierzy. Korzystamy tutaj ze wzoru:

Ze wzoru wynika, iż podniesienie lewej macierzy do potęgi n-tej daje nam macierz, której wyrazy są liczbami Fibonacciego. Macierz po lewej stronie równania jest oznaczana zwykle literą Q i nosi nazwę macierzy Q Fibonacciego ( ang. Fibonacci Q-matrix ). Ponieważ macierz możemy podnieść do n-tej potęgi przy złożoności obliczeniowej O ( log n  ), to również z taką samą złożonością możemy wyliczyć n-tą liczbę Fibonacciego. Praktycznie macierz wystarczy podnieść do potęgi n - 1, wtedy w pierwszym wierszu i pierwszej kolumnie otrzymamy poszukiwaną n-tą liczbę Fibonacciego. Oczywiście ten sposób obliczania liczb Fibonacciego sprawdza się dla dużych n. Jednakże musisz pamiętać, że liczby Fibonacciego rosną szybko i standardowe typy danych mogą nie wystarczyć do przechowania ich wartości.

Algorytm obliczania n-tej liczby Fibonacciego za pomocą szybkiego potęgowania macierzy Q

Wejście:

n  –  numer liczby Fibonacciego do obliczenia, n  ∈ N

Wyjście:

F n  –  wartość n-tej liczby Fibonacciego, F n  ∈ N

Zmienne pomocnicze:

Q  –  macierz Q Fibonacciego o wymiarze 2 x 2, Q  ∈ N
P  –  macierz pomocnicza o wymiarze 2 x 2, P  ∈ N
W  – macierz wyniku potęgowania o wymiarze 2 x 2, W  ∈ N

Lista kroków:

K01: Jeśli n  < 2,
to zakończ z wynikiem
n
dla n = 0, 1 liczba Fibonacciego ma wartość n
K02: Ustaw macierz Q  
K03: Ustaw macierz jednostkową w W  
K04: n  ← n  - 1 potrzebujemy potęgę n-1 macierzy Q
K05: Dopóki n  > 0,
wykonuj kroki K06...K12
w pętli obliczamy potęgę n-1 Q
K06:     Jeśli ( n  and 1 ) = 0,
    to idź do kroku K09
testujemy kolejne bity n
K07     P  ← W  × Q jeśli bit jest ustawiony, to do W dołączamy Q
K08:     W  ← P  
K09     n  ← n shr 1 przesuwamy w prawo bity n
K10     Jeśli n  = 0,
    to idź do kroku K13
 
K11:     P  ← Q  × Q wyznaczamy kolejny kwadrat Q
K12     Q  ← P  
K13: Zakończ z wynikiem W [ 1, 1 ]  

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 wyświetla liczby Fibonacciego od F 0 do F 93. Kolejna liczba Fibonacciego F 94 wykracza już poza zakres 64 bitowych liczb całkowitych. Ze względu na nieduży rozmiar macierzy Q, P i W nie tworzyliśmy dla nich tablic dwuwymiarowych. Również obliczenia są przeprowadzane bezpośrednio na elementach macierzy bez korzystania z pętli, co przyspiesza działanie programu.
Pascal
// Obliczanie liczb Fibonacciego za pomocą potęgowania macierzy
// Data: 19.02.2012
// (C)2020 mgr Jerzy Wałaszek
//-------------------------------------------------------------

program fib_matrix;

// Oblicza n-tą liczbę Fibonacciego
//---------------------------------
function fibo ( n : integer ) : qword;
var
  q11, q12, q21, q22 : qword; // macierz Q
  p11, p12, p21, p22 : qword; // macierz P
  w11, w12, w21, w22 : qword; // macierz W
begin
  if n < 2 then  fibo := n
  else
  begin

    // ustawiamy macierz Q

    q11 := 1; q12 := 1;
    q21 := 1; q22 := 0;

    // w macierzy W tworzymy macierz jednostkową

    w11 := 1; w12 := 0;
    w21 := 0; w22 := 1;

    dec ( n );      // będzie nam potrzebna n-1 potęga Q

    while n > 0 do
    begin

      if( n and 1 ) = 1 then
      begin

        // wykonujemy mnożenie P = W x Q

        p11 := w11*q11 + w12 * q21; p12 := w11*q12 + w12 * q22;
        p21 := w21*q11 + w22 * q21; p22 := w21*q12 + w22 * q22;

        // wynik przenosimy: W = P

        w11 := p11; w12 := p12;
        w21 := p21; w22 := p22;

      end;

      n := n shr 1;    // usuwamy z n sprawdzony bit

      if n = 0 then break;

      // podnosimy Q do kwadratu:  P = Q x Q

      p11 := q11*q11 + q12 * q21; p12 := q11*q12 + q12 * q22;
      p21 := q21*q11 + q22 * q21; p22 := q21*q12 + q22 * q22;

      // wynik przenosimy: Q = p

      q11 := p11; q12 := p12;
      q21 := p21; q22 := p22;

    end;

    fibo := w11;

  end;

end;

// Program główny
//---------------

var
  i : integer;

begin
  for i := 0 to 93 do writeln ( 'F ( ', i, ' ) = ', fibo ( i ) );
end.
C++
// Obliczanie liczb Fibonacciego za pomocą potęgowania macierzy
// Data: 19.02.2012
// (C)2020 mgr Jerzy Wałaszek
//-------------------------------------------------------------

#include <iostream>

using namespace std;

// Oblicza n-tą liczbę Fibonacciego
//---------------------------------
unsigned long long fibo ( int n )
{
  unsigned long long q11, q12, q21, q22, // macierz Q
                     p11, p12, p21, p22, // macierz P
                     w11, w12, w21, w22; // macierz W

  if( n < 2 ) return n;

  // ustawiamy macierz Q

  q11 = q12 = q21 = 1;
  q22 = 0;

  // w macierzy W tworzymy macierz jednostkową

  w11 = w22 = 1;
  w12 = w21 = 0;

  n--;      // będzie nam potrzebna n-1 potęga Q

  while( n )
  {
     if( n & 1 )
     {
       // wykonujemy mnożenie P = W x Q

       p11 = w11*q11 + w12 * q21; p12 = w11*q12 + w12 * q22;
       p21 = w21*q11 + w22 * q21; p22 = w21*q12 + w22 * q22;

       // wynik przenosimy: W = P

       w11 = p11; w12 = p12;
       w21 = p21; w22 = p22;

     }

     n >>= 1;    // usuwamy z n sprawdzony bit

     if( !n ) break;

     // podnosimy Q do kwadratu:  P = Q x Q

     p11 = q11*q11 + q12 * q21; p12 = q11*q12 + q12 * q22;
     p21 = q21*q11 + q22 * q21; p22 = q21*q12 + q22 * q22;

     // wynik przenosimy: Q = p

     q11 = p11; q12 = p12;
     q21 = p21; q22 = p22;

  }

  return w11;
}

// Program główny
//---------------

int main( )
{
  for( int i = 0; i < 94; i++ ) cout << "F ( " << i << " ) = " << fibo ( i ) << endl;
  return 0;
}
Basic
' Obliczanie liczb Fibonacciego za pomocą potęgowania macierzy
' Data: 19.02.2012
' (C)2020 mgr Jerzy Wałaszek
'-------------------------------------------------------------

' Oblicza n-tą liczbę Fibonacciego
'---------------------------------
Function fibo ( n As Integer ) As ULongInt

  Dim As Ulongint q11, q12, q21, q22, _ ' macierz Q
                  p11, p12, p21, p22, _ ' macierz P
                  w11, w12, w21, w22   ' macierz W

  If n < 2 Then Return n

  ' ustawiamy macierz Q

  q11 = 1: q12 = 1
  q21 = 1: q22 = 0

  ' w macierzy W tworzymy macierz jednostkową

  w11 = 1: w12 = 0 
  w21 = 0: w22 = 1 

  n -= 1      ' będzie nam potrzebna n-1 potęga Q

  While n 
    if( n And 1 ) = 1 Then

       ' wykonujemy mnożenie P = W x Q

       p11 = w11*q11 + w12 * q21: p12 = w11*q12 + w12 * q22
       p21 = w21*q11 + w22 * q21: p22 = w21*q12 + w22 * q22

       ' wynik przenosimy: W = P

       w11 = p11: w12 = p12
       w21 = p21: w22 = p22

    End If

    n Shr= 1    ' usuwamy z n sprawdzony bit

    If n = 0 then Exit While

    ' podnosimy Q do kwadratu:  P = Q x Q

    p11 = q11*q11 + q12 * q21: p12 = q11*q12 + q12 * q22
    p21 = q21*q11 + q22 * q21: p22 = q21*q12 + q22 * q22

    ' wynik przenosimy: Q = p

    q11 = p11: q12 = p12
    q21 = p21: q22 = p22

  Wend

  fibo = w11
End Function

' Program główny
'---------------

Dim i As Integer

For i = 0 To 93
  Print "F ( ";i;" ) = ";fibo ( i )
Next

End
Wynik:
F ( 0 ) = 0
F ( 1 ) = 1
F ( 2 ) = 1
F ( 3 ) = 2
F ( 4 ) = 3
F ( 5 ) = 5
F ( 6 ) = 8
F ( 7 ) = 13
F ( 8 ) = 21
F ( 9 ) = 34
F ( 10 ) = 55
F ( 11 ) = 89
F ( 12 ) = 144
F ( 13 ) = 233
F ( 14 ) = 377
F ( 15 ) = 610
F ( 16 ) = 987
F ( 17 ) = 1597
F ( 18 ) = 2584
F ( 19 ) = 4181
F ( 20 ) = 6765
F ( 21 ) = 10946
F ( 22 ) = 17711
F ( 23 ) = 28657
F ( 24 ) = 46368
F ( 25 ) = 75025
F ( 26 ) = 121393
F ( 27 ) = 196418
F ( 28 ) = 317811
F ( 29 ) = 514229
F ( 30 ) = 832040
F ( 31 ) = 1346269
F ( 32 ) = 2178309
F ( 33 ) = 3524578
F ( 34 ) = 5702887
F ( 35 ) = 9227465
F ( 36 ) = 14930352
F ( 37 ) = 24157817
F ( 38 ) = 39088169
F ( 39 ) = 63245986
F ( 40 ) = 102334155
F ( 41 ) = 165580141
F ( 42 ) = 267914296
F ( 43 ) = 433494437
F ( 44 ) = 701408733
F ( 45 ) = 1134903170
F ( 46 ) = 1836311903
F ( 47 ) = 2971215073
F ( 48 ) = 4807526976
F ( 49 ) = 7778742049
F ( 50 ) = 12586269025
F ( 51 ) = 20365011074
F ( 52 ) = 32951280099
F ( 53 ) = 53316291173
F ( 54 ) = 86267571272
F ( 55 ) = 139583862445
F ( 56 ) = 225851433717
F ( 57 ) = 365435296162
F ( 58 ) = 591286729879
F ( 59 ) = 956722026041
F ( 60 ) = 1548008755920
F ( 61 ) = 2504730781961
F ( 62 ) = 4052739537881
F ( 63 ) = 6557470319842
F ( 64 ) = 10610209857723
F ( 65 ) = 17167680177565
F ( 66 ) = 27777890035288
F ( 67 ) = 44945570212853
F ( 68 ) = 72723460248141
F ( 69 ) = 117669030460994
F ( 70 ) = 190392490709135
F ( 71 ) = 308061521170129
F ( 72 ) = 498454011879264
F ( 73 ) = 806515533049393
F ( 74 ) = 1304969544928657
F ( 75 ) = 2111485077978050
F ( 76 ) = 3416454622906707
F ( 77 ) = 5527939700884757
F ( 78 ) = 8944394323791464
F ( 79 ) = 14472334024676221
F ( 80 ) = 23416728348467685
F ( 81 ) = 37889062373143906
F ( 82 ) = 61305790721611591
F ( 83 ) = 99194853094755497
F ( 84 ) = 160500643816367088
F ( 85 ) = 259695496911122585
F ( 86 ) = 420206140727489673
F ( 87 ) = 679891637638612258
F ( 88 ) = 1100087778366101931
F ( 89 ) = 1779979416004714189
F ( 90 ) = 2880067194370816120
F ( 91 ) = 4660046610375530309
F ( 92 ) = 7540113804746346429
F ( 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.