Пролог - получить факторы для данного числа не останавливается?

Мне нужно найти факторы данного числа, например:

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

Код:

% 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).

Но когда я бегу divisors2(40,RR). Я получаю бесконечный цикл, и на экране ничего не отображается.

Зачем?

С уважением

Источник

3 ответа

Решение

У вас есть ошибка здесь

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

Если Z равен нулю, то S = [H|W], иначе S = W.

Источник

Вы спрашиваете, почему вы получаете бесконечный цикл для запроса divisors2(40,R), Я почти хотел объяснить вам это с помощью среза ошибки. Увы...

... ответ: нет, вы не получите бесконечный цикл! И ваша программа тоже находит ответ. Это

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

что выглядит разумным для меня. Они расположены в порядке возрастания, и вы хотели, чтобы список по убыванию, но кроме этого, это идеальный ответ. Без шуток. Однако я подозреваю, что вы недостаточно терпеливы, чтобы получить ответ. Для 36 мне понадобилось:

?- 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]

Довольно необычно... для списка с не более чем 36 скудными целыми числами Прологу потребовалось 10 744 901 605 выводов, то есть менее 2 34. Это звонит в колокол? В любом случае, есть проблемы с вашей программой. На самом деле есть две совершенно самостоятельные проблемы. Как мы можем их найти?

Может быть, мы смотрим не на ту сторону. Просто вернитесь к запросу. Нашей первой ошибкой было то, как мы использовали уровень Пролога. Мы были очень впечатлены, чтобы получить ответ. Но Пролог предложил нам дальнейшие ответы! По факту:

?- 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] ...

Это становится слишком утомительным. Может быть, достаточно крошечного примера?

?- 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.

Более, чем достаточно! Может быть, мы придерживаемся минимального примера [] и повторим это:

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

Понятно, что это не то, что мы ожидали. Мы хотели, чтобы это потерпело неудачу. Как локализовать проблему? В Прологе есть одна общая стратегия отладки:

Если цель слишком общая, специализируйте программу.

Мы можем специализировать программу, добавляя дополнительные цели, чтобы вышеуказанный запрос все еще был успешным. Я добавлю false и немного (=)/2 цели. false Это особенно интересно, потому что он стирает весь пункт:

? - делители2(6,[]).

диапазон (I, I, [I]): - I = 6.
диапазон (I, K, [I | L]): - K = 6,
   Я <К,
   I1 это I + 1,
   Диапазон (I1, K, L).

делители1 ([], [], X): - K = 6.
делители1([H|T],S,X):- неверно,
   divisors1 (Т,W, Х),
   Z является X mod H,
   Z = 0,
   S = [H | W].
делители1 ([_ | T], S, X): - S = [], X = 6,
   divisors1(Т,S,X).

делители2(X, Результат): - X = 6, Результат = [].
   Диапазон (1, Х,Result1),
   divisors1(Result1, результат, X).

Где-то в оставшейся части что-то слишком общее! На самом деле рекурсивное правило divisors1/3 слишком общий. Эта ваша новая модифицированная программа называется ломтик, который является специализацией нашей оригинальной программы.

Несколько способов исправить это, самый наивный способ - добавить соответствующее условие следующим образом:

divisors1 ([], [], _).
divisors1([H|T],S,X):-
   divisors1 (Т,W, Х),
   0 =:= Х мод Н,
   S=[H|W].
divisors1([H|T],S,X):-
   divisors1(Т,S,X),
   0 =\= Х мод Х.

Однако производительность программы не улучшилась. Чтобы увидеть это, я снова специализируюсь на этой программе:

делители1([],[],_):- неверно.
divisors1([H|T],S,X):-
   делители1(T,W,X), ложь,
   0 =: = Х мод Н,
   S = [H | W].
divisors1([H|T],S,X):-
   делители1(T,S,X), ложь,
   0 = \ = Х мод Н.

Таким образом: независимо от того, что находится за false эта программа попробует хотя бы 3 * 2^N умозаключения для списка длины N,

Ставя рекурсивные цели в последнюю очередь, мы можем избежать этого.

Источник

Если вы исправите свой диапазон (используйте сокращение в конце конца рекурсии), вы получите его вроде как работающий. Вам не сразу удастся найти все делители.

Решение, использующее вашу общую идею, а также встроенные функции между /3 и bagof/3 (чтобы немного упростить набор текста):

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

Обратите внимание, что это решение возвращает делители в порядке возрастания.

Источник
Другие вопросы по тегам