API tools faq
paste
Advertisement
ganryu

Pco2

ganryu
May 18th, 2018
201
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Prolog 12.85 KB | None | 0 0
raw download clone embed print report
  1. % Ejercicio 1a
  2. % Comprobar si una lista de elementos constituye un conjunto válido
  3. % Un conjunto es una lista de elementos que no contiene elementos repetidos
  4.  
  5. % pertenece(Lista, Elemento): true si Elemento esta en Lista
  6. pertenece([], _) :- fail.
  7. pertenece([E|_], E) :- !.
  8. pertenece([_|L], E) :- pertenece(L, E).
  9.  
  10. % esConjunto(Lista): true si Lista es un conjunto
  11. esConjunto([]) :- !.
  12. esConjunto([E|L]) :- not(pertenece(L, E)), esConjunto(L).
  13.  
  14. conjunto(C, []) :- esConjunto(C), !.
  15. conjunto(C, [H|L]) :- pertenece(C, H), conjunto(C, L).
  16.  
  17. % 1b. Determina si un elemento pertenece a un conjunto
  18. % perteneceAConjunto(Conjunto, Elemento): Elemento se encuentra en Conjunto y Conjunto es un Conjunto
  19. perteneceAConjunto(C, E) :- esConjunto(C), pertenece(C, E).
  20.  
  21. % 1c. Incorpora un elemento a un conjunto
  22. % insertarEnConjunto(C, E, CE): CE es el resultado de insertarEnConjunto E en C
  23.  
  24. insertarEnConjunto(C, E, C) :- perteneceAConjunto(C, E), !.
  25. insertarEnConjunto(C, E, C2) :- append(C, [E], C2).
  26.  
  27. % 1d. Unir dos conjuntos
  28. % unirConjuntos(C, C2, U): U es el resultado de la union entre C y C2
  29. unirConjuntos([], [], []) :- !.
  30. unirConjuntos([], C, C) :- esConjunto(C), !.
  31. unirConjuntos([H|T], C, U) :-
  32.     unirConjuntos(T, C, U2),
  33.     insertarEnConjunto(U2, H, U).
  34.  
  35. % 1e. Intersectar dos conjuntos
  36. % intersectarConjuntos(C, C2, I): I es la intersección entre C y C2
  37. intersectarConjuntos([], C, []) :- esConjunto(C), !.
  38.  
  39. intersectarConjuntos([H|T], C, I) :-
  40.     not(perteneceAConjunto(C, H)),
  41.     intersectarConjuntos(T, C, I),
  42.     !.
  43.  
  44. intersectarConjuntos([H|T], C, I) :-
  45.     intersectarConjuntos(T, C, I2),
  46.     insertarEnConjunto(I2, H, I).
  47.  
  48. % 1f. Calcular la diferencia entre dos conjuntos
  49. % diferencia(C, C2, D): D es la diferencia entre C2 y C
  50. diferencia(_, [], []) :- !.
  51.  
  52. diferencia(C, [H|T], D) :-
  53.     perteneceAConjunto(C, H),
  54.     diferencia(C, T, D),
  55.     !.
  56.  
  57. diferencia(C, [H|T], D) :-
  58.     diferencia(C, T, D2),
  59.     insertarEnConjunto(D2, H, D).
  60.  
  61. % 1h. Dada una lista de elementos con repeticiones, construir un conjunto que contenga todos los elementos de esa lista.
  62. % convertir(L, C): C es el conjunto formado con los elementos sin repeticiones de la lista L
  63.  
  64. convertir([], []) :- !.
  65. convertir([H|T], C) :- convertir(T, C2), insertarEnConjunto(C2, H, C).
  66.  
  67. % 2. Definir predicados recursivos para ordenar:
  68. %   1. Una lista de números
  69.  
  70. % pivotNros(P, L, I, D):
  71. %   la magia del quicksort se encuentra aquí, particiona el array
  72. %   de palabras L en los arrays I y D, I contiene los números que
  73. %   se encuentran antes del número P y D los números que se
  74. %   encuentran después.
  75. pivotNros(_, [], [], []) :- !.
  76. pivotNros(P, [H|T], [H|I], D) :- H =< P, !, pivotNros(P, T, I, D).
  77. pivotNros(P, [H|T], I, [H|D]) :- H > P, !, pivotNros(P, T, I, D).
  78.  
  79. % quicksortNros(L, R): R es el resultado de ordenar el array de números L
  80. quicksortNros([], []).
  81. quicksortNros([P|L], R) :-
  82.     pivotNros(P, L, I, D),
  83.     quicksortNros(I, I2),
  84.     quicksortNros(D, D2),
  85.     append(I2, [P|D2], R).
  86.  
  87. %   2. Una lista de palabras (una palabra se representa como una lista de carácteres)
  88.  
  89. % compararPalabras(P1, P2):
  90. %   devuelve true si P1 se encuentra antes de P2
  91. %   en orden lexicográfico
  92. compararPalabras([], []) :- fail.
  93. compararPalabras([], _) :- !.
  94. compararPalabras(_, []) :- !.
  95. compararPalabras([H|T], [H|T2]) :- compararPalabras(T, T2).
  96. compararPalabras([H|_], [H2|_]) :- char_code(H, X), char_code(H2, X2), X < X2.
  97.  
  98. % pivotPalabras(P, L, I, D):
  99. %   particiona el array de palabras L en los arrays I y D,
  100. %   I contiene las palabras que se encuentran antes de
  101. %   la palabra P y D las palabras que se encuentran después
  102. %   (en orden lexicográfico).
  103. pivotPalabras(_, [], [], []) :- !.
  104. pivotPalabras(P, [H|T], [H|I], D) :- compararPalabras(H, P), !, pivotPalabras(P, T, I, D).
  105. pivotPalabras(P, [H|T], I, [H|D]) :- compararPalabras(P, H), !, pivotPalabras(P, T, I, D).
  106.  
  107. % quicksortPalabras(L, R):
  108. %   R es el resultado de ordenar en orden lexicográfico las palabras
  109. %   que se encuentran en el array L.
  110. quicksortPalabras([], []).
  111. quicksortPalabras([P|L], R) :-
  112.     pivotPalabras(P, L, I, D),
  113.     quicksortPalabras(I, I2),
  114.     quicksortPalabras(D, D2),
  115.     append(I2, [P|D2], R).
  116.  
  117. % 5. Definir eval
  118.  
  119. % unionExclusiva(C, C2, U): U es el conjunto resultado de la unión exclusiva entre C y C2.
  120. unionExclusiva(C, C2, U) :-
  121.     diferencia(C, C2, D1),
  122.     diferencia(C2, C, D2),
  123.     unirConjuntos(D1, D2, U).
  124.  
  125. eval(E, E) :- esConjunto(E).
  126. eval(A+B, R) :- eval(A, R1), eval(B, R2), unirConjuntos(R1, R2, R).
  127. eval(A/B, R) :- eval(A, R1), eval(B, R2), unionExclusiva(R1, R2, R).
  128. eval(A-B, R) :- eval(A, R1), eval(B, R2), diferencia(R2, R1, R).
  129. eval(A*B, R) :- eval(A, R1), eval(B, R2), intersectarConjuntos(R1, R2, R).
  130.  
  131. % 8 Árbol
  132.  
  133. % esArbol(A): devuelve si A es un árbol
  134. esArbol(#).
  135. esArbol(t(_, B, C)) :- esArbol(B), esArbol(C).
  136.  
  137. % crearArbolVacio(X): crea un arbol vacío y lo retorna en X
  138. crearArbolVacio(#).
  139.  
  140. % insertar(A, V, A2): A2 es el resultado de ingresar el valor V en el árbol A
  141. insertar(#, V, t(V, #, #)).
  142. insertar(t(V, I, D), V, t(V, I, D)) :- !.
  143. insertar(t(R, I, D), V, t(R, I, D2)) :-
  144.     V > R,
  145.     !,
  146.     insertar(D, V, D2).
  147.  
  148. insertar(t(R, I, D), V, t(R, I2, D)) :-
  149.     V < R,
  150.     !,
  151.     insertar(I, V, I2).
  152.  
  153. anterior(V, t(V, I, #), I) :- !.
  154. anterior(V, t(P, I, D), t(P, I, D2)) :- anterior(V, D, D2).
  155.  
  156. % eliminar(A, V, A2): A2 es el árbol resultante de eliminar el nodo con el valor V del árbol A
  157. eliminar(#, _, #).
  158. eliminar(t(V, I, #), V, I) :- !.
  159. eliminar(t(V, #, D), V, D) :- !.
  160. eliminar(t(V, I, D), V, t(A, I2, D)) :- !, anterior(A, I, I2).
  161. eliminar(t(R, I, D), V, t(R, I2, D)) :- V < R, !, eliminar(I, V, I2).
  162. eliminar(t(R, I, D), V, t(R, I, D2)) :- V > R, !, eliminar(D, V, D2).
  163.  
  164. % altura(A, X): X es la altura del árbol A
  165. altura(#, 0).
  166. altura(t(_, #, #), 1) :- !.
  167. altura(t(_, I, D), A) :- altura(I, AI), altura(D, AD), A is max(AI, AD) + 1.
  168.  
  169. % balanceado(A): true si A esta balanceado
  170. balanceado(#).
  171. balanceado(t(_, I, D)) :-
  172.     balanceado(I),
  173.     balanceado(D),
  174.     altura(I, AI),
  175.     altura(D, AD),
  176.     abs(AI - AD) < 2.
  177.  
  178. :- begin_tests(pertenece).
  179. test(pertenece) :- pertenece([1, 2, 3], 1).
  180. test(pertenece) :- pertenece([1, 2, 3], 2).
  181. test(pertenece) :- pertenece([1, 2, 3], 3).
  182. test(pertenece, [fail]) :- pertenece([], 1).
  183. test(pertenece, [fail]) :- pertenece([1, 2, 3], 4).
  184. :- end_tests(pertenece).
  185.  
  186. :- begin_tests(esConjunto).
  187. test(esConjunto) :- esConjunto([]).
  188. test(esConjunto) :- esConjunto([1]).
  189. test(esConjunto) :- esConjunto([1, 2, 3]).
  190. test(esConjunto, [fail]) :- esConjunto([1, 2, 1]).
  191. :- end_tests(esConjunto).
  192.  
  193. :- begin_tests(perteneceAConjunto).
  194. test(perteneceAConjunto) :- perteneceAConjunto([1, 2, 3], 1).
  195. test(perteneceAConjunto) :- perteneceAConjunto([1, 2, 3], 2).
  196. test(perteneceAConjunto) :- perteneceAConjunto([1, 2, 3], 3).
  197. test(perteneceAConjunto, [fail]) :- perteneceAConjunto([], 1).
  198. test(perteneceAConjunto, [fail]) :- perteneceAConjunto([1, 2, 3], 4).
  199. test(perteneceAConjunto, [fail]) :- perteneceAConjunto([1, 1, 2, 3], 1).
  200. test(perteneceAConjunto, [fail]) :- perteneceAConjunto([1, 2, 3, 4, 3], 1).
  201. :- end_tests(perteneceAConjunto).
  202.  
  203. :- begin_tests(insertarEnConjunto).
  204. test(insertarEnConjunto) :- insertarEnConjunto([], 1, [1]).
  205. test(insertarEnConjunto) :- insertarEnConjunto([1, 2, 3], 1, [1, 2, 3]).
  206. test(insertarEnConjunto) :- insertarEnConjunto([1, 2, 3], 2, [1, 2, 3]).
  207. test(insertarEnConjunto) :- insertarEnConjunto([1, 2, 3], 3, [1, 2, 3]).
  208. test(insertarEnConjunto) :- insertarEnConjunto([1, 2, 3], 4, [1, 2, 3, 4]).
  209. test(insertarEnConjunto) :-
  210.     E = 4,
  211.     insertarEnConjunto([1, 2, 3], E, [1, 2, 3, 4]).
  212. test(insertarEnConjunto) :-
  213.     C = [1, 2, 3],
  214.     insertarEnConjunto(C, 4, [1, 2, 3, 4]).
  215. :- end_tests(insertarEnConjunto).
  216.  
  217. :- begin_tests(unirConjuntos).
  218. test(unirConjuntos) :- unirConjuntos([], [], []).
  219.  
  220. test(unirConjuntos) :-
  221.     unirConjuntos([1, 2], [3, 4], L),
  222.     conjunto(L, [1, 2, 3, 4]).
  223.  
  224. test(unirConjuntos) :-
  225.     unirConjuntos([1, 2], [1, 2], L),
  226.     conjunto(L, [1, 2]).
  227.    
  228. test(unirConjuntos) :-
  229.     unirConjuntos([1, 2], [1, 2, 3], L),
  230.     conjunto(L, [1, 2, 3]).
  231.  
  232. test(unirConjuntos) :-
  233.     unirConjuntos([1, 2, 3, 4], [2], L),
  234.     conjunto(L, [1, 2, 3, 4]).
  235.  
  236. test(unirConjuntos) :-
  237.     unirConjuntos([1, 2, 3, 4], [2, 3, 4, 5], L),
  238.     conjunto(L, [1, 2, 3, 4, 5]).
  239.  
  240. :- end_tests(unirConjuntos).
  241.  
  242. :- begin_tests(intersectarConjuntos).
  243. test(intersectarConjuntos) :- intersectarConjuntos([], [], []).
  244.  
  245. test(intersectarConjuntos) :- intersectarConjuntos([1, 2], [3, 4], []).
  246.  
  247. test(intersectarConjuntos) :- intersectarConjuntos([1, 2], [1, 2], L),
  248.     conjunto(L, [1, 2]).
  249.    
  250. test(intersectarConjuntos) :-
  251.     intersectarConjuntos([1, 2], [1, 2, 3], L),
  252.     conjunto(L, [1, 2]),
  253.     not(conjunto(L, [1, 2, 3])).
  254.  
  255. test(intersectarConjuntos) :-
  256.     intersectarConjuntos([1, 2, 3, 4], [2], L),
  257.     conjunto(L, [2]),
  258.     not(perteneceAConjunto(L, 1)),
  259.     not(perteneceAConjunto(L, 3)),
  260.     not(perteneceAConjunto(L, 4)).
  261.  
  262. test(intersectarConjuntos) :-
  263.     intersectarConjuntos([1, 2, 3, 4], [2, 3, 4, 5], L),
  264.     conjunto(L, [2, 3, 4]),
  265.     not(perteneceAConjunto(L, 1)),
  266.     not(perteneceAConjunto(L, 5)).
  267. :- end_tests(intersectarConjuntos).
  268.  
  269. :- begin_tests(diferencia).
  270. test(diferencia) :- diferencia([], [], []).
  271.  
  272. test(diferencia) :-
  273.     diferencia([1, 2], [3, 4], L),
  274.     conjunto(L, [3, 4]),
  275.     not(perteneceAConjunto(L, 1)),
  276.     not(perteneceAConjunto(L, 2)).
  277.  
  278. test(diferencia) :- diferencia([1, 2], [1, 2], []).
  279.    
  280. test(diferencia) :-
  281.     diferencia([1, 2], [1, 2, 3], L),
  282.     perteneceAConjunto(L, 3),
  283.     not(perteneceAConjunto(L, 2)),
  284.     not(perteneceAConjunto(L, 1)).
  285.  
  286. test(diferencia) :- diferencia([1, 2, 3, 4], [2], []).
  287.  
  288. test(diferencia) :-
  289.     diferencia([1, 2, 3, 4], [2, 3, 4, 5], L),
  290.     perteneceAConjunto(L, 5),
  291.     not(perteneceAConjunto(L, 1)),
  292.     not(perteneceAConjunto(L, 2)),
  293.     not(perteneceAConjunto(L, 3)),
  294.     not(perteneceAConjunto(L, 4)).
  295. :- end_tests(diferencia).
  296.  
  297. :- begin_tests(convertir).
  298. test(convertir) :- convertir([], []).
  299. test(convertir) :-
  300.     convertir([1, 2, 3], C),
  301.     conjunto(C, [1, 2, 3]).
  302.  
  303. test(convertir) :-
  304.     convertir([1, 2, 3, 1, 2], C),
  305.     conjunto(C, [1, 2, 3]).
  306. :- end_tests(convertir).
  307.  
  308. :- begin_tests(eval).
  309. test(eval) :- eval([1,2,3], [1, 2, 3]).
  310. test(eval) :-
  311.     eval([1,2]+[3,4], A),
  312.     unirConjuntos([1, 2], [3, 4], A).
  313.  
  314. test(eval) :-
  315.     eval(([1,2]+[3,4])+[5,6], A),
  316.     unirConjuntos([1, 2], [3, 4], R),
  317.     unirConjuntos(R, [5, 6], A).
  318.  
  319. test(eval) :-
  320.     eval(([a,b,c,d,e]/[d,e,f,g,h])+([h,i,j,k,l]*([j,k,l,m,n,t,u]-[m,n])), A),
  321.     conjunto(A, [a,b,c,f,g,h,j,k,l]).
  322. :- end_tests(eval).
  323.  
  324. :- begin_tests(arbol).
  325. % tests para crear árboles e insertar elementos
  326. test(arbol) :-
  327.     crearArbolVacio(A),
  328.     insertar(A, 30, t(30, #, #)).
  329.  
  330. test(arbol) :-
  331.     crearArbolVacio(A),
  332.     insertar(A, 30, A2),
  333.     insertar(A2, 15, t(30, t(15, #, #), #)).
  334.  
  335. test(arbol) :-
  336.     crearArbolVacio(A),
  337.     insertar(A, 30, A2),
  338.     insertar(A2, 15, A3),
  339.     insertar(A3, 7, A4),
  340.     insertar(A4, 31, t(30, t(15, t(7, #, #), #), t(31, #, #))).
  341.  
  342. test(arbol) :-
  343.     crearArbolVacio(A),
  344.     insertar(A, 30, A2),
  345.     insertar(A2, 15, A3),
  346.     insertar(A3, 15, A4),
  347.     insertar(A4, 31, t(30, t(15, #, #), t(31, #, #))).
  348.  
  349. % tests para eliminar elementos del árbol
  350. test(arbol) :-
  351.     crearArbolVacio(A),
  352.     insertar(A, 30, A2),
  353.     insertar(A2, 15, A3),
  354.     insertar(A3, 7, A4),
  355.     insertar(A4, 31, A5),
  356.     eliminar(A5, 7, t(30, t(15, #, #), t(31, #, #))).
  357.  
  358. test(arbol) :-
  359.     crearArbolVacio(A),
  360.     insertar(A, 30, A2),
  361.     insertar(A2, 15, A3),
  362.     insertar(A3, 7, A4),
  363.     insertar(A4, 31, A5),
  364.     eliminar(A5, 15, t(30, t(7, #, #), t(31, #, #))).
  365.  
  366. % tests para la altura del árbol
  367. test(arbol) :-
  368.     crearArbolVacio(A),
  369.     insertar(A, 30, A2),
  370.     insertar(A2, 15, A3),
  371.     insertar(A3, 7, A4),
  372.     insertar(A4, 31, A5),
  373.     altura(A5, 3).
  374.  
  375. test(arbol) :-
  376.     crearArbolVacio(A),
  377.     insertar(A, 30, A2),
  378.     insertar(A2, 15, A3),
  379.     insertar(A3, 7, A4),
  380.     insertar(A4, 31, A5),
  381.     insertar(A5, 32, A6),
  382.     insertar(A6, 33, A7),
  383.     insertar(A7, 34, A8),
  384.     altura(A8, 5).
  385.  
  386. % tests para ver si un árbol esta balanceado
  387. test(arbol) :- balanceado(#).
  388.  
  389. test(arbol) :-
  390.     crearArbolVacio(A),
  391.     insertar(A, 30, A2),
  392.     insertar(A2, 15, A3),
  393.     insertar(A3, 7, A4),
  394.     insertar(A4, 31, A5),
  395.     balanceado(A5).
  396.  
  397. test(arbol) :-
  398.     crearArbolVacio(A),
  399.     insertar(A, 30, A2),
  400.     insertar(A2, 15, A3),
  401.     insertar(A3, 7, A4),
  402.     insertar(A4, 31, A5),
  403.     insertar(A5, 32, A6),
  404.     insertar(A6, 33, A7),
  405.     insertar(A7, 34, A8),
  406.     not(balanceado(A8)).
  407. :- end_tests(arbol).
  408.  
  409. :- begin_tests(qsort).
  410. test(qsort) :- quicksortNros([1, 2, 3], [1, 2, 3]).
  411. test(qsort) :- quicksortNros([], []).
  412. test(qsort) :- quicksortNros([3, 2, 1], [1, 2, 3]).
  413. test(qsort) :- quicksortNros([5, 6, 1, 3, 4, 7], [1, 3, 4, 5, 6, 7]).
  414.  
  415. test(qsort) :- quicksortPalabras([], []).
  416. test(qsort) :- quicksortPalabras([
  417.     [c,a,s,a,m,i,e,n,t,o],
  418.     [a,r,b,o,l],
  419.     [c,a,s,a]
  420. ], [
  421.     [a,r,b,o,l],
  422.     [c,a,s,a],
  423.     [c,a,s,a,m,i,e,n,t,o]
  424. ]).
  425. test(qsort) :- quicksortPalabras([
  426.     [a,a],
  427.     [a,a],
  428.     [a,c]
  429. ], [
  430.     [a,a],
  431.     [a,a],
  432.     [a,c]
  433. ]).
  434. test(qsort) :- quicksortPalabras([
  435.     [a,a],
  436.     [a,b],
  437.     [a,c]
  438. ], [
  439.     [a,a],
  440.     [a,b],
  441.     [a,c]
  442. ]).
  443. :- end_tests(qsort).
  444.  
  445. :- run_tests.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!