FIBONACCIHO ČÍSLA
Posloupnost 0,1,1,2,3,5,8,13,21,34,..., ve které je každý člen sumou předcházejících dvou členů, objevil v roce 1202 italský matematik Leonardo Pisano (Leonardo z Pisy), kterého nazývali také Leonardo Fibonacci (Filius Bonacci, tj. syn Bonacciův). Fibonacciho čísla jsou definována vztahem:
F0=0;F1=1;...;FN=FN-1+FN-2 pro N>=2
Nejprve uvedu efektivní algoritmus (viz Technika: Odstranění rekurze) pro nalezení N-tého Fibonacciho čísla.
FIB: procedure
parse arg N
if N = 0 | N = 1 then return N
A = 0; B = 1
do N - 1
parse value(B (B + A)) with A B
end
return B
|
Nejhorší případ při výpočtu největšího společného dělitele pomocí Euklidova algoritmu nastane, když parametry A a B jsou dvě po sobě následující Fibonacciho čísla. Pro testování této vlastnosti je výhodné upravit funkci FIB tak, aby vracela právě ony dvě po sobě následující Fibonacciho čísla. Toho dosáhneme jednoduchou úpravou posledního příkazu na return B A. Volání funkce FIB(N) bude vracet N-té a ( N-1)-ní Fibonacciho číslo.
V 9. kapitole své knihy Systematisches Programmieren (slovenský překlad Systematické programovanie, Alfa Bratislava, 1981) uvádí N. Wirth vzorec pro explicitní vyjádření N-tého Fibonacciho čísla. Použijeme jej ve funkci GENERAL_FIB.
GENERAL_FIB: procedure
parse arg N, P
if N = 1 then return 1
Sqrt5 = SQRT(5, P); C = (1 + Sqrt5) / 2
return FORMAT(C ** N / Sqrt5,,0)
|
Program FIB počítá N-té Fibonacciho číslo, pro
N=10000 a P=2100 celkem 8.34 sekund, zatímco program GENERAL_FIB potřebuje 63.39 sekund. Je zajímavé, že příliš nepomůže ani předvypočítat hodnotu SQRT(5,2100) a vytvořit funkci SQRT5 vracející jen tuto hodnotu. GENERAL_FIB počítá 26.47 sekund.
SOUVISLOSTI
|
