序言 - 二進制加法？

Question

我需要編寫一個Prolog謂詞來計算列表中2個二進制數的和。 這些列表已經顛倒了，例如（[0,1]基數2）=（2基數10）。

它應與模式binary_plus工作（+，+， - ），例如

?- binary_plus([1,1],[1],X). 
X = [0,0,1]. 

並用模式binary_plus（ - ， - ，+），例如

?- binary_plus(X,X,[0,1]). 
X = [1]. 

林不允許使用切標誌，findall，否定或if-then-else。

這裏是我的代碼：

is_binary([]). 
is_binary([X]):- X is 1. 
is_binary([X|Xs]):- 
    append(_,[1],Xs), 
    member(X,[0,1]),  
    is_binary(Xs). 

binary_plus([],X,X):- 
    is_binary(X). 
binary_plus(X,[],X):- 
    is_binary(X). 

binary_plus([0|Xs],[Y|Ys],[Y|Zs]):- 
    binary_plus(Xs,Ys,Zs). 
binary_plus([1|Xs],[0|Ys],[1|Zs]):- 
    binary_plus(Xs,Ys,Zs). 
binary_plus([1|Xs],[1|Ys],[0|Zs]):- 
    binary_plus(Xs,[1],Ws), 
    binary_plus(Ws,Ys,Zs). 

我不知道我錯了，因爲有我不能解決一些奇怪的問題， 所以如果有人可以幫助我，我將不勝感激。 謝謝。

Answer 1

在這裏，我認爲二進制沒有任何東西。據我所知，你是不是使用clpfd：

binary_plus(A,B,C) :- binary_plus_0(A,B,C). 

binary_plus_0([], [], []). 
binary_plus_0([], [B|Bs],[B|Bs]). 
binary_plus_0([A|As],[], [A|As]). 
binary_plus_0([A|As],[B|Bs],[C|Cs]) :- binary_plus_0(A,B,C,As,Bs,Cs). 

binary_plus_0(0,0,0,As,Bs,Cs) :- binary_plus_0(As,Bs,Cs). 
binary_plus_0(0,1,1,As,Bs,Cs) :- binary_plus_0(As,Bs,Cs). 
binary_plus_0(1,0,1,As,Bs,Cs) :- binary_plus_0(As,Bs,Cs). 
binary_plus_0(1,1,0,As,Bs,Cs) :- binary_plus_1(As,Bs,Cs). 

binary_plus_1([], [], [1]). 
binary_plus_1([], [B|Bs],Cs)  :- binary_plus_0([1],[B|Bs],Cs). 
binary_plus_1([A|As],[], Cs)  :- binary_plus_0([A|As],[1],Cs). 
binary_plus_1([A|As],[B|Bs],[C|Cs]) :- binary_plus_1(A,B,C,As,Bs,Cs). 

binary_plus_1(0,0,1,As,Bs,Cs) :- binary_plus_0(As,Bs,Cs). 
binary_plus_1(0,1,0,As,Bs,Cs) :- binary_plus_1(As,Bs,Cs). 
binary_plus_1(1,0,0,As,Bs,Cs) :- binary_plus_1(As,Bs,Cs). 
binary_plus_1(1,1,1,As,Bs,Cs) :- binary_plus_1(As,Bs,Cs). 

Answer 2

在描述列表時，請始終考慮使用DCG表示法。例如，你的情況，考慮寫這本爲：

:- use_module(library(clpfd)). 

binary_addition(Xs, Ys, As) :- 
     phrase(binary_addition_(Xs, Ys, 0), As). 

binary_addition_([], [], 0)  --> []. 
binary_addition_([], [], 1)  --> [1]. 
binary_addition_([X|Xs], [], C) --> binary_addition_([X|Xs], [C], 0). 
binary_addition_([], [Y|Ys], C) --> binary_addition_([C], [Y|Ys], 0). 
binary_addition_([X|Xs], [Y|Ys], C0) --> 
     { [X,Y] ins 0..1, 
      Sum #= X + Y + C0 }, 
     sum_carry(Sum, C), 
     binary_addition_(Xs, Ys, C). 

sum_carry(0, 0) --> [0]. 
sum_carry(1, 0) --> [1]. 
sum_carry(2, 1) --> [0]. 

實例查詢和他們的解決方案：

?- binary_addition([1,0],[0,1,1], Sum). 
Sum = [1, 1, 1] . 

?- binary_addition([1,1],[1,0,1], Sum). 
Sum = [0, 0, 0, 1] . 

?- binary_addition([0,1],[1,1], Sum). 
Sum = [1, 0, 1] . 

注意，它也可以在其他方向：

?- binary_addition(Xs, Ys, [1,1]). 
Xs = [1, 1], 
Ys = [] ; 
Xs = [], 
Ys = [1, 1] ; 
Xs = [_G2510, 1], 
Ys = [_G2522], 
_G2510 in 0..1, 
_G2510+_G2522#=1, 
_G2522 in 0..1 ; 
etc. 

你如果您想要反向列表，可以簡單地將reverse/2目標添加到binary_addition/3。