Tutorial Prolog
Cu ocazia apropierii parțialului de Prolog, am găsit și eu o nouă temă pentru un post de blog: câteva exerciții de Prolog rezolvate și explicate.
1. Sa se genereze lista aranjamentelor de K elemente, cu elementele unei liste date. Ex: [2,3,4] K=2 => [[2,3], [3,2], [2,4], [4,2], [3,4], [4,3]]
Aranjamentele sunt alegeri din elementele listei în care ordinea contează. O metodă simplă de a genera aranjamentele este să generăm combinările și apoi generăm permutările fiecăruia. Combinările le putem genera în două moduri: alegând primul element din listă și reunind cu o combinare mai mică din restul listei, sau dintr-o combinare de aceași mărime din restul listei. Backtrackingul din Prolog will take care of the rest. Permutările le generăm scoțând elemente pe rând din listă și reunindu-le cu permutări din lista mai mică (care nu conține elementul ales).
domains
list=integer* predicates
aranjamente(list,integer,list)
combinari(list,integer,list)
permutari(list,list)
element(list,integer,list)
clauses
aranjamente(L,N,R):-
combinari(L,N,R1),
permutari(R1,R).
combinari(_,0,[]):-!.
combinari([H|T],N,[H|C]):-
N1=N-1,
combinari(T,N1,C).
combinari([_|T],N,C):-
combinari(T,N,C).
element([H|T],H,T).
element([H|T],C,[H|R]):-element(T,C,R).
permutari([],[]).
permutari(L,[E|C]):-element(L,E,X),
permutari(X,C).2. Sa se scrie un program care genereaza lista submultimilor de suma S data, cu elementele unei liste. Ex: [1,2,3,4,5,6,10] si S=10 => [[1,2,3,4], [1,4,5], [2,3,5], [4,6], [10]]
Există mai multe opțiuni aici. Am putea să generăm pe rând toate combinările de 1,2,3,4... elemente și să vedem care au suma care trebuie. Dar o metodă mai directă este să luăm pe rând câte un element din listă și să încercăm să îl adăugăm la lista obținută din încercând să generăm submulțimea cu suma S' = S - E din restul listei. Dacă am lăsa doar atât, atunci am obține aranjamentele, așa că trebuie să impunem o condiție asupra alegerii elementelor. Eu am ales să le aleg să fie în ordine crescătoare.
domains
list=integer*
predicates
element(list,integer,list)
suma(list,integer,list)
clauses
suma(_,0,[]):-!.
suma(L,S,[E|[H|T]]):-
element(L,E,L1),S1=S-E,S1>=0,
suma(L1,S1,[H|T]),E<H.
suma(L,E,[E]):-element(L,E,_).
element([H|T],H,T).
element([H|T],C,[H|R]):-
element(T,C,R).3. Sa se genereze toate sirurile de n paranteze ce se inchid corect.Exemplu: n=4 sunt 2 solutii: (()) si ()()
Pentru cei care vor să știe prea multe, numele general al unui asemenea șir este de Dyck word și numărul de asemenea șiruri este dat de numerele Catalan. Dar să trecem la generarea lor.
Primul lucru pe care îl observăm este că pentru N impar, nu avem soluție, deci nici nu are rost să ne chinuim. Apoi, va trebui să numărăm câte paranteze deschise și închise avem până acuma, și acestea fiind în total în număr de N/2, ne va fi mai ușor să lucrăm cu un predicat auxiliar care să aibă ca parametru numărul de paranteze de fiecare tip deschise. Dacă numărul de paranteze închise este mai mic decât cel de cele deschise, putem pune o paranteză închisă. Dacă numărul de paranteze deschise este mai mic decât N/2, mai putem adăuga o paranteză deschisă. Și cam atât. Programul se oprește în momentul în care numărul de paranteze închise și deschise este egal cu N/2.
domains
list=symbol*
predicates
paranteze(integer,list)
dyck(integer,integer,integer,list)
clauses
paranteze(N,R):-N mod
2=0,N2=N/2,dyck(N2,0,0,R).
dyck(N,N,N,[]):-!.
dyck(N,D,I,["("|X]):-D<N,D1=D+1,
dyck(N,D1,I,X).
dyck(N,D,I,[")"|X]):-I<D,D<=N,I1=I+1,
dyck(N,D,I1,X).4. Se da sirul a1,...an. Se cere sa se determine toate subsirurile strict crescatoare ale sirului a.
Prima observație este că dacă a_i,a_(i+1),...a_j este subșir crescător, și a_i,a_(i+1) este subșir crescător. Și evident toate celelalte până la a_j. Ca să facem lucrurile mai simple, folosim iar un predicat auxiliar. Predicatul principal are două clauze: una în care se autoapelează cu lista începând de la al doilea element, iar în cealaltă clauză se verifică dacă primele două elemente sunt în ordinea crescătoare, și dacă da, atunci folosim predicatul auxiliar să parcurgem lista până când elementul următor este descrescător. Cool stuff: putem folosi recursiv notația din Prolog pentru liste și obținem chestii gen [First|[Second|[Third|Tail]]] :>:>
domains
list=integer*
predicates
subsir(list,list)
subs(list,list) clauses
subsir([_|T],X):-subsir(T,X).
subsir([H|[S|T]],X):-H<S,subs([H|[S|T]],X).
subs([H],[H]).
subs([H|[T|S]],[H|X]):-H<T,
subs([T|S],X).
subs([H|[T|_]],[H]):-H>T,!.
subs([H|_],[H]).5. Fiind dat un numar n pozitiv, se cere sa se determine toate descompunerile sale ca suma de numere prime distincte.
Aici vom reduce repede problema la o problemă anterioară, la cea cu suma: vom genera o listă de toate numerele prime până la n, și apoi vom alege dintre ele pe acelea care ni se potrivesc. Partea de generare a listei de numere prime este cea mai lungă parte a problemei, pentru că are patru predicate. Primul predicat e cel care verifică dacă un număr e prim sau nu și face aceasta apelând un predicat care împarte pe rând numărul nostru la numerele mai mici decât el. Dacă nu se găsește niciun număr care să dividă, atunci numărul e prim. Apoi avem un predicat nextprim, care pur și simplu verifică numerele din 2 în 2 până găsește un număr prim mai mare decât cel pe care i l-am dat. Predicatul listaprime primește ca input două numere și caută toate numerele prime între ele și returnează lista lor.
domains
list=integer* predicates
divizibil(integer,integer)
prim(integer)
nextprim(integer,integer)
descompune(integer,list)
listaprime(integer,integer,list)
suma(list,integer,list)
element(list,integer,list)
clauses
prim(2):-!.
prim(N):-I=2,N>1,not(divizibil(N,I)).
divizibil(N,I):-
N mod I = 0,!.
divizibil(N,I):-
I2 = I*I,I2<N,I1=I+1,divizibil(N,I1).
nextprim(2,3):-!.
nextprim(N,N1):-N1=N+2,prim(N1),!.
nextprim(N,R):-N1=N+2,nextprim(N1,R).
listaprime(I,R,[]):-I>R,!.
listaprime(I,F,[H|T]):-nextprim(I,H),listaprime(H,F,T).
suma(_,0,[]):-!.
suma(L,S,[E|[H|T]]):-element(L,E,L1),S1=S-E,S1>=0,
suma(L1,S1,[H|T]),E<H.
suma(L,E,[E]):-element(L,E,_).
element([H|T],H,T).
element([H|T],C,[H|R]):-element(T,C,R).
descompune(N,X):-listaprime(1,N,L),suma(L,N,X).Update la cererea publicului:
6. Definiti un predicat care determina valoarea unui polinom intr-un punct. Polinomul se da sub forma listei coeficientilor sai.
În primul rând Sorina, avem nevoie de un predicat care să ne ridice un număr la o putere. Asta face pow. Cazul de oprire este când coeficientul este 1 și atunci returnăm numărul dat. În rest calculăm puterea mai mică cu unul și apoi returnăm valoarea respectivă înmulțită cu numărul nostru.
Apoi, avem predicatul principal care primește care parametru lista de coeficienți, punctul în care evaluăm și returneză rezultatul. Ca să știm la al câtelea coeficient suntem (și astfel să știm gradul lui), folosim un predicat auxiliar, care este la fel ca cel principal, doar că are un contor care începe la 1 și ne zice la ce putere să ridicăm numărul nostru. Cazul de bază este când suntem la ultimul coeficient și atunci returnăm pur și simplu N^M * H. În celălalt caz calculăm N^M * R și adunăm apoi la rezultatul returnat de evaluarea polinomului fără coeficientul curent (și cu contorul incrementat).
domains
list=integer*
predicates
polynomial(list,integer,integer) % i,i,o
poly(list,integer,integer,integer) % i,i,i,o
pow(integer,integer,integer) % i,i,o clauses
pow(N,1,N):-!.
pow(N,M,R):-M1=M-1,pow(N,M1,R1),R=R1*N.
polynomial(L,N,R):-poly(L,N,1,R).
poly([H],N,M,R):-pow(N,M,R1),R=R1*H,!.
poly([H|T],N,M,R):-pow(N,M,R1),R2=R1*H,
M1=M+1,poly(T,N,M1,R3),R=R3+R2.Faptul că începe cu coeficientul 1, nu cu 0, nu îi bug ci îi feature.