2

我们想要构建一个谓词，它获取一个列表L和一个数字N，如果N是 list 的最长序列的长度，则为 true L。例如：

?- ls([1,2,2,4,4,4,2,3,2],3).
    true.

?- ls([1,2,3,2,3,2,1,7,8],3).
    false.

为此我建造了 -

head([X|S],X). % head of the list
ls([H|T],N) :- head(T,X),H=X, NN is N-1 , ls(T,NN) . % if the head equal to his following
ls(_,0) :- !. % get seq in length N
ls([H|T],N) :- head(T,X) , not(H=X) ,ls(T,N). % if the head doesn't equal to his following

这个概念很简单 - 检查头部是否等于他的跟随，如果是，则继续尾部并减少N.

我检查了我的代码，它运行良好（忽略其中的情况N = 1） -

 ls([1,2,2,4,4,4,2,3,2],3).
true ; 
false .

但true答案不是有限的，之后还有更多的答案，我怎样才能让它返回有限的答案？

4

3 回答 3

3

Prolog 方面，你有一些问题。一个是你的谓词只在两个参数都被实例化时才有效，这让 Prolog 很失望。另一个是你的风格——<code>head/2 并没有真正在[H|T]. 我也认为这个算法从根本上是有缺陷的。如果不保留猜测长度的不变副本，我认为您无法确定列表尾部不存在更长长度的序列。换句话说，@Zakum 指出的第二件事，我认为不会有一个简单的解决方案。

这就是我解决问题的方式。首先是一个辅助谓词，用于获取两个值的最大值：

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- Y > X.

现在大部分工作sequence_length/2都委托给一个循环，除了空列表的基本情况：

sequence_length([], 0).
sequence_length([X|Xs], Length) :- 
    once(sequence_length_loop(X, Xs, 1, Length)).

调用once/1确保我们只得到一个答案。这将阻止谓词有效地生成带有序列的列表，同时也使谓词具有确定性，这是您想要的。（它与放置良好的切割具有相同的效果）。

循环的基本情况：将累加器复制到输出参数：

sequence_length_loop(_, [], Length, Length).

归纳案例#1：我们有另一个相同值的副本。增加累加器并重复。

sequence_length_loop(X, [X|Xs], Acc, Length) :- 
    succ(Acc, Acc1), 
    sequence_length_loop(X, Xs, Acc1, Length).

归纳案例#2：我们有不同的价值。计算列表剩余部分的序列长度；如果它比我们的累加器大，请使用它；否则，请使用蓄能器。

sequence_length_loop(X, [Y|Xs], Acc, Length) :- 
    X \= Y,
    sequence_length([Y|Xs], LengthRemaining),
    max(Acc, LengthRemaining, Length).

这就是我将如何解决这个问题。我不知道它是否对你有用，但我希望你能从中收集到一些东西。

于 2013-02-28T07:16:07.473 回答
2

在最后一条规则中添加一个中断怎么样？

head([X|S],X). % head of the list
ls([H|T],N) :- head(T,X),H=X, NN is N-1 , ls(T,NN) .    % if the head equal to his following
ls(_,0) :- !.                                           % get seq in length N
ls([H|T],N) :- head(T,X) , not(H=X) ,ls(T,N),!.         % if the head doesn't equal to his following

为我工作，虽然我不是 Prolog 专家。

//编辑：顺便说一句。尝试

14 ?- ls([1,2,2,4,4,4,2,3,2],2).
true ;
false.

对我来说看起来是错误的，没有检查 N 是否是最长的序列。还是我弄错了要求？

于 2013-02-28T00:55:37.430 回答
2

您的代码正在检查列表中是否至少有一系列指定长度的元素。在访问列表时，您需要更多参数来保持搜索状态：

ls([E|Es], L) :- ls(E, 1, Es, L).

ls(X, N, [Y|Ys], L) :-
  (  X = Y
  -> M is N+1,
     ls(X, M, Ys, L)
  ;  ls(Y, 1, Ys, M),
     ( M > N -> L = M ; L = N )
  ).
ls(_, N, [], N).
于 2013-02-28T08:01:12.687 回答