list - saber - numero palindromo en c

Predicado de Prólogo recursivo para reverso/palíndromo

Question

1. ¿Puedo obtener un predicado Prolog recursivo con dos argumentos, llamado reverse, que devuelve el inverso de una lista?

   Consulta de muestra y resultado esperado:

   ?- reverse([a,b,c], L). L = [c,b,a].

2. Un predicado Prolog recursivo de dos argumentos llamado palindrome que devuelve verdadero si la lista dada es palindrome.

   Consulta de muestra con resultado esperado:

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

Answer 1

Solo por curiosidad aquí va una implementación recursiva de reverse / 2 que no usa predicados auxiliares y aún invierte la lista. Puede considerar que es una trampa ya que usa reverse / 2 usando listas y la estructura - / 2 como argumentos.

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).

Answer 2

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).

Answer 3

Anuncio 1: es imposible definir reverse/2 como un predicado recursivo (edite directamente thx a @repeat: tail) - a menos que permita un predicado auxiliar.

Anuncio 2:

palindrome(X) :- reverse(X,X).

Pero la forma más fácil es definir dichos predicados con los 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].

Answer 4

No hay una manera eficiente de definir reverse/2 con una única definición recursiva sin usar algún predicado auxiliar. Sin embargo, si esto está permitido, una solución simple que no dependa de ningún built-in como append/3 (y debería ser aplicable para la mayoría de las implementaciones de Prolog) sería usar una lista de acumuladores , de la siguiente manera:

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 es el predicado de inversión que simplemente ''delega'' (o envuelve) la versión basada en el acumulador llamada rev-acc/2 , que recursivamente agrega elementos de la lista de entrada en un acumulador en orden inverso.

Ejecutando esto:

?- rev([1,3,2,x,4],L).
L = [4, x, 2, 3, 1].

Y de hecho, como @false ya ha señalado (+1),

palindrome(X) :- rev(X,X).