LFS - Charlespunk

COMPLICATED

LISTAS Y BÚSQUEDA BINARIA EN PROLOG:

% Autor: lcfb

% Fecha: 21/05/2012

%-------------------------- LISTAS --------------------------------------

%Representacion [6,7,8,9]

%lista vacia = []

%lista recursiva = [X|Y]  X:Cabeza de lista o primero de la lista tipo elemento.

% Y:Cola de lista o sublista tipo lista. Ejemplo [a, sublista]=[a,[b,sublista]].

%l=[4,8,10,2]=[X|Y] donde X=4 y Y=[8,10,2]

%Subguion "_" representa a un elemento de cual no hay necesidad de almacenar innformacion.

%========Operaciones de Lista ============

%es_vacia(l): ¿Esa vacia la lista l?

es_vacia([]).

%longitud(l,long): Long es la longitud de la lista l

longitud([],0):-!.

longitud([_|Y],L):- longitud(Y,L1),L is 1+L1.

%insertar(E,L,P,LR): Insertar el elemento E en la lista L en la posicion P,Lista resultante

insertar(E,L,1,[E|L]):- !.

insertar(E,[X|Y],P,[X|LR]):- P1 is P - 1, insertar(E,Y,P1,LR).

%eliminar(L,P,LR): eliminar el elemento en la posicion P de la list L, Lista Resultante.

eliminar([X|Y],1,Y):- !.

eliminar([X|Y],P,[X|LR]):- P1 is P - 1,eliminar(Y,P1,LR).

%cabeza

cabeza([X|Y],X):- !.

%cola

cola([X|Y],Y):- !.

%ubicacion

ubicacion([X|Y],X,1):-!.

ubicacion([X|Y],E,P):- ubicacion(Y,E,P1),P is P1+1.

%Enesimo(L,P,E): Encuentra el elemento en la posicion P de la lista L

enesimo([],_N,[]):-!.

enesimo([_X|_N],1,[_X]):-!.

enesimo([_X|R],N,S):-M is N-1,enesimo(R,M,S).

%pertenece(X,L):Determina si el elmento X pertenece a la lista L

pertenece(_X,[_X|_Y]).

pertenece(X,[_C|Y]):-pertenece(X,Y).

%sumatoria(L,X): Sum los elementos de la lista L

sumatoria([X],X):-!.

sumatoria([X|Y],S):-sumatoria(Y,T),S is T + X.

%menor(L,X):Muestra el menor elemento en la lista L

menor([X],X).

menor([X|Y],X):- menor(Y,Z), X =< Z.

menor([X|Y],N):- menor(Y,N), N < X.

% OrdenarA(L,LR): Ordena la lista L de forma ascendente

ordenarA([],[]).

ordenarA([X|Y],LR):-ordenarA(Y,Z),insertarO(X,Z,LR).

% concatenar(L1,L2,LR): Concatena la lista 1 y la lista 2

concatenar([],L,L):-!.

concatenar([X|M],L,[X|LR]):-concatenar(M,L,LR).

%Unir(L1,L2,LR): Unir sin crear duplicados

unir([],S,S).

unir(S,[],S).

unir(L1,L2,LR):- concatenar(L1,L2,L),eliminaD(L,LR).

%insertarO(X,Y,LR): Inserta de forma ordenada el elemento X en la lista Y

insertarO(X,[],[X]).

insertarO(X,[Y|Z],[Y|LR]):-X>Y,insertarO(X,Z,LR).

insertarO(X,[Y|Z],[X,Y|Z]):-X=<Y.

%Eliminar Apariciones(L,X,LR): Elimina las apariciones del numero X en la lista L

eliminarA([],_X,[]):-!.

eliminarA([X|M],X,LR):- eliminarA(M,X,LR),!.

eliminarA([R|M],X,[R|LR]):- eliminarA(M,X,LR),!.

%Eliminar Dobles(L1,LR):Elimina los elementos duplicados de la lista 1

eliminaD([],[]):-!.

eliminaD([X|M],LR):- eliminarA(M,X,T),eliminaD(T,Y),concatenar([X],Y,LR).

%DivideListaDesde(L,E,LR): Divide la lista desde el elemento.

divD([X|Y],X,[X|Y]).

divD([X|Y],E,LR):-divD(Y,E,LR).

divH([X,Y|Z],Y,[X]). 

divH([X|Y],E,LR):-divH(Y,E,LS),concatenar([X],LS,LR).

%BusquedaBinaria(L,X): Realiza la busqueda binaria en una lista

busquedaB([X|Y],X).

busquedaB([X|Y],E):- ordenarA([X|Y],LR),longitud(LR,long),

    M is long div 2,enesimo(LR,M,EM),E=EM!,

    E<EM,divH(LR,EM,LD),busquedaB(LD,E).

busquedaB([X|Y],E):- ordenarA([X|Y],LR),longitud(LR,long),

    M is long div 2,enesimo(LR,M,EM),E=EM,

    E>EM,divD(LR,EM,LD),busquedaB(LD,E).

bbinaria(L,P,F,E):-P>F,false.

bbinaria(L,P,F,E):-M is P+F div 2,enesimo(L,M,EM),

E<EM,bbinaria(L,P,M-1,E).

bbinaria(L,P,F,E):-M is P+F div 2,enesimo(L,M,EM),

E<EM,bbinaria(L,M+1,F,E).

bbinaria(L,P,F,E):-M is P+F div 2,enesimo(L,M,[E]).

%Inlcusion(L1,L2): Determina si la lista 1 esta incluida en la lista 2

inclusion([],V).

inclusion([X|Y1],[X|Y2]) :- inclusion(Y1,Y2).

inclusion([X1|Y1],[X2|Y2]) :- X2<X1,inclusion([X1|Y1],Y2).

%Diferencia(L1,L2,LR): Determina la diferencia de la primera con la segunda.

diferencia(L1,L2,R):-setof(X, (pertenece(X,L1), not(pertenece(X,L2))), R).

%DifS(L1,L2,LR): Determina la diferencia simetrica de las listas.

difS(L1,L2,R):-diferencia(L1,L2,R1),diferencia(L2,L1,R2),concatenar(R1,R2,R).

PROGRAMACIÓN EN PROLOG:

Algoritmos generales:


% Autor: lcfb
% Fecha: 14/05/2012

%MCD algoritmmo de  euclides
%mcd(M,N,Y) : Y es el MCD de M  y N
mcd(M,N,N):- X is M mod N, X=0,!.
mcd(M,N,Y):- X is M mod N, mcd(N,X,Y).

%MCD5 mcd de 5 cifras
mcd5(M,N,O,P,Q,Y):-  mcd(M,N,A),mcd(O,P,B),mcd(A,B,C),mcd(Q,C,Y).

%Suma de cifras(N,S): S es la suma de cifras de N
suma_cifras(N,N):- N<10,!.
suma_cifras(N,S):- C is N // 10,
                   R is N mod 10,
                   suma_cifras(C,S1),
                   S is S1+R.

%Decimal a Binario:
decimal_binario(D,D):- D<2,!.
decimal_binario(D,B):- R is D mod 2,C is D // 2, decimal_binario(C,B1),B is B1*10+R.

%Cualquier base a decimal:
base_decimal(N,B,N):- N<B,!.
base_decimal(N,B,D):- R is N mod 10, C is N // 10,base_decimal(C,B,D1),D is D1*B+R.




%Base a base
 base_base(N,B1,B2,N):- N<B2,!.
 base_base(N,B1,B2,S):- base_decimal(N,B1,D),D is N,R is N mod B2, C is N // B2
                    , base_base(C,B1,B2,S1),S is S1*10+R.

%Suma de Numeros
 num_exp(N,S):- N=1, !, write(1).
 num_exp(N,S):- R is N mod 2, C is N // 2,num_exp(C,S1), S is S1,write('+').