rolisz's site

Tutorial Prolog

Cu ocazia apropierii parțialu­lui 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 aran­ja­mentelor 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]]

Aran­ja­mentele sunt alegeri din elementele listei în care ordinea contează. O metodă simplă de a genera aran­ja­mentele este să generăm com­binările și apoi generăm per­mutările fiecăruia. Com­bină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. Back­trackingul din Prolog will take care of the rest. Per­mută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).
  1. Sa se scrie un program care genereaza lista sub­mul­ti­m­ilor 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 com­bină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 sub­mulțimea cu suma S' = S - E din restul listei. Dacă am lăsa doar atât, atunci am obține aran­ja­mentele, așa că trebuie să impunem o condiție asupra alegerii el­e­mentelor. 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).
  1. 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).
  1. Se da sirul a1,...an. Se cere sa se determine toate sub­sirurile strict cresca­toare 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 au­toape­lează 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 de­screscă­tor. Cool stuff: putem folosi recursiv notația din Prolog pentru liste și obținem chestii gen [First|[Sec­ond|[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]).
  1. Fiind dat un numar n pozitiv, se cere sa se determine toate de­scom­puner­ile 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:

  1. Definiti un predicat care determina valoarea unui polinom intr-un punct. Polinomul se da sub forma listei co­e­fi­ci­en­tilor 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 co­e­fi­cien­tul 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 co­e­fi­cienț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 poli­no­mu­lui fără co­e­fi­cien­tul curent (și cu contorul in­cre­men­tat).

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 co­e­fi­cien­tul 1, nu cu 0, nu îi bug ci îi feature.