prolog - Prolog。从第一个列表中删除在第二个列表中出现偶数的项目

我刚刚开始学习如何使用 prolog 中的列表,并且尝试在类似任务的示例上编写程序,但它不起作用。任务是 - 从第一个列表中删除在第二个列表中出现偶数次的项目。

我在这个函数中有这样的逻辑:

  1. 函数 counter 应该返回列表中某个元素的数量。
  2. 函数 remove 忽略在第二个列表中具有偶数数量的元素。

我的代码:

counter(_,[],0).

counter(Number, [H|T], Quantity):- 
    Number =:= H,
    UpdatedQuantity is Quantity + 1,
    counter(Number, T, UpdatedQuantity).
    
counter(Number, [H|T], Quantity):- 
    Number =\= H,
    counter(Number, T, Quantity).


remove([], [], []).

remove([H1|T1], T2, [H1 | T1]) :-
    counter(H1, T2, Quantity),
    Quantity mod 2 =:= 0,
    remove(T1, T2, T1).
    
remove([H1|T1], T2, T1) :-
    counter(H1, T2, Quantity),
    Quantity mod 2 =\= 0,
    remove(T1, T2, T1).

例如 remove([1,2,3,4][1,1,2,3,3,3,4,4,4,4,5,6,7,7], Res) 将返回 Res = [2,3,4,5,7,7]

回答1

修改谓词counter/3的第二个子句如下:

  • 首先找到问题的更简单实例的解决方案。
  • 然后使用该解决方案来获得问题原始实例的解决方案。
counter(_, [], 0).

counter(Number, [H|T], UpdatedQuantity):-
    Number =:= H,
    counter(Number, T, Quantity),    
    UpdatedQuantity is Quantity + 1. 

counter(Number, [H|T], Quantity):-
    Number =\= H,
    counter(Number, T, Quantity).

修改谓词 remove/3 如下:

  • 将第一个子句替换为 remove([], _, []),因为第二个列表不需要为空即可停止递归。
  • 在最后两个子句中,当 T1 出现在第三个参数中时,将其替换为 T3(一个新变量),因为结果列表可能不等于第一个输入列表。
  • 另外,交换最后两个子句中使用的条件;否则,您将删除出现奇数个的项目。
remove([], _, []).

remove([H1|T1], T2, [H1|T3]) :-
    counter(H1, T2, Quantity),
    Quantity mod 2 =\= 0,
    remove(T1, T2, T3).

remove([H1|T1], T2, T3) :-
    counter(H1, T2, Quantity),
    Quantity mod 2 =:= 0,
    remove(T1, T2, T3).

例子:

?- remove([1,2,3,4,5],[1,1,2,2,2,4], Res).
Res = [2, 4] ;
false.

改进的解决方案 避免虚假选择点和 counter/3 的冗余调用。

improved_counter([], _, 0).
improved_counter([H|T], Number, UpdatedQuantity):-
    improved_counter(T, Number, Quantity),
    (   Number =:= H
    ->  UpdatedQuantity is Quantity + 1
    ;   UpdatedQuantity is Quantity ).

improved_remove([], _, []).
improved_remove([H1|T1], T2, Res) :-
    improved_counter(T2, H1, Quantity), % solve this goal only once!
    (   Quantity mod 2 =:= 0
    ->  Res = T3
    ;   Res = [H1|T3] ),
    improved_remove(T1, T2, T3).

例子:

?- improved_remove([1,2,3,4,5],[1,1,2,2,2,4], Res).
Res = [2, 4].

相似文章

最新文章