fib/2 — Fibonacci, varianta ineficientă și cu memoizare

Exerciții › Laboratorul 2, Exercițiul 1 (recapitulativ)

fib/2 — Fibonacci, varianta ineficientă și cu memoizare

Laboratorul 2, Exercițiul 1 (recapitulativ) medium Recursivitate pe liste Aritmetică și egalitate (is, =, ==, =:=)

Implementați un predicat fib/2 care primește ca prim argument un număr natural X și returnează al X-lea termen din șirul lui Fibonacci.

Vă răspunde programul la interogarea de mai jos?

?- fib(50, Res).

Observație: varianta recursivă directă (fără memoizare) devine prohibitiv de lentă pentru N ≥ 40. Scrieți și o variantă eficientă efficient_fib/2 cu acumulator.

Hint: pentru varianta cu acumulator, definește un predicat ajutător fib(F1, F0, Index, N, F) care merge din cazul de bază Index = 1 în sus, calculând F2 = F1 + F0 la fiecare pas.

Te-ai blocat?

editor soluție

% Varianta ineficientă
fib(0, 1) :- !.
fib(1, 1) :- !.
fib(N, R) :-
    N1 is N - 1,
    N2 is N - 2,
    fib(N1, R1),
    fib(N2, R2),
    R is R1 + R2.

% Varianta cu memoizare
fib(F, _, N, N, F) :- !.
fib(F1, F0, Index, N, F) :-
    F2 is F1 + F0,
    NewIndex is Index + 1,
    fib(F2, F1, NewIndex, N, F).

efficient_fib(N, F) :-
    fib(1, 1, 1, N, F).

Tastează o interogare (ex. father_of(sandra, X).) și apasă Enter — sau apasă pe un caz de test de mai jos.

Cazuri de test (3 — apasă pe unul ca să îl rulezi, sau Verifică pentru toate)

fib(10, R). așteptat: R = 89

efficient_fib(10, R). așteptat: R = 89

efficient_fib(50, R). așteptat: R = 20365011074