Bienvenido a nuestra página, en este lugar hallarás la respuesta que estás buscando.
Solución:
Su solución explicada: si invertimos la lista vacía, obtenemos la lista vacía. Si invertimos la lista [H|T] terminamos con la lista obtenida al invertir T y concatenar con [H] . Para ver que la cláusula recursiva es correcta, considere la lista [a,b,c,d] . Si invertimos la cola de esta lista obtenemos [d,c,b] . Concatenando esto con [a] rendimientos [d,c,b,a] que es el reverso de [a,b,c,d]
Otra solución inversa:
reverse([],Z,Z).
reverse([H|T],Z,Acc) :- reverse(T,Z,[H|Acc]).
llamar:
?- reverse([a,b,c],X,[]).
Para obtener más información, lea: http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse25
Las listas de prólogos son estructuras de datos simples: ./2
- La lista vacía es el átomo.
[]. - Una lista de un elemento,
[a]es en realidad esta estructura:.(a,[]). - Una lista de dos elementos,
[a,b]es en realidad esta estructura:.(a,.(b,[])) - Una lista de tres elementos,
[a,b,c]es en realidad esta estructura:.(a,.(b,.(c,[]))) - y así.
La notación de corchetes es azúcar sintáctica para evitar que pase su vida escribiendo paréntesis. Sin mencionar que es más agradable a la vista.
De aquí obtenemos la noción de cabeza de la lista (el dato en la parte más externa ./2 estructura) y la cola de la lista (la sublista contenida en ese extremo ./2 estructura de datos.
Esta es esencialmente la misma estructura de datos que ve para una lista clásica de enlaces simples en C:
struct list_node
char payload ;
struct list_node *next ;
donde el next el puntero es NULL u otra estructura de lista.
Entonces, a partir de eso, obtenemos el simple [naive] implementación de reverse/2:
reverse( [] , [] ) . % the empty list is already reversed.
reverse[ [X] , [X] ) . % a list of 1 item is already reversed. This special case is, strictly speaking, optional, as it will be handled by the general case.
reverse( [X|Xs] , R ) :- % The general case, a list of length >= 1 , is reversed by
reverse(Xs,T) , % - reversing its tail, and
append( T , [X] , R ) % - appending its head to the now-reversed tail
. %
Este mismo algoritmo funcionaría para invertir una lista de enlaces simples en un lenguaje de programación más convencional.
Sin embargo, este algoritmo no es muy eficiente: exhibe O(n2) comportamiento, para empezar. Tampoco es recursivo de cola, lo que significa que una lista de longitud suficiente provocará un desbordamiento de pila.
Se debe tener en cuenta que agregar un elemento a una lista de prólogos requiere recorrer toda la lista, anteponer es una operación trivial, debido a la estructura de una lista de prólogos. Podemos anteponer un elemento a una lista existente de la siguiente manera:
prepend( X , Xs , [X|Xs] ) .
Un modismo común en prolog es usar un predicado trabajador con un acumulador. Esto hace que el reverse/2 implementación mucho más eficiente y (posiblemente) un poco más fácil de entender. Aquí, invertimos la lista sembrando nuestro acumulador como una lista vacía. Iteramos sobre la lista de fuentes. A medida que encontramos un elemento en la lista de origen, lo anteponemos a la lista invertida, produciendo así la lista invertida a medida que avanzamos.
reverse(Xs,Ys) :- % to reverse a list of any length, simply invoke the
reverse_worker(Xs,[],Ys) . % worker predicate with the accumulator seeded as the empty list
reverse_worker( [] , R , R ). % if the list is empty, the accumulator contains the reversed list
reverse_worker( [X|Xs] , T , R ) :- % if the list is non-empty, we reverse the list
reverse_worker( Xs , [X|T] , R ) % by recursing down with the head of the list prepended to the accumulator
.
Ahora tienes un reverse/2 implementación que se ejecuta en tiempo O(n). También es recursivo de cola, lo que significa que puede manejar una lista de cualquier longitud sin arruinar su pila.
Considere usar un DCG en su lugar, que es mucho más fácil de entender:
reverse([]) --> [].
reverse([L|Ls]) --> reverse(Ls), [L].
Ejemplo:
?- phrase(reverse([a,b,c]), Ls).
Ls = [c, b, a].
Puntuaciones y comentarios
Acuérdate de que puedes añadir una tasación correcta si te fue preciso.