首页 文章

反向/回文的递归Prolog谓词

提问于
浏览 次
8
  • 我可以得到一个带有两个参数的递归Prolog谓词，称为reverse，它返回列表的反转：

示例查询和预期结果：

?- reverse([a,b,c], L).
L = [c,b,a].
  • 一个名为 palindrome 的两个参数的递归Prolog谓词，如果给定列表是回文，则返回true .

具有预期结果的示例查询：

?- palindrome([a,b,c]).
false.

?- palindrome([b,a,c,a,b]).
true.
list prolog reverse palindrome dcg

4 回答

  • 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].
    回复于
  • 0

    没有使用某个辅助谓词的方法，没有一种有效的方法可以使用单个递归定义来定义 reverse/2 . 但是，如果允许这样做，一个不依赖于任何内置函数的简单解决方案（如适用于大多数Prolog实现）将使用累加器列表，如下所示：

    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).
    回复于
  • 3

    只是为了好奇，这里是一个递归实现的反向/ 2，不使用辅助谓词，仍然反转列表 . 你可能会认为它作弊，因为它使用反向/ 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).
    回复于
  • 7
    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).
    回复于

相关问题