Prolog 检查列表是否包含偶数个元素

Question

我必须检查列表是否包含偶数个没有内置元素的元素。

示例：

containsEvenNumber([a,b,c,a,a], a).

returns false

containsEvenNumber([a,b,c,a], a).

return真

当前状态：

not(A) :-
    A, !,
    fail.
not(_).
equal([E|_], E).
containsEvenNumber([], _).
containsEvenNumber([E|Tail], E) :-
    unevenCount(Tail, E).

containsEvenNumber([Head|Tail], E) :-
    not(equal([Head|Tail], E)),
    evenCount(Tail, E).

evenCount([], _).
evenCount([E|Tail], E) :-
    unevenCount(Tail, E).

evenCount([Head, Tail], E) :-
    not(equal([Head|Tail], E)),
    unevenCount(Tail, E).

unevenCount([], _) :-
    fail.
unevenCount([E, Tail], E) :-
    evenCount(Tail, E).

unevenCount([Head, Tail], E) :-
    not(equal([Head|Tail], E)),
    unevenCount(Tail, E).

我尝试在元素出现时在状态之间切换。它不起作用，因为我从不进入头部不是元素的状态，或者更确切地说，我也进入状态并且当头部是元素时 return false。

我怎样才能做到work/fix呢？

Answer 1

“状态切换”其实是解决这个问题的好方法。逻辑应遵循以下简单规则：

There are an even number of X elements in [X|Xs] if there are an odd number of X elements in Xs.

There are an even number of X elements in [Y|Xs] if X and Y are different, and there are an even number of X elements in Xs.

There are an odd number of X elements in [X|Xs] if there are an even number of X elements in Xs.

There are an odd number of X elements in [Y|Xs] if X and Y are different, and there are an odd number of X elements in Xs.

然后你有基本情况：

There are an even number of any element in [].

There are an odd number of X in [X].

你只需要将这些规则写成序言即可。但是，您的实施存在一些问题。

在少数情况下，您将列表写成 [Head, Tail] 而不是 [Head|Tail]。 [Head, Tail] 是恰好有两个元素的列表。此外，您 unevenCount/2 的基本情况（我假设您的意思是奇数）不正确。如果你有一个总是失败的基本案例，那么你的谓词将永远失败。除了少数例外，您应该编写谓词子句以取得成功，而不是失败。无法成功时自动失败

让我们试着写出上面的规则。 ISO Prologs 已经有 \+，所以你不需要定义 not/1。另外，写 equal([E|_], E). 是不必要的。您可以直接在代码中简单地执行此操作。

evenCount(_, []).          % base case for even
evenCount(X, [X|Xs]) :-    % rule #1
    oddCount(X, Xs).
evenCount(X, [Y|Xs]) :-    % rule #2
    dif(X, Y),
    evenCount(X, Xs).

oddCount(X, [X]).          % base case for odd
oddCount(X, [X|Xs]) :-     % rule #3
    evenCount(X, Xs).
oddCount(X, [Y|Xs]) :-     % rule #4
    dif(X, Y),
    oddCount(X, Xs).

SWI Prolog 定义 dif/2。您也可以使用 \== 但它不是纯粹定义的（因此表现不一般）如 dif/2.

Prolog 检查列表是否包含偶数个元素

Prolog check if list contains even number of an element

list

recursion

prolog

tail

head