1

我有以下程序：

% finds all members in sorted list L1 that are not in the sorted L2 
%   and puts them in NL
make_list(L1,L2,NL):-
    make_list(L1,L2,NL,x).
make_list([],_,[],_):-!.

% X represents the last value parsed from L1
make_list(L1,[],L2,X):-!,
    make_list(L1,[99999999],L2,X).

make_list([X1|L1],[X2|L2],[X3|NewL],Last):-
    (
        (X1<X2,
         X1 \= Last,
         X3=X1,!,
         make_list(L1,[X2|L2],NewL,X1);
         X1<X2,!,
         make_list(L1,[X2|L2],[X3|NewL],X1)
         )
    );
    (
        X1=X2,!,
        make_list(L1,[X2|L2],[X3|NewL],*)
    );
    make_list([X1|L1],L2,[X3|NewL],*).

我的问题是，当最后一个值相同（即：）?- make_list([1,2],[2],L).时，代码不起作用，因为

make_list([X1|L1],L2,[X3|NewL],*).

和

make_list(L1,[X2|L2],[X3|NewL],*)

它将包含至少一个变量（第三个列表）的列表传递给make_list([],_,[],_). 有一条注释说明了程序的作用。如何让代码做它应该做的事情？

我还在这里问了一个关于相同但完全不起作用的代码的问题：括号是如何工作的？.

4

2 回答 2

2

解决此问题时应考虑六种互斥情况：

  1. 您用完了两个列表中的元素
  2. 您在第一个列表中用完了元素，但在第二个列表中没有
  3. 第二个列表中的元素用完了，但第一个列表中没有
  4. 两个列表都至少有一个元素，并且头部元素匹配
  5. 两个列表都至少有一个元素，并且第一个列表的头元素更小
  6. 两个列表都至少有一个元素，并且第一个列表的头元素更大

这六种组合涵盖了您需要编写的规则。

前两种情况可以由一条规则涵盖：

make_list([], _, []).

这意味着如果第一个列表为空，则不会有任何内容可添加到输出列表中。

第三种情况也很简单：如果第二个列表为空，则输出与第一个列表相同：

make_list(L1, [], L1).

案例四稍微不那么琐碎：如果头统一，同时放下它们，并解决一个较小的子问题：

make_list([H|T1], [H|T2], NL) :-
    make_list(T1, T2, NL).

案例五将第一个列表的头部插入到输出中，案例六跳过第二个列表的头部：

make_list([H1|T1], [H2|T2], NL) :-
    H1 < H2,
    make_list(T1, [H2|T2], N2),
    NL = [H1|N2].

make_list([H1|T1], [H2|T2], NL) :-
    H1 > H2,
    make_list([H1|T1], T2, NL).

请注意，当第一个列表包含重复项且第二个列表不包含相应元素的重复项时，此解决方案无法按预期工作。

于 2012-08-20T18:57:38.893 回答
1 
% finds all members in sorted list L1 that are not in the sorted L2 
% and puts them in NL

make_list(L1,L2,NL):-
    make_list(L1,L2,NL,x).

make_list([],_,[],_):-!.

% X represents the last value parsed from L1
make_list(L1,[],L2,X):-!,
    make_list(L1,[99999999],L2,X).

这里的问题是NewL，[X3|NewL]当L1为空时，由于无法分配make_list([],_,[],_):-!.而失败[X3|NewL][]

make_list([X1|L1],[X2|L2],NewL,Last):-
    X1<X2,
    X1 \= Last,
    NewL = [X3|NewL2],X3=X1,
    make_list(L1,[X2|L2],NewL2,X1),!
    ;
    X1<X2,
    make_list(L1,[X2|L2],NewL,X1),!.

make_list([X1|L1],[X1|L2],NewL,Last):-!,
    make_list(L1,[X1|L2],NewL,Last).

接下来的两种情况是 when X1>X2,X2无论如何都会被忽略，X1仅当X1=Last

make_list([X1|L1],[_|L2],NewL,X1):-!, % X1>X2
    make_list(L1,L2,NewL,X1).

make_list([X1|L1],[_|L2],NewL,Last):- % X1>X2
    make_list([X1|L1],L2,NewL,Last).
于 2012-08-20T20:41:06.437 回答