将List转为数字，将数字加1，然后将数字转为列表

Question

我的头被困在序言中的这个练习中，我一直在尝试自己做，但它就是行不通。示例： ?-后继([1,9,9],X) -> X = [2,0,0]。首先尝试反转列表并将其增加 1，然后执行 if %10 = 0 下一个元素也应该增加。问题是我太习惯编程语法了，我无法理解这一点。任何帮助将不胜感激。

到目前为止我已经这样做了，但输出是错误的。

%[1,9,9] -> 199 +1 -> 200;

numbers_atoms([],[]).
numbers_atoms([X|Y],[C|K]) :-
   atom_number(C, X),
   numbers_atoms(Y,K).

%([1,2,3],X)

digits_number(Digits, Number) :-
   numbers_atoms(Digits, Atoms),
   number_codes(Number, Atoms).

number_tolist( 0, [] ).
number_tolist(N,[A|As]) :-
   N1 is floor(N/10),
   A is N mod 10,
   number_tolist(N1, As).

addOne([X],[Y]):-
   digits_number(X,Y1), %[1,9,9] -> 199
   Y1 is Y1+1, % 199 -> 200
   number_tolist(Y1,[Y]), % 200 -> [2,0,0]
   !.

Answer 1

您可以像手动解决这个问题一样解决这个问题：遍历数字列表，直到到达最右边的数字；增加该数字并计算进位数字，该数字必须递归地向左传播。最后，如果等于 1，则在前面添加进位数字（否则忽略它）。

% successor(+Input, -Output)

  successor([X0|Xs], L) :-
      successor(Xs, X0, C, Ys),
      (   C = 1                  % carry-on 
      ->  L = [C|Ys]
      ;   L = Ys ).

% helper predicate

  successor([], X, C, [Y]) :-
      Z is X + 1,
      Y is Z mod 10,
      C is Z div 10.             % carry-on 
  successor([X1|Xs], X0, C, [Y|Ys]) :-
      successor(Xs, X1, C0, Ys),
      Z is X0 + C0,
      Y is Z mod 10,
      C is Z div 10.             % carry-on 

示例：

?- successor([1,9,9], A).
A = [2, 0, 0].

?- successor([2,7],A), successor(A,B), successor(B,C), successor(C,D).
A = [2, 8],
B = [2, 9],
C = [3, 0],
D = [3, 1].

?- successor([7,9,9,8], A), successor(A, B).
A = [7, 9, 9, 9],
B = [8, 0, 0, 0].

?- successor([9,9,9,9], A), successor(A, B).
A = [1, 0, 0, 0, 0],
B = [1, 0, 0, 0, 1].

Answer 2

这是一个不使用 is 的版本，并且可以两种方式工作：

successor(ListIn, ListOut) :-
    reverse(ListIn, ListInRev),
    ripple_inc(ListInRev, ListOutRev),
    reverse(ListOutRev, ListOut).

ripple_inc([], [1]).
ripple_inc([0|T], [1|T]).
ripple_inc([1|T], [2|T]).
ripple_inc([2|T], [3|T]).
ripple_inc([3|T], [4|T]).
ripple_inc([4|T], [5|T]).
ripple_inc([5|T], [6|T]).
ripple_inc([6|T], [7|T]).
ripple_inc([7|T], [8|T]).
ripple_inc([8|T], [9|T]).
ripple_inc([9|T], [0|Tnext]) :-
    ripple_inc(T, Tnext).

例如，

?- successor([1,9,9], X).
X = [2, 0, 0]

?- successor([1,9,9], [2,0,0]).
true

?- successor(X, [2,0,0]).
X = [1, 9, 9]

尽管在“向前”运行时它具有很好的确定性，但令人烦恼的是，如果“向后”运行它会找到答案，然后留下一个选择点如果重试该选择点，则无限循环。我认为导致这种情况的原因是从较高的数字开始，然后 reverse(ListIn, ListInRev) 没有什么可处理的，并开始生成越来越长的列表，列表中都充满了空变量，并且永远不会结束。

我可以将输入和输出限制为 same_length/2 但我想不出一种方法来将它们限制为相同的长度或 ListOut 长一项 ([9,9,9] -> [1,0,0,0]）。

Answer 3

这个答案试图改进@TessellatedHacker之前的答案，如下所示：

successor(ListIn, ListOut) :-
   no_longer_than(ListIn, ListOut),  % weaker than same_length/2
   reverse(ListIn, ListInRev),
   ripple_inc(ListInRev, ListOutRev),
   reverse(ListOutRev, ListOut).

no_longer_than/2如下。请注意与 same_length/2 的相似之处：

no_longer_than([],_).                % same_length([],[]).
no_longer_than([_|Xs],[_|Ys]) :-     % same_length([_|Xs],[_|Ys]) :- 
   no_longer_than(Xs,Ys).            %    same_length(Xs,Ys).

以下示例查询仍然确定性地成功，就像以前一样：

?- successor([1,9,9], X).
X = [2,0,0].

?- successor([1,9,9], [2,0,0]).
true.

successor/2 的“向后运行”使用现在也普遍终止：

?- successor(X, [2,0,0]).
   X = [1,9,9]
;  false.