我可以得到一个递归 Prolog 谓词,它有两个参数,称为 reverse,它返回一个列表的倒数:
示例查询和预期结果:
?- 反向([a,b,c],L)。 L = [c,b,a]。
palindrome
如果给定列表是回文,则调用两个参数的递归 Prolog 谓词,该谓词返回 true。具有预期结果的示例查询:
?- 回文([a,b,c])。 错误的。 ?- 回文([b,a,c,a,b])。 真的。
问问题
6065 次
4 回答
7
在不使用一些辅助谓词的情况下,没有一种有效的方法来reverse/2
使用单个递归定义进行定义。但是,如果仍然允许这样做,一个不依赖于任何内置函数的简单解决方案append/3
(并且应该适用于大多数 Prolog 实现)将是使用accumulator list,如下所示:
rev([],[]).
rev([X|Xs], R) :-
rev_acc(Xs, [X], R).
rev_acc([], R, R).
rev_acc([X|Xs], Acc, R) :-
rev_acc(Xs, [X|Acc], R).
rev/2
是反向谓词,它简单地“委托”(或包装)基于累加器的版本,称为rev-acc/2
,它将输入列表的元素以相反的顺序递归地添加到累加器中。
运行这个:
?- rev([1,3,2,x,4],L).
L = [4, x, 2, 3, 1].
确实正如@false 已经指出的那样(+1),
palindrome(X) :- rev(X,X).
于 2011-06-23T00:26:15.290 回答
7
广告 1:不可能定义reverse/2
为(直接编辑 thx 到 @repeat:tail)递归谓词 - 除非您允许辅助谓词。
广告 2:
palindrome(X) :- reverse(X,X).
但最简单的方法是使用 DCG 定义此类谓词:
iseq([]) --> [].
iseq([E|Es]) --> iseq(Es), [E].
reverse(Xs, Ys) :-
phrase(iseq(Xs), Ys).
palindrome(Xs) :-
phrase(palindrome, Xs).
palindrome --> [].
palindrome --> [E].
palindrome --> [E], palindrome, [E].
于 2011-06-22T16:33:25.090 回答
4
只是为了好奇,这里有一个 reverse/2 的递归实现,它不使用辅助谓词并且仍然反转列表。您可能会认为它作弊,因为它使用 reverse/2 使用列表和结构 -/2 作为参数。
reverse([], []):-!.
reverse([], R-R).
reverse(R-[], R):-!.
reverse(R-NR, R-NR).
reverse([Head|Tail], Reversed):-
reverse(Tail, R-[Head|NR]),
reverse(R-NR, Reversed).
于 2011-06-23T14:57:07.427 回答
0
conca([],L,L).
conca([X|L1],L2,[X|L3]):- conca(L1,L2,L3).
rev([],[]).
rev([X|Y],N):- rev(Y,N1),conca(N1,[X],N).
palindrome([X|Y]):- rev([X|Y],N),equal([X|Y],N).
equal([X],[X]).
equal([X|Y],[X|Z]):- equal(Y,Z).
于 2014-11-23T09:10:42.320 回答