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

Problem

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

Rozwiazanie

Przypomnijmy, liczby Fibonacciego tworzą ciąg rekurencyjny:

F0 = 0
F1 = 1
Fn = Fn-2 + Fn-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:

 
1 1
1 0
 
   
n =
 
Fn+1
Fn
 
 
Fn
Fn-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:

Fn : wartość n-tej liczby Fibonacciego; Fn ∈ N.

Elementy 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, ; 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: nn-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: WP
K09: nn shr 1 ; przesuwamy w prawo bity n
K10: Jeśli n = 0,
     to idź do kroku K13
K11: PQ×Q ; wyznaczamy kolejny kwadrat Q
K12: QP
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 F0 do F93. Kolejna liczba Fibonacciego F94 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

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.