Prolog：对表示整数的两个列表的元素求和（限制在非正则求和内！！）

Question

我正在解决一个问题：一个列表表示一个整数，比如 12345 乘以 L=[12,34,5] 每个元素应该从 0 到 99.The 练习是编写一个函数（sum）来对两个列表求和并给出它们的等价列表sum 表示两个整数的总和。

?-sum([11,11],[11,11],L,0).
L=[22,22].

?-sum([12,81],[11,44],L,0).
L=[24,25].

//digit fxn for making sure that we insert an elemnt of two or single integer 
//and saving the overflow digit in S1.

我的代码出现错误：

digit(X,D,S1):- S is X/100,S1 is integer(S),0 is S1,D is X.

digit(X,D,S1):-D is mod(X/100).

sum([],[],[],0).

sum(H1|T1,H|T,H3|T3,S):-Z is H1+H+S ,digit(Z,H3,S1),sum(T1,T,T3,S1).

Answer 1

digit 是一个递归谓词。我在你的定义中没有看到递归。

基本情况当然是数字为 0，且列表为空：

digit(0, []).

然而，递归情况分为两部分，具体取决于第一个参数是变量还是第二个：

digit(X, [Y|Ys]) :- nonvar(Y), digit(Z, Ys), X is Y + 100 * Z.
digit(D, [X|Xs]) :- nonvar(D), D>0, X is mod(D,100), R is div(D,100), digit(R, Xs).

现在您可以使用 digit 两种方式：

?- digit(12345,X).
X = [45, 23, 1] ;
false.

?- digit(X,[45,23,1]).
X = 12345.

请注意，列表是颠倒的！你可以让它输出已经反转（我会把它留给你作为练习，而我会在这里使用 reverse/2；提示：使用 accumulators）。

sum(A,B,R) :- reverse(A,AR), reverse(B,BR),
              digit(A1,AR), digit(B1,BR),
              R1 is A1+B1,
              digit(R1,RR),
              reverse(R,RR).

?- sum([11,11],[11,11],X).
X = [22, 22] .

?- sum([12,81],[11,44],X).
X = [24, 25] .

Answer 2

使用 clpfd!

简单明了

:- use_module(library(clpfd)).

digitFD(X,Zs) :-
   digitFD_aux(X,Zs,[],Zs).

digitFD_aux(X,[_],Zs,[X|Zs]) :-
   X in 0..99.
digitFD_aux(X,[_|Ys],Zs0,Zs) :-
   X #> 99,
   Z #> 0,
   Y in 0..99,
   X #= Y + 100 * Z,
   digitFD_aux(Z,Ys,[Y|Zs0],Zs).

让我们测试一下digitFD/2！

?- As = [12,34,56,78], digitFD(N,As).
As = [12,34,56,78], N = 12345678 ;
false.

?- N = 123456789, digitFD(N,As).
N = 123456789, As = [1,23,45,67,89] ;
false.

好的！让我们定义 sumFD/4：

sumFD(As,Bs,Cs,Zs) :-
   digitFD(A,As), 
   digitFD(B,Bs),
   C #= A+B,
   digitFD(C,Cs),
   append([As,Bs,Cs],Zs).

让我们使用它！

?- sumFD([11,11],[11,11],Xs,Zs), labeling([],Zs).
Xs = [22,22], Zs = [11,11,11,11,22,22] ;
false.

?- sumFD([12,81],[11,44],Xs,Zs), labeling([],Zs).
Xs = [24,25], Zs = [12,81,11,44,24,25] ;
false.

Answer 3

出于所有意图和目的，您的列表都是以 100 为基数的数字。解决它的简单方法是按照与手写计算相同的方式进行算术运算：从最低有效位开始，计算到最高有效位，对每对数字求和，并向左进位如果溢出。

我们颠倒了列表，以便我们轻松地从右到左工作。您会注意到工作谓词 sum_list_mod_100/4 构建的结果顺序正确。

sum_list_mod_100( Xs , Ys , Zs ) :-       % to compute the sum of a list representing a base-100 integer.
  reverse( Xs , X1 ) ,                    % - reverse the digits of the left hand side (so we're working from least- to most-significant digit)
  reverse( Ys , Y1 ) ,                    % - reverse the digits of the right hand side (so we're working from least- to most-significant digit)
  sum_list_mod_100( X1 , Y1 , 0 , Zs ) .  % - invoke the worker with the carry initialized as zero.
  .

sum_list_mod_100( []     , [] , C , []  ) .         % both lists are empty w/o carry: terminate. 
  C = 0                                             %
  .                                                 %
sum_list_mod_100( []     , [] , C , [C] ) :-        % both lists are empty with a carry: prepend the carry to the result.
  C > 0                                             %
  .                                                 %
sum_list_mod_100( [X|Xs] , [] , C , [Z|Zs]  ) :-    % right-hand side exhausted?
  sum_digits(X,0,C,Z,C1) ,                          % - sum the digits, returning the new digit and the new carry
  sum_list_mod_100( Xs , [] , C1 , Zs )             % - recurse down, passing the new carry
  .                                                 % 
sum_list_mod_100( [] , [Y|Ys] , C , [Z|Zs]  ) :-    % left-hand side exhausted?
  sum_digits(0,Y,C,Z,C1) ,                          % - sum the digits, returning the new digit and the new carry
  sum_list_mod_100( [] , Ys , C1 , Zs )             % - recurse down, passing the new carry
  .                                                 %
sum_list_mod_100( [X|Xs] , [Y|Ys] , C , [Z|Zs] ) :- % not yet exhausted?
  sum_digits(X,Y,C,Z,C1) ,                          % - sum the digits, returning the new digit and the new carry
  sum_list_mod_100( Xs , Ys , C1 , Zs )             % - recurse down passing the new carry
  .                                                 % Easy!

sum_digit(X,Y,C,Z,C1) :-  % to sum two digits (and the carry)
  S is X+Y+C ,            % - sum the LHS, RHS and the carry
  Z is X mod 100 ,        % - compute the digit modulo 100
  C1 is X div 100         % - compute the carry
  .

Prolog：对表示整数的两个列表的元素求和（限制在非正则求和内！！）

Prolog: Summing elements of two lists representing an integer(restrictions inside not regular sum!!)

list

prolog