% KSP 19-3-6 Kozel zahradníkem

fib(N,F) :- fibiter(N,0,1,F).

fibiter(0,F1,F2,F) :- F is F1 + F2.
fibiter(N,F1,F2,F) :- N1 is N - 1,
	F3 is F1 + F2,
	fibiter(N1,F2,F3,F).

% KSP 19-3-6 Stromeček

delka([],0).
delka([_|Telo],Delka) :- delka(Telo,Delka1), Delka is Delka1 + 1.

strom([],nil).
strom(Seznam,VyslStrom) :- delka(Seznam,Delka),
	strom2(Seznam,Delka,_,VyslStrom).

% strom2(Seznam, Delka, Zbytek, VyslStrom)
% Ze seznamu Seznam udělá binární vyvážený strom o délce Delka
% Použije Delka prvků od počátku seznamu a nepoužitý zbytek vrátí
% pro další použití
strom2(Seznam,0,Seznam,nil).

% Ze vstupního seznamu si uříznu první prvek (tedy hlavu),
% udělám z ní strom a nepoužitý zbytek vrátím. Hotovo.
strom2([H|Telo], 1, Telo, t(nil, H, nil)).

strom2(Seznam, Delka, Zbytek, t(LevyStrom,Stred,PravyStrom)) :-
	DelkaLevy is Delka // 2,             % Zjistím, kolik prvků má být v levém podstromu
	DelkaPravy is Delka - DelkaLevy - 1, % Zjistím, kolik prvků má být v pravém podstromu
	% Chci ze vstupního seznamu ukousnout DelkaLevy prvků a z nich vyrobit
	% LevyStrom, tj. levý podstrom. Zároveň se mi vrátí nepoužitý zbytek seznamu
	strom2(Seznam, DelkaLevy, [Stred|Zbytek1], LevyStrom),

	% Vezmu nepoužitý zbytek seznamu, jeho hlavu použiju jako střed stromu,
	% z těla si ukousnu DelkaPravy prvků a z těch udělám pravý podstrom. Zase vrátím
	% nepoužitý zbytek seznamu a ten se vrátí jako nepoužiý zbytek z celého predikátu.
	strom2(Zbytek1, DelkaPravy, Zbytek, PravyStrom).