Acerca de:

Este blog contiene los códigos, ejemplos y bases de datos que he usado cuando aprendía acerca de algún tema específico. En lugar de borrarlos (una vez dominado ya el tema), he decidido publicarlos :)

jueves, 17 de marzo de 2016

Calculando el MCD de dos números con el algoritmo de Euclides en Prolog

Esta vez sí estoy usando el algoritmo de Euclides (pero usando restas sucesivas) :D

Blatant Copy/Paste:
La lógica de Prolog es la siguiente: devuelve el valor de retorno en la variable del extremo derecho. La coma es el AND lógico, y el punto y coma el OR lógico. Cada declaración de la función "mcd" equivale a un if.
End of Blatant Copy/Paste

Si el valor en la variable B es 0 ó 1, el algoritmo ignora el valor de A y retorna 0 ó 1 según corresponda. Si no es así, evalúa si A es menor a B, si es así intercambia los valores de A y B, y luego realiza las restas sucesivas como indica el algoritmo. En el algoritmo de Euclides se suele usar un bucle, pero en Prolog se debe utilizar recursividad.

He aquí el código:

mcd(_, 0, 0).
mcd(_, 1, 1).
mcd(A, B, X):- A < B, mcd(B,A,X).
mcd(A, B, X):- N is A - B, N =:= 0, X is B.
mcd(A, B, X):- N is A - B, N =:= B, X is B.
mcd(A, B, X):- N is A-B, N < B, mcd(B, N, X).
mcd(A, B, X):- N is A-B, N > B, mcd(A, N, X).



Estoy usando SWI Prolog 7.2.