Correction des exercices de listes de l'AP

Code:

puissance(0,0,Y):-Y<>0,!.
puissance(Y,Y,1):-!.
puissance(X,Y,Z):-T=Z-1,puissance(E,Y,T),X=E*Y.


predicates
  fib1(integer,integer)
  fib2(integer,integer)
  fib3(integer,integer)
  iteration(integer,integer,integer,integer,integer)
clauses
  fib1(0,1).
  fib1(1,1).
  fib1(X,Y) :- X>=2,J=X-2,I=X-1,fib1(J,R),fib1(I,H),Y=R+H.
/* cette version ne permet pas d'aller plus loin que fib(11,N). */
  fib2(0,1):-!.
  fib2(1,1):-!.
/* jusqu'a fib2(22,K).*/
  fib2(X,Y):-J=X-2,I=X-1,fib2(J,R),fib2(I,H),Y=R+H.

  fib3(0,1):-!.
  fib3(1,1):-!.
  fib3(N,R):-iteration(N,2,1,1,R).
  iteration(N,N,X,Y,R):-R=X+Y,!.
  iteration(N,I,X,Y,R):-II=I+1,XX=Y,YY=X+Y,iteration(N,II,XX,YY,R).
/* meme borne que precedemment avec un temps de calcul moindre */

  produit(0,X,0).
  produit(X,Y,Z):-suc(X,T),produit(T,Y,E),somme(E,Y,Z).

  inf(X,Y):-suc(Y,_).
  inf(X,Y):-suc(X,X1),suc(Y,Y1),inf(X1,Y1).
  div(A,B,Q,R):-produit(B,Q,T),somme(T,R,A),inf(R,B).

domains
  liste=integer*
predicates
  liste_pair(liste,liste)
clauses
  liste_pair1([],[]).
  liste_pair1([X|L],[X|Y]) :- 0=X mod 2, liste_pair1(L,Y).
  liste_pair1([X|L],Y) :- 0<>X mod 2, liste_pair1(L,Y).

  liste_pair([],[]):-!.
  liste_pair([X|L],[X|Y]):-0=X mod 2,!,liste_pair(L,Y).
  liste_pair([_|L],Y) :-liste_pair(L,Y).


predicates
  reverse1(liste,liste)
  reverse2(liste,liste)
  reverse_acc(liste,liste,liste)
  append(liste,liste,liste)
  appart1(integer,liste)
  appart2(integer,liste)
  prefixe1(liste,liste)
  prefixe2(liste,liste)
  suffixe2(liste,liste)
  sous_liste(liste,liste)
  sous_liste2(liste,liste)
clauses
  append([],X,X).
  append([X|L],Y,[X|Z]):-append(L,Y,Z).
  reverse1([],[]).
  reverse1([X|L],Z):- reverse1(L,T),append(T,[X],Z).

  reverse2(X,Y):- reverse_acc(X,[],Y).
  reverse_acc([X|Y],A,Z):-reverse_acc(Y,[X|A],Z).
  reverse_acc([],Y,Y).

 prefixe1([],_).
  prefixe1([X|Xs],[X|Ys]):-prefixe1(Xs,Ys).

  suffix(X,X).
  suffix(X,[Y|L]):-suffix(X,L).

  prefixe2(X,Y):-append(X,Z,Y).
  suffixe2(X,Y):-append(Z,X,Y).

 sous_liste(X,Y):- append(Z,B,Y), append(A,X,Z).
  sous_liste2(X,L):-prefixe(P,L),suffixe(X,P). /*(Suffixe de prefixe)*/
  sous_liste3(X,L):-prefixe(X,T),suffixe(T,L). /*(Prefixe de suffixe)*/

/* --select(X,Y,Z): La liste Z est le resultat obtenu en rayant
une occurrence X de la liste Y. ce programme est utlisable suivant
plusieurs mode----*/
  select(X,[X|L],L).
  select(X,[Y|L],[Y|M]):-select(X,L,M).

/*delete(L,X,M): La liste M est le resultat obtenu en effacant
toutes les occurrences de X dans le liste L----*/
  delete([],_,[]).
  delete([X|L),X,M):- delete(L,X,M).
  delete([X|L),Y,[X|M]):- X<>Y, delete(L,X,M).


  member(X,[X|_]).
  member(X,[_|L]):-member(X,L).


  make-set([],[]).
  make-set([X|L],T):-member(X,L),!,make-set(L,T).
  make-set([X|L],[X|T]):-make-set(L,T).


  subset([],_).
  subset([X|L],T):-member(X,T), subset(L,T).


  union(L1,L2,L):-concate(L1,L2,T),make-set(T,L).


  inter([],_,[]).
  inter([X|L],T,[X|E]):-member(X,T),!,inter(L,T,E).
  inter([_|L],T,E):-inter(L,T,E).


   sous-suite-ex([],_).
   sous-suite-ex([X|L],[X|M]):-sous-suite-ex(L,M).
   sous-suite-ex(L,[_|M]):-sous-suite-ex(L,M).


/* ------------------------------Tri par permutation ------------- */
  sort(L,M):-permutation(L,M),ord(M).
  permutation([],[]).
  permutation(L,[Y|M]):-select(Y,L,U),permutation(U,M).
  ord([]).
  ord([_]).
  ord([X|[Y|L]]):-X<=Y,ord([Y|L]).

/* -------- Tri par insertion ------*/
  sort([],[]).
  sort([X|L],M):-sort(L,U), insert(X,U,M).
  insert(X,[],[X]).
  insert(X,[Y|M],[Y|U]):- X>Y, insert(X,M,U).
  insert(X,[Y|M],[X|[Y|M]]):-X<=Y.
/* -------- tri par insertion utilisant un accumulateur -------*/
 predicates
 insert(integer,liste,liste)
 sort(liste,liste)
 sort_ins(liste,liste,liste)
clauses
 insert(X,[],[X]):-!.
 insert(X,[Y|L],[X|[Y|L]]):- X<=Y,!.
 insert(X,[Y|L],[Y|M]):-insert(X,L,M).
 sort_ins([],L,L):-!.
 sort_ins([X|L],D,H):-insert(X,D,T),sort_ins(L,T,H).
 sort(L,M):-sort_ins(L,[],M).


/* ------------------- Tri rapide ------------------- */
  qs([],[]).
  qs([X|L],M):- partition(L,X,P,G), qs(P,LP), qs(G,LG),
                app(LP,[X|LG],M).
  partition([],Y,[],[]).
  partition([X|L],Y,[X|M],U):-X<=Y,partition(L,Y,M,U).
  partition([X|L],Y,M,[X|U]):-X>Y, partition(L,Y,M,U).

predicates
 pp(liste,integer)
 tri_sel(liste,liste)
 select(integer,liste,liste)
/*--------------------- tri par selection du minimum-------*/
clauses
 pp([],_):-!,fail.
 pp([X],X):-!.
 pp([X|[Y|L]],X):- pp([Y|L],Z), X<=Z,!.
 pp([_|[Y|L]],T):-pp([Y|L],T).
 select(X,[X|L],L):-!.
 select(X,[Y|L],[Y|M]):- select(X,L,M).
 tri_sel([],[]).
 tri_sel([I|L],[X|M]):-pp([I|L],X),select(X,[I|L],T),tri_sel(T,M).

/*----------------------------- Tri par fusion
---------------------------*/
predicates
 trier(liste,liste)
 separer(liste,liste,liste))
 fusion(liste,liste,liste)
clauses
  trier([],[]).
  trier([X],[X]).
  trier([X|[Y|L]],LL):-separer([X|[Y|L]],L1,L2),
                      trier(L1,LL1), trier(L2,LL2),
                      fusion(LL1,LL2,LL).
  separer([],[],[]).
  separer([X],[X],[]).
  separer([X|[Y|L]],[X|M],[Y|U]):-separer(L,M,U).
  fusion([],L,L).
  fusion([X|L],[],[X|L]).
  fusion([X|L1],[Y|L2],[X|L]):-X<=Y, fusion(L1,[Y|L2],L).
  fusion([X|L1],[Y|L2],[Y|L]):-X<=Y, fusion([X|L1],L2,L).


  Tri-Cr-De([],[],[]):-!.
  Tri-Cr-De([X],[X],[X]):-!.
 
Tri-Cr-De(L,C,D):-Min-max(I,G,E,L),Tri-Cr-De(E,L1,L2),append([I|L1],[G],C),
                             append([G|L2],[I],D).


tri-bul(L,T):-append(L1,[X|[Y|L2]],L),X>Y,!,concate(L1,[Y|[X|L2]],E),tri-bu(E,T).
tri-bul(L,L).



tiger a écrit:Merci!!!
Bonne revision,a propos pourriez vous svp mettre le calendrier des exams sur le forum. Encore merci pour tt ce que vous faites.