Liste, Matrice, Sortari
<![CDATA[
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Liste, Matrice, Sortari
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Prof. Dr. Luminita STATE, 2009
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Prolog, TP 2.0
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/* *********************
* APLICATII LISTE *
* *
*********************/
DOMAINS
lista=integer*
fcv=f(integer,integer)
listaf=fcv*
llista=lista*
predicates
lungime(integer,lista)
suma(integer,lista)
apartine(integer,lista) /* verifica daca un element apartine unei liste */
lipeste(lista,lista,lista) /*concateneaza doua liste */
max_min(integer,integer,lista)/* calculeaza valorile maxima si minima dintr-o lista*/
calc_max(integer,integer,integer)
calc_min(integer,integer,integer)
elimina_ultimul (lista,lista) /* elimina ultimul element al listei prim argument */
elimina(integer,lista,lista) /* elimina element dintr-o lista*/
elimina_duplicate(lista,lista) /*elimina duplicatele elementelor dintr-o lista*/
frecvente(lista,listaf) /* calculeaza frecventele componentelor unei liste */
frecv_element(integer,lista,integer) /* calculeaza frecventa primului argument in lista*/
revers(lista,lista) /* calculeaza reversul unei liste (i,o) */
adauga(lista,integer,lista) /* adauga un element ca ultim argument intr-o lista */
produs_scalar(lista,lista,integer) /* calculeaza produsul scalar a doi vectori reprezentati prin liste */
produs_matrice_vector (llista,lista,lista) /* calculeaza produsul unei matrice reprezentata ca lista
liniilor ei cu un vector */
produs_matrice_matrice(llista,llista,llista) /*calculeaza produsul a doua matrice,
matricea prim argument reprezentata pe linii, matricea al doilea argument reprezentata
pe coloane */
intersectie(lista,lista,lista) /* calculeaza intersectia a doua multimi reprezentate ca liste */
reuniune(lista,lista,lista)
complementara(lista,lista,lista) /* calculeaza complementara listei al doilea argument
in raport cu lista prim argument */
sortare_insertie(lista,lista)
insera(integer,lista,lista)
/* insera primul argument in al doilea argument lista sortata crescator,
calculeaza al treilea argument,lista sortata crescator */
bubble_sort (lista,lista) /* algoritmul de sortare bubble-sort*/
sortata(lista) /* verifica daca lista este sortata crescator */
quick_sort(lista,lista)
/* quick_sort(L,LS)="LS => din sortarea
listei L"*/
separare(lista,integer,lista,lista)
/* separare(L,MC,MR)
separa lista L=[H|T] in lista MR si
MC dupa H*/
concatenare(lista,lista,lista)
inssort(lista,lista)
/*inssort(L,LS) sorteaza lista L in LS*/
inser(integer,lista,lista)
impachetare (lista,integer,llista)
/* "impacheteaza" lista prim argument in liste de lungime al doilea argument */
despachetare(llista,lista)
/* "despacheteaza primul argument lista de liste in cel de al doilea argument */
selecteaza(lista,integer,lista,lista)
/* selecteaza(L,N,R,Rest) compune lista R de N elemente din L,
Rest este lista elementelor ramase din L */
elimina_mic(lista,integer,lista)
/* elimina din lista prim argument componentele mai mici decat al doilea argument*/
citeste_lista_n(integer,lista)
/* citeste_lista_n(N,L): citeste de la tastatura lista L de numere intregi de lungime N */
citeste_lista(lista)
/* citeste_lista (L): citeste de la tastatura lista L de lungime nespecificata */
citeste_lista_liste(integer,llista)
/* citeste_lista_liste(N,L) : citeste de la tastatura lista L de N liste de numere intregi */
scrie_lista(lista)
/* scrie_lista(L) : afiseaza componentele listei de numere intregi L */
scrie_llista (llista)
/* scrie_llista (L) : afiseaza componentele listei de liste de numere intregi L */
clauses
lungime (0,[]):-!.
lungime(N,[_|T]):- lungime (M,T), N=M+1.
suma(X,[X]).
suma(N,[H|T]):-suma(M,T),N=M+H.
apartine (X,[X|_]).
apartine (X,[_|T]):-apartine(X,T).
lipeste([],L,L).
lipeste([H|T],L,[H|R]):-lipeste(T,L,R).
max_min(X,X,[X]).
max_min(Max,Min,[H|T]):- max_min(MaxT,MinT,T),calc_max(MaxT,H,Max), calc_min(MinT,H,Min).
calc_max (X,Y,X):-X>=Y,!.
calc_max (_,Y,Y).
calc_min(X,Y,X):-X<=Y,!.
calc_min(_,X,X).
elimina_ultimul([_],[]):-!.
elimina_ultimul([H|T],[H|R]):-elimina_ultimul(T,R).
elimina(_,[],[]).
elimina(X,[X|T],R):-elimina(X,T,R),!.
elimina(X,[H|T],[H|R]):-elimina(X,T,R).
elimina_duplicate([],[]).
elimina_duplicate([H|T],[H|R]):-elimina(H,T,S), elimina_duplicate(S,R).
frecv_element(_,[],0).
frecv_element(X,[X|T],N):-frecv_element(X,T,M), N=M+1,!.
frecv_element(X,[_|T],N):-frecv_element(X,T,N).
frecvente([],[]).
frecvente([H|T],[f(H,NH)|R]):- frecv_element(H,T,NH), elimina(H,T,S), frecvente (S,R).
revers([],[]).
revers([H|T],R):-revers(T,S), adauga(S,H,R).
adauga([],X,[X]).
adauga([H|T],X,[H|S]):- adauga(T,X,S).
produs_scalar([X],[Y],R):- R=X*Y.
produs_scalar([H1|T1],[H2|T2],R):- produs_scalar(T1,T2,S), R=S+H1*H2.
/*OPERATII CU LISTE DE LISTE */
produs_matrice_vector ([L],V,[R]):-produs_scalar(L,V,R).
produs_matrice_vector([H|T],V,[R|S]):- produs_scalar(H,V,R), produs_matrice_vector(T,V,S).
produs_matrice_matrice (M,[Y],[R]):-produs_matrice_vector(M,Y,R).
produs_matrice_matrice(M,[H|T],[S|M1]):-produs_matrice_vector(M,H,S), produs_matrice_matrice(M,T,M1).
/* OPERATII CU MULTIMI REPREZENTATE CA LISTE */
intersectie ([],_,[]):-!.
intersectie([H|T],L,[H|S]):- apartine (H,L), intersectie2(T,L,S),!.
intersectie([_|T],L,S):-intersectie2(T,L,S).
reuniune([],L,L).
reuniune([H|T],L,[H|S]):-not (apartine (H,L)), reuniune (T,L,S),!.
reuniune([_|T],L,S):- reuniune(T,L,S).
complementara ([],_,[]).
complementara ([H|T],L, S):-apartine (H,L),complementara(T,L,S),!.
complementara ([H|T],L,[H|S]):-complementara(T,L,S).
/*ALGORITMI DE SORTARE */
sortare_insertie ([],[]).
sortare_insertie ([H|T],R):- sortare_insertie(T,S), insera (H,S,R).
insera (X,[],[X]):-!.
insera (X, [H|T],[X,H|T]):- X<=H,!.
insera (X,[H|T],[H|S]):-insera (X,T,S).
bubble_sort(L,L):- sortata (L),!.
bubble_sort([X,Y|T],R):- Y<=X, bubble_sort([Y,X|T],R),!.
bubble_sort([X,Y|T], R):- bubble_sort([Y|T],S), bubble_sort([X|S],R).
sortata([_]):-!.
sortata([X,Y|T]):- X<=Y, sortata ([Y|T]).
separare([],_,[],[]).
separare([H|T],X,[H|MC],MR):-H<=X,
separare(T,X,MC,MR).
separare([H|T],X,MC,[H|MR]):-H>X,
separare(T,X,MC,MR).
concatenare([],L,L).
concatenare([H|T],L,[H|S]):-concatenare(T,L,S).
quick_sort([],[]).
quick_sort([H|T],LS):-separare(T,H,MC,MR),
quick_sort(MC,MCS),
quick_sort(MR,MRS),
concatenare(MCS,[H|MRS],LS).
inser(X,[],[X]).
inser(X,[H|T],[X,H|T]):-X<H.
inser(X,[H|T],[H|R]):-X>=H,
inser(X,T,R).
inssort([],[]).
inssort([H|T],LS):-inssort(T,TS),
inser(H,TS,LS).
despachetare([],[]).
despachetare([H|T],R):- despachetare(T,S), concatenare(H,S,R).
impachetare([],_,[]).
impachetare([H|T],N,[[H|S]|R]):-M=N-1,
selecteaza(T,M,S,Rest),
impachetare(Rest,N,R).
/*selecteaza([],_,[],[]).*/
selecteaza(L,0,[],L):-!.
selecteaza([H|T],M,[H|S],Rest):-M1=M-1,
selecteaza(T,M1,S,Rest),!.
selecteaza(L,N,L,[]):- lungime(M,L), M<N,!.
elimina_mic([],_,[]):-!.
elimina_mic([H|T],N,R):-H<N, elimina_mic(T,N,R),!.
elimina_mic([H|T],N,[H|S]):- elimina_mic(T,N,S).
citeste_lista_n(N,[]):-N<=0,!.
citeste_lista_n(N,[X|L]):-write("dati componenta: "),
readint(X),nl,N1=N-1,citeste_lista_n(N1,L).
citeste_lista([]):-write("Mai sunt componente [d/n]?"),
readchar(C),C='n',nl,!.
citeste_lista([H|T]):-nl,write("Dati componenta: "),
readint(H),nl,citeste_lista(T).
citeste_lista_liste(N,[]):-N<=0,!.
citeste_lista_liste(N,[X|R]):-nl,nl, write("Citeste o noua lista"),
nl,citeste_lista(X),N1=N-1,citeste_lista_liste(N1,R).
scrie_lista([]):-nl, !.
scrie_lista([H|T]):- write (" ",H),scrie_lista(T).
scrie_llista([]):-!.
scrie_llista([H|T]):- nl,nl,scrie_lista(H),scrie_llista(T).
]]>