Przed rozwiązaniem problemu ciągu fibonacciego opiszę czym właściwie jest ten ciąg liczb. W ciągu fibonacciego pierwsze dwa wyrazy to 0, 1 a następne są sumą dwóch poprzednich czyli 0, 1, 1, 2, 3, 5, 8, 13 itd. ciąg przedstawia się wzorem

dla:

Fib(0) = 0
Fib(1) =  1

Fib(n) = Fib(n-1) + Fib(n-2)

Ciąg fibonacciego został odkryty w 1202 roku przez Leonarda z Pizy, który zawarł go w swoim dziele Liber Abaci jako rozwiązanie problemu rozmnażania się królików.  Ciąg fibonacciego jest obecny w naturze, muzyce, sztuce oraz literaturze. Dlatego warto zastanowić się nad napisaniem programu, który wyliczy n wyraz tego ciągu.

Przykład implementacji w PHP

Ciąg fibbonaciego można zaimplementować używając techniki iteracyjnej lub rekursji(rekurencji). Osobiście wole rozwiązanie rekurencyjne, w którym piszemy mniej kodu, jednakże jest ono bardziej skomplikowane technicznie. Najprostszym rozwiązaniem problemu jest poniższa funkcja:

<?php
function fib($n)
{
   if($n == 0) return 0;
   else if ($n == 1) return 1;
   else
   {
      return fib($n-1) + fib($n-2);
   }
}

echo fib(1);
echo fib(2);
echo fib(3);
echo fib(4);
echo fib(5);

Powyższy kod wyświetli wyrazy ciągu fibbonaciego dla n > 0 i n < 6

Jak to działa?

funkcja jest wywoływana rekurencyjnie. W przypadku gdy n jest równe 0 zwracany jest wynik 0. Gdy n jest równe 1 zwracany jest wynik 1. W innym wypadku wykonywane są dwie funkcje fib(n-1) + fib(n-2) jest to wywołanie rekurencyjne o którym więcej przeczytasz tutaj. Złożoność tego rozwiązania jest wykładnicza dokładnie wynosi  O(2n). I nie jest to złożność, która nas satysfakcjonuje. Z uwagi na to, że funkcja fib() jest wywoływana wielokrotnie dla tych samych wartości, warto zapamiętać te wartości i gdy wartość już istnieje to ją zwrócić zamiast obliczać ją ponownie.

<?php

$memo = array(0, 1);

function fib($n, &$memo)
{
   if(!isset($memo[$n]))
   {
      $memo[$n] = fib($n-1, $memo) + fib($n-2, $memo);
   }
   return $memo[$n];
}

echo fib(1, $memo);
echo fib(2, $memo);
echo fib(3, $memo);
echo fib(4, $memo);
echo fib(5, $memo);

Użycie tablicy $memo znacząco przyspiesza wywołanie funkcji fib() , w takim przypadku złożoność spada do iteracyjnej czyli O(n). Rozwiązanie to można jeszcze przyspieszyć używając mnożenia macierzy.

<?php

function fib($n)
{
  $q11 = $q12 = $q21 = $q22 = 0; // macierz Q
  $p11 = $p12 = $p21 = $p22 = 0; // macierz P
  $w11 = $w12 = $w21 = $w22 = 0; // macierz W

  if($n < 2) return $n;

  //macierz Q

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

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

  $n--;   

  while($n)
  {
     if($n & 1)
     {
       //P = W x Q

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

       //W = P

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

     $n >>= 1;

     if(!$n) break;

     //P = Q x Q

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

     // Q = p

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

  }

  return $w11;
}

Złożoność tego rozwiązania jest mniejsza niż iteracyjna i wynosi 0(log(n)). Spróbujcie zastosować 3 różne funkcje dla liczb większych od 9 i zobaczycie na przykładzie tych rozwiązań jak jakość kodu wykonującego takie samo zadanie, może mieć znaczenie dla szybkości działania aplikacji.

więcej na temat rozwiązania za pomocą mnożenia macierzy możecie znaleźć tutaj