%   La suite de Fibonacci est definie par
%   f(0)=0
%   f(1)=1
%   f(n)=f(n-1)+f(n-2)
%   
%   le predicat fibo par
%   fibo(N,F) <=> F=f(N)

% version declarative %%%%%%

fibo(0,0).
fibo(1,1).
fibo(N,F):-N>1,N1 is N-1,fibo(N1,F1),N2 is N-2,fibo(N2,F2),F is F1+ F2,
           write('N='),write(N),write(' F='),write(F),nl.

% version, non declarative, memorisant les valeurs deja calculees %%%%%%

:- dynamic fibo1/2. % necessaire dans certaines versions de prolog pour avoir
                    % le droit d'ajouter dynamiquement des clauses fibo1(.,.)
fibo1(0,0).
fibo1(1,1).
fibo1(N,F):-N>1,N1 is N-1,fibo1(N1,F1),N2 is N-2,fibo1(N2,F2),F is F1+ F2,
            write('N='),write(N),write(' F='),write(F),nl,
            asserta((fibo1(N,F) :- !)).
% pour une seule execution, la coupe n'est pas indispensable
% mais elle l'est en cas de retour arriere 


%%   Executions   %%%%%%%

%%   ?- fibo(6,Fib).
%%   N=2 F=1
%%   N=3 F=2
%%   N=2 F=1   % f(2) est calcule une 2eme fois
%%   N=4 F=3
%%   N=2 F=1   % f(2) est calcule une 3eme fois
%%   N=3 F=2   % f(3) est calcule une 2eme fois
%%   N=5 F=5
%%   N=2 F=1   % f(2) est calcule une 4eme fois
%%   N=3 F=2   % f(3) est calcule une 3eme fois
%%   N=2 F=1   % f(2) est calcule une 5eme fois
%%   N=4 F=3   % f(4) est calcule une 2eme fois
%%   N=6 F=8
%%   
%%   Fib = 8 
 

%%%%%%%%%%%%%%%%%%%%%%%%%

%%   ?- listing(fibo1).

%%   :- dynamic fibo1/2.
%%   fibo1(0, 0).
%%   fibo1(1, 1).
%%   fibo1(A, D) :- A>1, B is A-1, fibo1(B, E), C is A-2, fibo1(C, F), D is E+F,
%%                  write('N='), write(A), write(' F='), write(D), nl,
%%                  asserta((fibo1(A, D):-!)).

%%   ?- fibo1(6,Fib).
%%   N=2 F=1
%%   N=3 F=2
%%   N=4 F=3
%%   N=5 F=5
%%   N=6 F=8
%%   
%%   Fib = 8 

%%   ?- listing(fibo1).

%%   :- dynamic fibo1/2.
%%   fibo1(6, 8) :- !.   % toutes les valeurs intermediaires
%%   fibo1(5, 5) :- !.   % qui ont ete caculees sont memorisees
%%   fibo1(4, 3) :- !.
%%   fibo1(3, 2) :- !.
%%   fibo1(2, 1) :- !.
%%   fibo1(0, 0).
%%   fibo1(1, 1).
%%   fibo1(A, D) :- A>1, B is A-1, fibo1(B, E), C is A-2, fibo1(C, F), D is E+F,
%%                  write('N='), write(A), write(' F='), write(D), nl,
%%                  asserta((fibo1(A, D):-!)).

%%  ?- fibo1(8,Fib).
%%  N=7 F=13      % seules les valeurs pour 7 et 8
%%  N=8 F=21      % ont besoin d'etre calculees
%%  
%%  Fib = 21 

%%  ?- fibo1(5,Fib).
%%                % rien a calculer  
%%  Fib = 5