Найти все натуральные делители числа (с прологом)

Question

Я хочу создать предикатные делители (X, [Y]), которые верны, если X> 1 и Y - список всех делителей X, начинающихся с X и понижающихся до 1.

Чтомой код сейчас выглядит так:

divisors(1,[1]).
divisors(X,[Y,Z|Ys]) :- 
    X>0,
    Y is X,
    Y>Z, 
    divides(X,[Z|Ys]).

divides(X,[Y,Z|Ys]) :-
    Y>Z, 
    0 is X mod Y, 
    divides(X,[Z|Ys]).
divides(X,[1]).

Но есть несколько проблем с ним:

1. Пролог возвращает ошибку, если запрашивается список (например,? -divisors(10, X).)

2. ? - делители (X, [Y]).Где [Y] - неполный список делителей, верно ...

---

Редактировать Guy Coder

Этот ответ принадлежит ОП и был опубликован вкомментарий ниже.

Перемещение сюда, чтобы другие могли его видеть.

divisors(X,R) :- 
  X > 1, 
  divisors(X,1,[],R). 

divisors(X,D,R,R):-
  D>X.

divisors(N,D0,R0,R) :-
  divisors_0(N,D0,R0,R1), 
  D is D0 + 1, 
  divisors(N,D,R1,R). 

divisors_0(N,D,R0,[D|R0]) :-
  divides(N,D). 

divisors_0(N,D,R0,R0).

divides(N,D) :-
  0 is N mod D.

Оператор также отметил некоторые ошибки в этой версии:

1. Не прекращается, еслиЯ спрашиваю неправильное утверждение, как (10, [1,2,3]).

2. Выдает ошибку, если я спрашиваю утверждение типа (X, [10,5,2,1]).(-> Аргументы недостаточно инициализированы.)

Answer 1

Хотя ответ Уильяма хорош и, вероятно, быстрее, здесь ответ ближе к тому, что вы написали.

divides(N,D) :-
    0 is N mod D.

divisors_0(N,D,R0,[D|R0]) :-
    divides(N,D).

divisors_0(N,D,R0,R0) :-
    \+ divides(N,D).

divisors(_,0,R,R).

divisors(N,D0,R0,R) :-
    divisors_0(N,D0,R0,R1),
    D is D0 - 1,
    divisors(N,D,R1,R).

divisors(X,R) :-
    X > 1,
    divisors(X,X,[],R), !.

Пример:

?- between(1,15,N), divisors(N,Rs).
N = 2,
Rs = [1, 2] ;
N = 3,
Rs = [1, 3] ;
N = 4,
Rs = [1, 2, 4] ;
N = 5,
Rs = [1, 5] ;
N = 6,
Rs = [1, 2, 3, 6] ;
N = 7,
Rs = [1, 7] ;
N = 8,
Rs = [1, 2, 4, 8] ;
N = 9,
Rs = [1, 3, 9] ;
N = 10,
Rs = [1, 2, 5, 10] ;
N = 11,
Rs = [1, 11] ;
N = 12,
Rs = [1, 2, 3, 4, 6, 12] ;
N = 13,
Rs = [1, 13] ;
N = 14,
Rs = [1, 2, 7, 14] ;
N = 15,
Rs = [1, 3, 5, 15].

---

Редактировать

OP изменил свой код, увидел обновление в вопросе и имел некоторые ошибки.

Эта версия устраняет эти ошибки.

divisors(X,R) :-
  (
    var(X)
  ->
    false
  ;
    (
      var(R)
    ->
      X > 1,
      divisors(X,1,[],R)
    ;
      divisors_2(X,R), !
    )
  ).

divisors_2(_,[]).

divisors_2(X,[H|T]) :-
  divides(X,H),
  divisors_2(X,T).

divisors(X,D,R,R):-
  D>X.

divisors(N,D0,R0,R) :-
  divisors_0(N,D0,R0,R1),
  D is D0 + 1,
  divisors(N,D,R1,R).

divisors_0(N,D,R0,[D|R0]) :-
  divides(N,D).

divisors_0(_,_,R0,R0).

divides(N,D) :-
  0 is N mod D.

Первая ошибка: It doesn't terminate if I ask a wrong statement like divisors(10,[1,2,3]).

исправлено путем добавления к делителям / 2

(
  var(R)
->
  X > 1,
  divisors(X,1,[],R)
;
  divisors_2(X,R), !
)

и

divisors_2(_,[]).

divisors_2(X,[H|T]) :-
  divides(X,H),
  divisors_2(X,T).

, которые просто обрабатывают список знаменателей вместо генерации списка.

Вторая ошибка: It throws an error if I ask a statement like divisors(X, [10,5,2,1]). (-> Arguments are not sufficiently initialized.)

устраняется путем дополнительного добавления к divisor/2

divisors(X,R) :-
  (
    var(X)
  ->
    false
  ;
    (
      var(R)
    ->
      X > 1,
      divisors(X,1,[],R)
    ;
      divisors_2(X,R), !
    )
  ).

, который проверяет, является ли первый параметр X переменной, и если да, то простовозвращает false.Другой вариант - создать бесконечный список ответов.Пока возможно, это не было запрошено.

Answer 2

В Прологе весьма распространено использование обратного отслеживания и предложение нескольких решений для одного и того же запроса.Вместо того, чтобы составлять список делителей, мы можем построить предикат, который объединяет второй параметр со всеми делителями.Например:

divisor(N, D) :-
    between(1, N, D),
    0 is N mod D.

Это дает:

?- divisor(12, N).
N = 1 ;
N = 2 ;
N = 3 ;
N = 4 ;
N = 6 ;
N = 12.

Вышеприведенный алгоритм является алгоритмом O (n) : мы сканируем делители, линейные со значениемэлемента, для которого мы хотим получить делители.Мы можем легко улучшить это значение до O (√n) , просканировав до √n , и каждый раз получим как делитель (конечно, если это делитель), так исо-делитель, как:

emitco(D, _, D).
emitco(D, C, C) :-
    dif(D, C).

divisor(N, R) :-
    UB is floor(sqrt(N)),
    between(1, UB, D),
    0 is N mod D,
    C is N / D,
    emitco(D, C, R).

Это все еще дает правильные ответы, но порядок похож на сходящуюся чередующуюся последовательность:

?- divisor(12, N).
N = 1 ;
N = 12 ;
N = 2 ;
N = 6 ;
N = 3 ;
N = 4.

?- divisor(16, N).
N = 1 ;
N = 16 ;
N = 2 ;
N = 8 ;
N = 4 ;
false.

Мы можем получить список делителей следующим образом:используя findall/3 [swi-doc] или setof/3 [swi-doc] .setof/3 будет даже сортировать делители, поэтому мы можем реализовать divisors/2 с точки зрения divisor/2:

divisors(N, Ds) :-
    setof(D, divisor(N, D), Ds).

Например:

?- divisors(2, N).
N = [1, 2].

?- divisors(3, N).
N = [1, 3].

?- divisors(5, N).
N = [1, 5].

?- divisors(12, N).
N = [1, 2, 3, 4, 6, 12].

?- divisors(15, N).
N = [1, 3, 5, 15].

Мы можем использовать reverse/2, чтобы отменить этот результат.