Определение того, является ли набор аддитивным по модулю K в Прологе

Я новичок в Прологе, и я решил, что могу попытаться написать простой тест, чтобы проверить, является ли набор целых чисел по модулю K (L) группой. Я начал с попытки выяснить, является ли указанный набор аддитивным, т.е. если сумма любых двух элементов L также является элементом L.

Я написал следующее:

group(A,K):-member(B,A),member(C,A),As is B+C, Bs is mod(As,K), member(Bs,A).

Затем я попробовал это с этим:

trace. group([0,1,2],3).

Это, естественно, дает все возможные суммы и правильно отвечает, что ответ верен для всех из них.

Но после всех этих случаев он наконец печатает следующее:

  1    1  Redo: group([0,1,2],3) ? 
  6    2  Redo: member(1,[0,1,2]) ? 
  6    2  Fail: member(1,[0,1,2]) ? 
  1    1  Fail: group([0,1,2],3) ?
  no

Почему программа проверяет именно этот последний случай, который мне кажется бессмысленным?

Последний случай перед этим:

  1    1  Redo: group([0,1,2],3) ? 
  6    2  Redo: member(0,[0,1,2]) ? 
  6    2  Fail: member(0,[0,1,2]) ? 
  3    2  Redo: member(1,[0,1,2]) ? 
  3    2  Exit: member(2,[0,1,2]) ? 
  4    2  Call: _158 is 2+2 ? 
  4    2  Exit: 4 is 2+2 ? 
  5    2  Call: _186 is 4 mod 3 ? 
  5    2  Exit: 1 is 4 mod 3 ? 
  6    2  Call: member(1,[0,1,2]) ? 
  6    2  Exit: member(1,[0,1,2]) ? 
  1    1  Exit: group([0,1,2],3) ? 

  true

который делает то, что должен.


addition discrete-mathematics prolog
person Valtteri    schedule 15.11.2012    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Использование трассировщика для такой цели не очень полезно. Он показывает вам много деталей, которые не имеют значения. Вместо этого сконцентрируйтесь на правильной формулировке проблемы. Сконцентрируйтесь на осмысленных именах. Вы используете A для набора и B и C для элементов. Это можно улучшить!

В настоящее время вы тестируете следующее:

Существуют два элемента множества, сумма которых по модулю K принадлежит одному и тому же множеству.

То, что вы хотите проверить, это то, что:

Для всех X, Y в S: ((X+Y) mod K) в S.

Саму операцию можно записать так:Z is (X+Y) mod K

Как трейсер может вам это объяснить?

group(S, K) :-
   \+ (
         member(X,S), member(Y,S), Z is (X+Y) mod K,
         \+ member(Z,S)
   ).

?- group([0,1,2],3).
true.

?- group([0,2],3).
false.
person false    schedule 16.11.2012
comment
Я использовал трассировщик, потому что только что нашел его, а также подумал, что он может показать, почему окончательный ответ — «нет», хотя правильный ответ должен быть «да». Кроме того, верно, что я проверяю, существуют ли два элемента множества, сумма которых по модулю K принадлежит одному и тому же множеству, и, насколько я вижу, эта проверка выполняется корректно для всех случаев, но последняя проверка выполняется так: кажется мне загадочным. @ЛОЖЬ - person Valtteri; 16.11.2012
comment
@Valtteri: Единственное, что загадочно, - это мельчайшие детали, которые производит трассировщик. Смотреть не стоит. Важно то, что означает ваша программа! - person false; 16.11.2012
comment
Да, вы использовали отрицание в решении. Это логично. Спасибо. И ответ Desert69 объясняет, почему он делает это окончательное нет. По крайней мере, я надеюсь, что правильно понял... - person Valtteri; 16.11.2012
comment
@Valtteri: трассировка не показала ничего отрицательного. Ибо раньше это вовсе не отрицалось. Лучше всего смотреть ответы (без трассировщика). И попробуйте также такие случаи, как [0,2],3, где не должно быть решения (но раньше были некоторые...) - person false; 16.11.2012
comment
Трассировка не показала ничего отрицательного, но вы используете отрицание /+ в своем решении, т.е. проверьте, есть ли суммы, которые не работают, и если их нет, ответ верен. Кроме того, если я использую случай [0,2],3 , есть решения моей исходной формулировки, такие как (0,0). Вы, конечно, правы, что трассировщик в данном случае бесполезен, потому что проблема настолько очевидна, что его использование отвлекло меня от правильного решения и заставило сосредоточиться на нем, а не на коде. Но я узнал кое-что новое и разместил здесь, так что из этого вышло что-то хорошее! - person Valtteri; 16.11.2012

arrow_upward
0
arrow_downward

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

Посмотрите на выполнение в целом, вы наверняка увидите ошибочные предикаты, которые действительно верны, например Fail: (7) lists:member(0, [0, 1, 2]) во втором вычислении.

[trace]  ?- group([0, 1, 2], 3).
   Call: (6) group([0, 1, 2], 3) ? creep
   Call: (7) lists:member(_G718, [0, 1, 2]) ? creep
   Exit: (7) lists:member(0, [0, 1, 2]) ? creep
   Call: (7) lists:member(_G718, [0, 1, 2]) ? creep
   Exit: (7) lists:member(0, [0, 1, 2]) ? creep
^  Call: (7) _G721 is 0+0 ? creep
^  Exit: (7) 0 is 0+0 ? creep
^  Call: (7) _G724 is 0 mod 3 ? creep
^  Exit: (7) 0 is 0 mod 3 ? creep
   Call: (7) lists:member(0, [0, 1, 2]) ? creep
   Exit: (7) lists:member(0, [0, 1, 2]) ? creep
   Exit: (6) group([0, 1, 2], 3) ? creep
true ;
   Redo: (7) lists:member(0, [0, 1, 2]) ? creep
   Fail: (7) lists:member(0, [0, 1, 2]) ? creep
   Redo: (7) lists:member(_G718, [0, 1, 2]) ? creep
   Exit: (7) lists:member(1, [0, 1, 2]) ? creep
^  Call: (7) _G721 is 0+1 ? creep
^  Exit: (7) 1 is 0+1 ? creep
^  Call: (7) _G724 is 1 mod 3 ? creep
^  Exit: (7) 1 is 1 mod 3 ? creep
   Call: (7) lists:member(1, [0, 1, 2]) ? creep
   Exit: (7) lists:member(1, [0, 1, 2]) ? creep
   Exit: (6) group([0, 1, 2], 3) ? creep
true ;
   Redo: (7) lists:member(1, [0, 1, 2]) ? creep
   Fail: (7) lists:member(1, [0, 1, 2]) ? creep
   Redo: (7) lists:member(_G718, [0, 1, 2]) ? creep
   Exit: (7) lists:member(2, [0, 1, 2]) ? creep
^  Call: (7) _G721 is 0+2 ? creep
^  Exit: (7) 2 is 0+2 ? creep
^  Call: (7) _G724 is 2 mod 3 ? creep
^  Exit: (7) 2 is 2 mod 3 ? creep
   Call: (7) lists:member(2, [0, 1, 2]) ? creep
   Exit: (7) lists:member(2, [0, 1, 2]) ? creep
   Exit: (6) group([0, 1, 2], 3) ? creep
true ;
   Redo: (7) lists:member(_G718, [0, 1, 2]) ? creep
   Exit: (7) lists:member(1, [0, 1, 2]) ? creep
   Call: (7) lists:member(_G718, [0, 1, 2]) ? creep
   Exit: (7) lists:member(0, [0, 1, 2]) ? creep
^  Call: (7) _G721 is 1+0 ? creep
^  Exit: (7) 1 is 1+0 ? creep
^  Call: (7) _G724 is 1 mod 3 ? creep
^  Exit: (7) 1 is 1 mod 3 ? creep
   Call: (7) lists:member(1, [0, 1, 2]) ? creep
   Exit: (7) lists:member(1, [0, 1, 2]) ? creep
   Exit: (6) group([0, 1, 2], 3) ? creep
true ;
   Redo: (7) lists:member(1, [0, 1, 2]) ? creep
   Fail: (7) lists:member(1, [0, 1, 2]) ? creep
   Redo: (7) lists:member(_G718, [0, 1, 2]) ? creep
   Exit: (7) lists:member(1, [0, 1, 2]) ? creep
^  Call: (7) _G721 is 1+1 ? creep
^  Exit: (7) 2 is 1+1 ? creep
^  Call: (7) _G724 is 2 mod 3 ? creep
^  Exit: (7) 2 is 2 mod 3 ? creep
   Call: (7) lists:member(2, [0, 1, 2]) ? creep
   Exit: (7) lists:member(2, [0, 1, 2]) ? creep
   Exit: (6) group([0, 1, 2], 3) ? creep
true ;
   Redo: (7) lists:member(_G718, [0, 1, 2]) ? creep
   Exit: (7) lists:member(2, [0, 1, 2]) ? creep
^  Call: (7) _G721 is 1+2 ? creep
^  Exit: (7) 3 is 1+2 ? creep
^  Call: (7) _G724 is 3 mod 3 ? creep
^  Exit: (7) 0 is 3 mod 3 ? creep
   Call: (7) lists:member(0, [0, 1, 2]) ? creep
   Exit: (7) lists:member(0, [0, 1, 2]) ? creep
   Exit: (6) group([0, 1, 2], 3) ? creep
true ;
   Redo: (7) lists:member(0, [0, 1, 2]) ? creep
   Fail: (7) lists:member(0, [0, 1, 2]) ? creep
   Redo: (7) lists:member(_G718, [0, 1, 2]) ? creep
   Exit: (7) lists:member(2, [0, 1, 2]) ? creep
   Call: (7) lists:member(_G718, [0, 1, 2]) ? creep
   Exit: (7) lists:member(0, [0, 1, 2]) ? creep
^  Call: (7) _G721 is 2+0 ? creep
^  Exit: (7) 2 is 2+0 ? creep
^  Call: (7) _G724 is 2 mod 3 ? creep
^  Exit: (7) 2 is 2 mod 3 ? creep
   Call: (7) lists:member(2, [0, 1, 2]) ? creep
   Exit: (7) lists:member(2, [0, 1, 2]) ? creep
   Exit: (6) group([0, 1, 2], 3) ? creep
true ;
   Redo: (7) lists:member(_G718, [0, 1, 2]) ? creep
   Exit: (7) lists:member(1, [0, 1, 2]) ? creep
^  Call: (7) _G721 is 2+1 ? creep
^  Exit: (7) 3 is 2+1 ? creep
^  Call: (7) _G724 is 3 mod 3 ? creep
^  Exit: (7) 0 is 3 mod 3 ? creep
   Call: (7) lists:member(0, [0, 1, 2]) ? creep
   Exit: (7) lists:member(0, [0, 1, 2]) ? creep
   Exit: (6) group([0, 1, 2], 3) ? creep
true ;
   Redo: (7) lists:member(0, [0, 1, 2]) ? creep
   Fail: (7) lists:member(0, [0, 1, 2]) ? creep
   Redo: (7) lists:member(_G718, [0, 1, 2]) ? creep
   Exit: (7) lists:member(2, [0, 1, 2]) ? creep
^  Call: (7) _G721 is 2+2 ? creep
^  Exit: (7) 4 is 2+2 ? creep
^  Call: (7) _G724 is 4 mod 3 ? creep
^  Exit: (7) 1 is 4 mod 3 ? creep
   Call: (7) lists:member(1, [0, 1, 2]) ? creep
   Exit: (7) lists:member(1, [0, 1, 2]) ? creep
   Exit: (6) group([0, 1, 2], 3) ? creep
true ;
   Redo: (7) lists:member(1, [0, 1, 2]) ? creep
   Fail: (7) lists:member(1, [0, 1, 2]) ? creep
   Fail: (6) group([0, 1, 2], 3) ? creep
false.
person mgarciaisaia    schedule 16.11.2012
comment
Ах я вижу. Таким образом, сначала он ищет одно решение (0,0), но затем, поскольку я спросил, есть ли другие решения, он должен ошибиться с правильным решением из предыдущего случая, чтобы создать тест для другого случая, и, наконец, он должен потерпеть неудачу. решающий тест, и он отвечает нет. Интересно и имеет большой смысл. Может быть, я должен проверить, есть ли решение, которое не принадлежит набору. Но спасибо за ответ. @desert69 - person Valtteri; 16.11.2012