prolog - Prólogo: ¿los factores para un número dado no se detienen?

failure-slice program-slicing

Question

Necesito encontrar los factores de un número dado, por ejemplo:

?- divisors2(40,R).
R = [40,20,10,8,5,4,2,1].

El código :

% get all the numbers between 1-X
range(I,I,[I]).
range(I,K,[I|L]) :- I < K, I1 is I + 1, range(I1,K,L).
% calc the modulo of each element with the given number :
% any x%y=0 would be considered as part of the answer
divisors1([],[],_).
divisors1([H|T],S,X):-divisors1(T,W,X),Z is X mod H,Z==0,S=[H|W].
divisors1([_|T],S,X):-divisors1(T,S,X).
divisors2(X,Result) :-range(1,X,Result1),divisors1(Result1,Result,X).

Pero cuando ejecuto divisors2(40,RR). Tengo un ciclo infinito y no se presenta nada en la pantalla.

Por qué ?

Saludos

Answer 1

Si corrige su rango (use un corte para la cláusula de final de recursión), obtendrá algo de trabajo. Sin embargo, no logras encontrar todos los divisores inmediatamente.

Una solución que utiliza su idea general, pero también integraciones entre / 3 y bagof / 3 (para facilitar la escritura):

divisors(X, Divs) :- bagof(D, divs(X,D), Divs).
divs(X,D) :- between(1,X,D), 0 is X mod D.

Tenga en cuenta que esta solución devuelve los divisores en orden creciente.

Answer 2

Tienes un error aquí

divisors1([H|T],S,X):-
divisors1(T,W,X),
Z is X mod H,
Z==0,S=[H|W]. <=== here

Si Z es cero, entonces S = [H | W] sino S = W.

Answer 3

Usted está preguntando por qué obtiene un bucle infinito para los divisors2(40,R) consulta2 divisors2(40,R) . Casi quería explicarte esto usando un slice de falla . Alas ...

... la respuesta es: ¡no, no obtienes un ciclo infinito! Y tu programa también encuentra una respuesta. Sus

R = [1, 2, 4, 5, 8, 10, 20, 40]

lo cual me parece razonable Están en orden ascendente, y querías una lista descendente, pero aparte de eso, esa es una respuesta perfecta. En serio. Sin embargo, sospecho que no fue lo suficientemente paciente para obtener la respuesta. Para 36 necesitaba:

?- time(divisors2(36,R)).
% 10,744,901,605 inferences, 2248.800 CPU in 2252.918 seconds (100% CPU, 4778061 Lips)
R = [1, 2, 3, 4, 6, 9, 12, 18, 36]

Muy inusual ... para una lista con un máximo de 36 enteros exiguos Prolog necesitaba 10 744 901 605 inferencias, es decir, menos de 2 ³⁴ . ¿Suena esto? En cualquier caso, hay problemas con su programa. De hecho, hay dos problemas bastante independientes. ¿Cómo podemos encontrarlos?

Tal vez estamos viendo el lado equivocado. Solo regrese a la consulta. Nuestro primer error fue cómo utilizamos el nivel de Prolog. Nos impresionó mucho recibir una respuesta. ¡Pero Prolog nos ofreció más respuestas! De hecho:

?- time(divisors2(36,R)).
% 10,744,901,605 inferences, 2248.800 CPU in 2252.918 seconds (100% CPU, 4778061 Lips)
R = [1, 2, 3, 4, 6, 9, 12, 18, 36] ;
% 10 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 455892 Lips)
R = [1, 2, 3, 4, 6, 9, 12, 18] ;
% 917,508 inferences, 0.192 CPU in 0.192 seconds (100% CPU, 4789425 Lips)
R = [1, 2, 3, 4, 6, 9, 12, 36] ...

Esto se vuelve demasiado tedioso. Tal vez un pequeño ejemplo sea suficiente?

?- divisors2(6,R).
R = [1, 2, 3, 6] ;
R = [1, 2, 3] ;
R = [1, 2, 6] ;
R = [1, 2] ;
R = [1, 3, 6] ;
R = [1, 3] ;
R = [1, 6] ;
R = [1] ;
R = [2, 3, 6] ;
R = [2, 3] ;
R = [2, 6] ;
R = [2] ;
R = [3, 6] ;
R = [3] ;
R = [6] ;
R = [] ;
false.

¡Mas que suficiente! Tal vez nos apeguemos al ejemplo mínimo [] y lo replanteemos:

?- divisors2(6,[]).
true ;
false.

Claramente, eso no es lo que esperábamos. Queríamos que esto fallara. ¿Cómo localizar el problema? Hay una estrategia de depuración general en Prolog:

Si un objetivo es demasiado general, especialícelo.

Podemos especializar el programa agregando objetivos adicionales de modo que la consulta anterior aún tenga éxito . Agregaré objetivos false y algunos (=)/2 . false es particularmente interesante porque borra una cláusula completa:

?- divisors2(6,[]). range(I,I,[I]) :- I = 6. range(I,K,[I|L]) :- K = 6, I < K, I1 is I + 1, range(I1,K,L). divisors1([],[],X) :- K=6. divisors1([H|T],S,X):- false, divisors1(T,W,X), Z is X mod H, Z=0, S=[H|W]. divisors1([_|T],S,X):- S = [], X = 6, divisors1(T,S,X). divisors2(X,Result) :- X = 6, Result = []. range(1,X,Result1), divisors1(Result1,Result,X).

En algún lugar de la parte restante, ¡algo es demasiado general! De hecho, la regla recursiva de los divisors1/3 es demasiado general. Este nuevo programa modificado suyo se llama segmento que es una especialización de nuestro programa original.

Varias formas de solucionar esto, la forma más ingenua es agregar la condición correspondiente de esta manera:

divisors1([],[],_). divisors1([H|T],S,X):- divisors1(T,W,X), 0 =:= X mod H, S=[H|W]. divisors1([H|T],S,X):- divisors1(T,S,X), 0 =/= X mod H.

Sin embargo, el rendimiento del programa no mejoró. Para ver esto, volveré a especializar este programa:

divisors1([],[],_) :- false. divisors1([H|T],S,X):- divisors1(T,W,X), false, 0 =:= X mod H, S=[H|W]. divisors1([H|T],S,X):- divisors1(T,S,X), false, 0 =/= X mod H.

Por lo tanto: no importa qué hay detrás de lo false , este programa intentará al menos 3 * 2^N inferencias para una lista de longitud N

Al poner los objetivos recursivos al final podemos evitar esto.