1. možnosť
(klasické riešenie).
Klasické rekurzívne riešenie vychádza priamo zo zadania
úlohy.
2. možnosť (efektívnejšia verzia).
Použije sa viacero funkcií a pomocný parameter.
V našom prípade sme
zvolili pomocný parameter v ktorom budeme ukladať vždy už
vypočítané výsledky funkcie fib, aby sme ich
mohli v prípade potreby znova použiť a nemuseli ich znovu
počítať. Tak budeme počítať každú fib(x)
pre dané x len raz.
Parameter má formát ((x1 hodnota1)(x2 hodnota2)...(xn
hodnotan)), pričom vždy platí hodnota=fib(x).
Pri našej imlementacií 2., sme okrem hlavnej funkcie (fib)
použili funkciu na vyhľadávanie (isin),
funciu na vlastné generovanie zoznamu výsledkov (zfib)
a funkciu na pridanie nového prvku (novy),
ktorá predpokladá, že všetky ostatné potrebné prvky sú už
v aktuálnom zozname azoz.
(Fib používa isin a zfib,
zfib používa novy a isin,
novy používa isin.)
; Implementácia: 1 možnosť (klasické riešenie).
(defun fib (n)
(cond ((<= n 2) 1)
(T (+ (fib (- n 1)) (fib (- n 2))))
)
)
; Príklady:
(fib 2) ; -> 1
(fib 3) ; -> 2
(fib 7) ; -> 13
(fib 23) ; -> 28657
; Implementácia: 2 možnosť (efektivnejšia verzia).
; Funkcia isin slúži na zistenie toho, či sme už počítali hodnotu c
; (teda či je v zozname azoz) a ak áno vráti hodnotu výsledku.
; Inak vráti NIL.
(defun isin (c zoz)
(cond ((null zoz) NIL)
((= c (first (first zoz))) (second (first zoz)))
(T (isin c (rest zoz)))
)
)
; Príklad:
(isin 3 '((1 1)(2 1)(3 2))) ; -> 2
; Funkcia novy.
; Pridá nový prvok do zoznamu. Index bude a. Hodnota bude zoz[b]+zoz[c].
(defun novy (a b c azoz)
(cons (list a (+ (isin b azoz) (isin c azoz))) azoz)
)
; Príklad:
(novy 7 1 2 '((1 5)(2 6))) ; -> ((7 11)(1 5)(2 6))
; Funkcia zfib.
; Doplní zoznam o chýbajúce výsledky pre n a všetky podvýsledky.
; Úvodná inicializácia azoz pre náš príklad je ((1 1)(2 1))!
; Vracia celý zoznam ((parameter hodnota)...).
; Dôležité tu je, že zfib(n-2) sa vykoná a aktualizovaný zoznam
; predá zfib(n-1) a tá predá aktualizovaný zoznam výsledkov (azoz)
; funkcií novy. Na tomto mieste v zozname už určite sú
; výsledky pre (n-1) a (n-2) a funkcia novy môže korektne prebehnúť.
(defun zfib (n azoz)
(cond ((isin n azoz) azoz)
(T (novy n (- n 1) (- n 2) (zfib (- n 1) (zfib (- n 2) azoz))))
)
)
; Príklady:
(zfib 2 '((1 1)(2 1))) ; -> ((1 1)(2 1))
(zfib 4 '((1 1)(2 1))) ; -> ((4 3)(3 2)(1 1)(2 1))
; Hlavná funkcia.
; Najprv vytvoríme celý zoznam výsledkov pomocou zfib a potom z neho
; pomocou isin vyberieme náš potrebný výsledok.
(defun fib (n)
(isin n (zfib n '((1 1)(2 1))))
)
; Príklady:
(fib 2) ; -> 1
(fib 3) ; -> 2
(fib 7) ; -> 13
(fib 23) ; -> 28657