פרולוג תרגיל 5

bennyprologLeave a Comment

תרגיל 5 בפרולוג – רקורסיות, רקורסיות זנב, ורקורסיות על רשימות מקוננות

פיתרון 1


first_last([],[],[]):-!.
first_last([F|LST],F,T):-last([F|LST],T).
last([F],F):-!.
last([_|L],T):-last(L,T).
/*
tail recurtion
1.cut green
2.cut green

1 ?- first_last([],F,T).
F = T, T = [].

2 ?- first_last([1],F,T).
F = T, T = 1.

3 ?- first_last([1,2,3],F,T).
F = 1,
T = 3.
*/

product([],0):-!.
product([X],X):-!.
product([X|List], Product):-product(List, Product1),Product is X*Product1.
/*
recurtion
1.cut red
2.cut green

7 ?- product([1,1,1],Result).
Result = 1.

8 ?- product([1,1,2],Result).
Result = 2.

9 ?- product([1,10,2],Result).
Result = 20.

11 ?- product([],Result).
Result = 0.
*/

product1([],0):-!.
product1(List,Result):-product1(List,1,Result).
product1([X],Product,X1):-X1 is X*Product,!.
product1([X|List],Product,Result):-Result1 is X*Product, product1(List, Result1,Result).
/*
tail recurtion
1.cut red 
2.cut green

15 ?- product1([1,1,1],Result).
Result = 1.

[1] 16 ?- product1([1,10,2],Result).
Result = 20.

[1] 17 ?- product1([],Result).
Result = 0.
*/

flatten([],[]):-!.
flatten([X|L1],[X|L]):-atomic(X),flatten(L1,L),!.
flatten([X|L1],Z):-not(atomic(X)), flatten(X,S),flatten(L1,L),append(S,L,Z).

product2(List, Product):- flatten(List, L),product(L, Product).
/*
רקורסיה רגילה עבור רשימות מקוננות
1.cut green
2.cut green
3 ?- product2([1,[2],3],Result).
Result = 6.

4 ?- product2([1,2,3],Result).
Result = 6.

5 ?- product2([],Result).
Result = 0.

6 ?- product2([1,2,[3,2,3]],Result).
Result = 36.
*/

kuku1([],[]):-!.
kuku1([X],[K]):-kefel(X,K),!.
kuku1([X|L1],R):-kuku1(L1,L2),kefel(X,K),append(L2,[K],R).
kefel(X,[X,Y]):-Y is X*2.
/*
רקורסיה רגילה
1. cut green
2. cut green

?- kuku1([1,3,4,6],R).
R = [[6, 12], [4, 8], [3, 6], [1, 2]].
*/

kuku([],[]):-!.
kuku([X],K):-kefel(X,K),!.
kuku(L,X1):-reverse(L,LR),kefel1(LR,X1).
kefel1([X],[[X,Y]]):-Y is X*2,!.
kefel1([X|Rest],[[X,Y]|R]):-Y is X*2, kefel1(Rest,R).

/*
tail recurtion
1. cut green
2. cut green
3. cut green

10 ?- kuku([1,2,5,9],R).
R = [[9, 18], [5, 10], [2, 4], [1, 2]].

11 ?- kuku([9],R).
R = [9, 18].
*/

kuku3([],[]):-!.
kuku3([X],[K]):-kefel(X,K),!.
kuku3([X|L1],R):-atomic(X),kuku3(L1,L2),kefel(X,K),append(L2,[K],R),!.
kuku3([X|L1],R):-kuku3(X,K),kuku3(L1,L2),append(L2,[K],R).
kefel(X,[X,Y]):-Y is X*2.

/*
רקורסיה רגילה על רשימה מקוננת
1. cut green
2. cut green
3. cut green

 ?- kuku3([1,[3,4],6],R).
R = [[6, 12], [[4, 8], [3, 6]], [1, 2]].
*/

flattenList([],[]):-!.
flattenList([X|L1],[X|L]):-atomic(X),flattenList(L1,L),!.
flattenList([X|L1],Z):-not(atomic(X)), flattenList(X,S),flattenList(L1,L),append(S,L,Z).

/*
 recurtion
1. cut green
2. cut green
55 ?- flattenList([1,[[4,5,6],7,8,[9]]],X).
X = [1, 4, 5, 6, 7, 8, 9].
*/

flattenList1(L,R):-flattenList1(L,[],R).
flattenList1([],Acc,Acc):-!.
flattenList1([X|L],Acc,R):-atomic(X),append(Acc,[X],X1),flattenList1(L,X1,R),!.
flattenList1([X|L],Acc,R):-append(X,L,R1),flattenList1(R1,Acc,R).

/*
tail recurtion
1. cut green
2. cut green

62 ?- flattenList1([1,2,[3,4],4,5],R).
R = [1, 2, 3, 4, 4, 5].

63 ?- flattenList1([1,2,[3,4],[[4],5]],R).
R = [1, 2, 3, 4, 4, 5].
*/

deepReverse([],[]):- !.
deepReverse([X|Rest],Result):- atomic(X),deepReverse(Rest,L),append(L,[X],Result),!.
deepReverse([X|Rest],Result):-deepReverse(X,L),deepReverse(Rest,L1), append(L1,[L],Result).

/*
1. cut green
2. cut green

 ?- deepReverse([1,2,[3,4],5],L).
L = [5, [4, 3], 2, 1].

 ?- deepReverse([1,2],L).
L = [2, 1].

 ?- deepReverse([1,2,[[3,4],5],[6]],L).
L = [[6], [5, [4, 3]], 2, 1].
*/








benny
פיתרון 2


1)	first_last([X], X, X).
first_last([X, Y | L], X, F) :- first_last([Y | L], Y, F), !.

רקורסיה זנבית, הקריאה הרקורסיבית היחידה היא בשורה השנייה, אין נקודות backtracking משמאל לקריאה הרקורסיבית שבו החוק נמצא.



2)	רגילה: 
product([H | L], P) :- product(L, P17), P is P17  * H, !.
product([H], H).



זנבית: 
product([H], H) :- !.
product([X, Y | L], Res) :- Z is X * Y, product([Z | L], Res).



רמ"מ:
product([],1).
product([H | T], Res) :- number(H), !, product(T, Res17), Res is H * Res17.
product([H | T], Res) :- product(H, Res17), product(T, Res18), Res is Res18 * Res17.



3)	רגילה:
kuku([H | T], Z) :- H17 is 2 * H, append(Z1,[[H, H17]],Z), kuku(T, Z1), !.
kuku([],[]).


זנבית:
kuku(L, Z) :- kuku(L, [], Z).
kuku([], Res, Res).
kuku([H | T], Z, Res) :- H17 is 2 * H, Z17 = [[H, H17] | Z], kuku(T, Z17, Res).



רמ"מ:
kuku([], []).
kuku([H | T], Z) :- number(H), !, H17 is 2 * H, append(Z17,[[H, H17]], Z), kuku(T, Z17), !.
kuku([L | T], Z) :- kuku(L, L17), append(Z17, [L17], Z), kuku(T, Z17), !.


4)	לא זנבית:
flattenList([],[]) :- !.
flattenList([H | T], L) :- listp(H), !, append(H, T, H17), flattenList(H17, L).
flattenList([H | T], [H | L]) :- flatten(T, L).

listp([_ | _]).
listp([]).

זנבית:
flattenList(L, S) :- flattenList(L,[],S).
flattenList([], Res, Res).
flattenList([H | T], L, Res) :- listp(H), !, append(L, H, L17), append(L17, T, L34), !, flattenList(L34, [], Res).
flattenList([H | T], L, Res) :- append(L, [H], L17), flattenList(T, L17, Res).

listp([_ | _]).
listp([]).
5)	deepReverse([],[]).
deepReverse([H | T], Z) :- listp(H), !, deepReverse(H, H17), deepReverse(T, T17), append(T17, [H17], Z).
deepReverse([H | T], Z) :- deepReverse(T, T17), append(T17, [H], Z).

listp([_ | _]).
listp([]).

H.s

פיתרון 3



%prolog5
%1
%this is non tail rec. explaitation: we are not count before we call rec, also we build stack for the next calls.
%the cut is green one.
first_last([H|T], H, T1):-first_last(T, H1, T1), !.
first_last([A], H1, A).


%2
%tail rec
product(List, Product):- product(List, 1, Product).
product([], Product, Product).
product([H|T], ACC, Product):- ACC1 is H*ACC, product(T, ACC1, Product).
%non tail rec
product1([H|T], Product):- product1(T, Product1), Product is H*Product1.
product1([], 1).
%rec רמ"מ the first cut is red one, and the rest are green one
product2([H|T], Product):- listp(H), !, product2(H, Product1), product2(T, Product2), Product is Product1*Product2.
product2([H|T], Product):-!,  product2(T, Product1), Product is H*Product1.
product2([], 1).
listp([ _ | _ ]):- !.
listp([ ]).

%3
%tail rec
kuku(L1, L2):-kuku(L1, [], L2).
kuku([], L2, L2).
kuku([H|T], ACC, L2):- H1 is 2*H, append([[H, H1]], ACC, ACC1), kuku(T, ACC1, L2).
%non tail rec
kuku1([H|T], L):-kuku1(T, L1), H1 is 2*H, append(L1, [[H, H1]], L).
kuku1([],[]).
%rec רמ"מ the first cut is red one, and the rest are green one
kuku2([H|T], L):- listp(H), !, kuku2(H, L1), kuku2(T, L2), append(L2, [L1], L).
kuku2([H|T], L):-!, kuku2(T, L1), H1 is 2*H, append(L1, [[H, H1]], L).
kuku2([],[]).

%4
%non rec and the first cut is red one
flattenList([H|T], Flat):-listp(H), !, flattenList(H, Flat1), flattenList(T, Flat2), append(Flat1, Flat2, Flat).
flattenList([H|T], Flat):-!, flattenList(T, Flat1), append([H], Flat1, Flat).
flattenList([], []).

%5
%the first cut is red
deepReverse([H|T], Deep):-listp(H), !, deepReverse(H, Deep1), deepReverse(T, Deep2), append(Deep2, [Deep1], Deep).
deepReverse([H|T], Deep):-!, deepReverse(T, Deep1), append(Deep1, [H], Deep).
deepReverse([], []).



%1
%this is non tail rec. explaitation: we are not count before we call rec, also we build stack for the next calls.

דוגמאות הרצה

1.---------------------------

?- first_last([1, 2, 3], F, L).
F = 1,
L = 3.

2.---------------------------

?- product([1, 2 3], Product).
Product = 23.

?- product1([1, 2, 3], Product).
Product = 6.

?- product2([1, 2, 3, 3], Product).
Product = 18.

3.------------------------------

?- kuku([1,2], Z).
Z = [[2, 4], [1, 2]].

?- kuku2([1,2], Z).
Z = [[2, 4], [1, 2]].

?- kuku2([1,2], Z).
Z = [[2, 4], [1, 2]].

4.----------------------

?- flattenList([1, 2, 3, [4, 5, [[6], 7]]], Flat).
Flat = [1, 2, 3, 4, 5, 6, 7].

5.----------------------

?- deepReverse([a,[d,f],[],[[k],g]],R).
R = [[g, [k]], [], [f, d], a].


Y,levental

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *