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
Dokładnie przejrzawszy wasz materiał stwierdzam iż jest on wysoko dla doświadczonych programistów kończących podstawówkę, myślę że
Jakieś sugestie? Staram się pisać na różnym poziomie, zarówno dla doświadczonych programistów jak i dla tych początkujących. Może niedługo napiszę coś o Redis/ElasticSearch albo np React.js, socket.io zastanawiam się nad tematami.