Algorytmy i Struktury Danych - Liczby Fibonacciego

Przypomnijmy, liczby Fibonacciego tworzą ciąg rekurencyjny:

F₀ = 0
F₁ = 1
F_n = F_n_-₂+F_n_-₁, 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:

1 1

1 0

ⁿ

	F_n+1	F_n
	F_n	F_n-1

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 (problem nie dotyczy języka Python).

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.

Elementy pomocnicze:

Q : macierz Q Fibonacciego o wymiarze 2×2; Q ∈ N.
P : macierz pomocnicza o wymiarze 2×2; P ∈ N.
W : macierz wyniku potęgowania o wymiarze 2×2; W ∈ N.

Lista kroków:

K01: Jeśli n < 2, ; dla n = 0, 1 liczba Fibonacciego ma wartość n
     to zakończ z wynikiem 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: ; w pętli obliczamy potęgę n-1 Q
     wykonuj kroki K06…K12
K06: Jeśli (n and 1) = 0, ; testujemy kolejne bity n
     to idź do kroku K09
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₀ do F₉₃. Kolejna liczba Fibonacciego F₉₄ wykracza już poza zakres 64 bitowych liczb całkowitych (nie dotyczy to języka Python, w którym liczby całkowite mogą być dowolnie duże). 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

Python (dodatek)

# Obliczanie liczb Fibonacciego
# za pomocą potęgowania macierzy
# Data: 15.04.2024
# (C)2024 mgr Jerzy Wałaszek
#-------------------------------


# Oblicza n-tą liczbę Fibonacciego
#---------------------------------
def fibo(n):
    if n < 2: return n
    # ustawiamy macierz Q
    q11, q12 = 1, 1
    q21, q22 = 1, 0
    # w macierzy W tworzymy macierz jednostkową
    w11, w12 = 1, 0
    w21, w22 = 0, 1
    n -= 1 # 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, w12 = p11, p12
           w21, w22 = p21, p22
       n >>= 1 # usuwamy z n sprawdzony bit
       if not 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, q12 = p11, p12
       q21, q22 = p21, p22
    return w11


# Program główny
#---------------

for i in range(341): # brak ograniczeń
    print("F(", i, ") = ", fibo(i), sep="")

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

do podrozdziału do strony

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.

Liczby Fibonacciego