Проблема с рекурсивным предикатом на Прологе

Question

Цель a(3, X) должна вернуться 6.На основании этого кода.Я преобразовал его в код Пролога, но с проблемой в рекурсивном предикате.Первые две строки для 0 и 1 возвращают одно и то же значение.

c=1
  for i = 2 to n do
    if c > i then
      c=c-1
    else
      c=c+1
    end if
end for
return c

Но на шаге 4 он получает результат, затем возвращается к шагу 2 и возвращается с итерацией к неверному результату.Я думаю, что есть проблема объединения, но не могу найти где.

a(N, N) :- N < 2, !.
a(N, X) :- a(1, 2, N, X).

Шаг 2.

a(C1, I, N, C1) :- I > N, !.

Шаг 3.

a(C, I, N, C1) :- C > I, !,
                 C1 is C - I,
                 I1 is I + 1,
                 a(C1, I1, N, C1).

Шаг 4.

a(C, I, N, C1) :- C =< I, !,
                 C1 is C + I,
                 I1 is I + 1,
                 a(C1, I1, N, C1).

Это след.

[trace]  ?- a(3, X).
   Call: (8) a(3, _1238) ? creep
   Call: (9) 3<2 ? creep
   Fail: (9) 3<2 ? creep
   Redo: (8) a(3, _1238) ? creep
   Call: (9) a(1, 2, 3, _1238) ? creep
   Call: (10) 2>3 ? creep
   Fail: (10) 2>3 ? creep
   Redo: (9) a(1, 2, 3, _1238) ? creep
   Call: (10) 1>2 ? creep
   Fail: (10) 1>2 ? creep
   Redo: (9) a(1, 2, 3, _1238) ? creep
   Call: (10) 1=<2 ? creep
   Exit: (10) 1=<2 ? creep
   Call: (10) _1474 is 1+2 ? creep
   Exit: (10) 3 is 1+2 ? creep
   Call: (10) _1480 is 2+1 ? creep
   Exit: (10) 3 is 2+1 ? creep
   Call: (10) a(3, 3, 3, 3) ? creep
   Call: (11) 3>3 ? creep
   Fail: (11) 3>3 ? creep
   Redo: (10) a(3, 3, 3, 3) ? creep
   Call: (11) 3>3 ? creep
   Fail: (11) 3>3 ? creep
   Redo: (10) a(3, 3, 3, 3) ? creep
   Call: (11) 3=<3 ? creep
   Exit: (11) 3=<3 ? creep
   Call: (11) _1486 is 3+3 ? creep
   Exit: (11) 6 is 3+3 ? creep
   Call: (11) _1492 is 3+1 ? creep
   Exit: (11) 4 is 3+1 ? creep
   Call: (11) a(6, 4, 3, 6) ? creep
   Call: (12) 4>3 ? creep
   Exit: (12) 4>3 ? creep
   Exit: (11) a(6, 4, 3, 6) ? creep  !!! SHOULD STOP HERE !!!
   Exit: (10) a(3, 3, 3, 3) ? creep
   Exit: (9) a(1, 2, 3, 1) ? creep
   Exit: (8) a(3, 1) ? creep
X = 1 .

Answer 1

Вам нужна другая переменная.Вы «перегружаете» C1, поэтому он уже создан (связан), когда вы выполняете рекурсивный вызов, и в результате вы получаете такие вещи в трассировке (заметьте, используя код, который вы показываете, я не получаюТо же самое вы делаете, так что вы сделали что-то другое с вашим кодом):

| ?- a(3,X).
      1    1  Call: a(3,_23) ?
      2    2  Call: 3<2 ?
      2    2  Fail: 3<2 ?
      2    2  Call: a(1,2,3,_23) ?
      3    3  Call: 2>3 ?
      3    3  Fail: 2>3 ?
      3    3  Call: 1>2 ?
      3    3  Fail: 1>2 ?
      3    3  Call: 1=<2 ?
      3    3  Exit: 1=<2 ?
      4    3  Call: _23 is 1+2 ?
      4    3  Exit: 3 is 1+2 ?
      5    3  Call: _174 is 2+1 ?
      5    3  Exit: 3 is 2+1 ?
      6    3  Call: a(3,3,3,3) ?
      7    4  Call: 3>3 ?
      7    4  Fail: 3>3 ?
      7    4  Call: 3>3 ?
      7    4  Fail: 3>3 ?
      7    4  Call: 3=<3 ?
      7    4  Exit: 3=<3 ?
      8    4  Call: 3 is 3+3 ?
      8    4  Fail: 3 is 3+3 ?  <--- FAILS HERE: DUE TO C1 ALREADY BOUND
                                     3 cannot be 3+3 !
      6    3  Fail: a(3,3,3,3) ?
      2    2  Fail: a(1,2,3,_23) ?
      1    1  Fail: a(3,_23) ?

(1 ms) no

Итак, вот исправление с дополнительной переменной:

a(C, I, N, C1) :- C > I, !,
                 C2 is C - I,
                 I1 is I + 1,
                 a(C2, I1, N, C1).

a(C, I, N, C1) :- C =< I, !,
                 C2 is C + I,
                 I1 is I + 1,
                 a(C2, I1, N, C1).

Тогда вы получите:

| ?- a(3,X).

X = 6

(1 ms) yes
| ?-

Кстати, не спешите разбрасывать фрагменты кода.Получите все это работает первым без них.Затем поместите их очень намеренно, чтобы обрезать ветви решений.Иногда они обрезают пути, которые вам действительно нужны, и приводят к нежелательным результатам.