Viajeros, hola.
Si lees esto, te sugiero que continúes el material "entretenido" que escribí antes. Si seguiste un pequeño pensamiento, que se ramificó en tres artículos, pero el mensaje principal fue, solo para mostrar interés en el enfoque declarativo. Por alguna razón, no es genial, como si eSCuel no estuviera disponible públicamente y fuera obligatorio, porque sin ella es imposible pensar en cómo se pueden procesar los datos de manera diferente. Es cierto que es mejor formular la tarea y no preocuparse por lo que esto se traduce.
Pasemos a los negocios, escribí antes sobre tratar de divertirlo, así que continuaré mostrando un ejemplo de uso del prólogo, aunque los artículos anteriores han demostrado que el interés en Python e incluso irán despertarán el interés de inmediato para un par de miles de personas, ese interés en las noticias sobre una batería nueva a Tesla, es stotysch puntos de vista, y para la escritura de programas en el razrabotnichestskom portal no tan pocos, visto detrás de este comportamiento se observó en la lectura de los comentarios, y tal vez cinco de ellos, después de la segunda lectura de esta propuesta Esch Se confunde la idea de que debería leer más ...
Resultó que la hipótesis de interés no se cumple, y luego solo muestro cómo usar el prólogo, es una herramienta moderna, en desarrollo y de distribución libre, se puede tomar y formular, solo para que se pueda formular para ver una ventaja.
Diré que el viaje en el tiempo no existe, pero iremos hace una semana, había un Prólogo interesante sobre tres partes en la cinta, ahí fue donde se tocó el tema de resolver un nuevo problema encontrado al azar, tomo este sitio interesante y la tarea más difícil (solo no convertir una cadena en un número)), intentaré hacerlo en el Prolog .
Deja de aumentar el interés, comenzando ...
Una secuencia de números se llama aritmética si consta de al menos tres elementos y si la diferencia entre dos elementos consecutivos es la misma.
Por ejemplo, estas son secuencias aritméticas:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
La siguiente secuencia no es aritmética.
1, 1, 2, 5, 7
Con todo, la diferencia entre los dos vecinos debe ser preservada, ¿solo necesita verificar esto?
Sigue leyendo:
Se da una matriz A de índice cero que consta de N números. Un segmento de subsecuencia de esa matriz es cualquier secuencia de enteros (P0, P1, ..., Pk) tal que 0 ≤ P0 <P1 <... <Pk <N.
Un segmento de subsecuencia (P0, P1, ..., Pk) de la matriz A se llama aritmética si la secuencia A [P0], A [P1], ..., A [Pk-1], A [Pk] es aritmética . En particular, esto significa que k ≥ 2.
La función debe devolver el número de cortes de subsecuencia aritmética en la matriz A.
Wow redacción, necesita averiguar cuántos segmentos puede encontrar, cuántas opciones para las sublistas puede encontrar, para que la diferencia entre elementos adyacentes no difiera.
Es como si las sublistas estuvieran en un gran conjunto de todas las permutaciones de la lista de entrada.
Ejemplo:
Entrada: [2, 4, 6, 8, 10]
Salida: 7
Explicación
Todos los cortes de subsecuencia aritmética son:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
Sé cómo expresar una sublista en un prólogo, esto:
sublists(InputList, SubList):- append(Prefix,Root,InputList), append(SubList,Suffix,Root).
Cómo verificar que la lista del tipo deseado es necesaria para verificar triples:
is_seq(A,B,C]):-AB =:=BC. is_seq(A,B,C|Tail]):-AB =:=BC, is_seq(B,C|Tail]).
Si descartamos las permutaciones de todos los elementos de la lista, resulta que esto no es solo una sublista de los elementos que están cerca, es una sublista que se formó con la omisión de los elementos.
Luego ponlo así:
seq(_,[]). seq([H|T],[H|T1]):-seq(T,T1). seq([_|T],T1):-seq(T,T1).
Dicha regla devolverá todas las sublistas posibles de la lista, pero puede comenzar desde un elemento, o saltearlo, desde el siguiente, también se puede descartar cualquier cantidad al final.
En total, obtenemos una cantidad sobrestimada de soluciones, está claro de inmediato que una lista vacía volverá muchas veces, y las repeticiones no se pueden evitar cuando los elementos se descartan desde el final.
Después de revisar las pruebas propuestas para este problema, resultó que podría haber valores duplicados en la entrada, que para dicha lista [0,1,2,2,2] debería haber 4 soluciones. Cada 2-ka se puede tomar por separado, y esto debe considerarse como un segmento separado, por lo que son adecuadas tres opciones [0,1,2] y una [2,2,2].
Esto es mala suerte, porque el generador de secuencias producirá valores duplicados, pero ¿cómo hacer que el cálculo sea único? Tendrás que marcarlos, hacer que las listas sean diferentes entre sí. Construiré toda la solución sobre la base de generar listas, verificar la condición y contar el número de soluciones. Y qué hacer con la repetición de decisiones ...
Haré una simple numeración de los elementos, dejaré que la lista se convierta en una lista de componentes Valor / Índice, un término estructurado, así lo llaman. Para el ejemplo anterior, esto sería [0 / 1,1 / 2,2 / 3,2 / 4,2 / 5]. Las secuencias generadas por esta entrada serán todas diferentes.
Por lo tanto, puede convertir la lista en una marcada:
label([],[],_). label([A|T],[A/N|T1],N):-N1 is N+1, label(T,T1,N1).
Bueno, y el punto más importante, al verificar la aritmética is_seq, después de una serie de intentos, teniendo en cuenta la lista marcada, esta regla se convirtió en una expresión bastante complicada. Aquí verificamos que los triples números corresponden a la condición, y calculamos la clave de esta solución en particular, para excluir soluciones únicas, se necesitaba una clave, esto ayudará a recopilar todas las claves en una lista y luego contarlas.
En la entrada hay una lista marcada, la salida será el valor clave, calcúlelo como un entero cuyos dígitos son la suma de Valor + Índice para cada elemento.
%is_seq , , is_seq([A/An,B/Bn,C/Cn],2,N):- AB=:=BC, N is 10000*(A+An)+100*(B+Bn)+(C+Cn). is_seq([A/An,B/Bn,C/Cn|T],K,N):- AB=:=BC, is_seq([B/Bn,C/Cn|T],K1,N1), K is K1+1, N is N1+(A+An)*(100**K).
Para contar todas las soluciones, utilizaré la capacidad incorporada para cumplir el objetivo y reunir todas las soluciones únicas en la lista setof (). Simplemente compilar una lista de todas las secuencias resultó ser completamente ineficaz, de aquí surgió la idea de una clave como un valor más simple:
get_number(List,N) :- label(List,ListL,1), setof(Len,K^Sub^(seq(ListL,Sub),is_seq(Sub,K,Len)),Result), length(Result,N),!. get_number(_,0).
Por supuesto, el rendimiento no se expresó particularmente en tal solución.
Aquí hay un texto tan completo del programa, con una lista de pruebas, que se extrae del sitio con la tarea (esto es solo parte de las pruebas):
label([],[],_). label([A|T],[A/N|T1],N):-N1 is N+1, label(T,T1,N1). seq(_,[]). seq([H|T],[H|T1]):-seq(T,T1). seq([_|T],T1):-seq(T,T1). is_seq([A/An,B/Bn,C/Cn],2,N):- AB=:=BC, N is 10000*(A+An)+100*(B+Bn)+(C+Cn). is_seq([A/An,B/Bn,C/Cn|T],K,N):- AB=:=BC, is_seq([B/Bn,C/Cn|T],K1,N1), K is K1+1, N is N1+(A+An)*(100**K). get_number(List,N) :- label(List,ListL,1),setof(Len,K^Sub^(seq(ListL,Sub),is_seq(Sub,K,Len)),Result), length(Result,N),!. get_number(_,0). %unit-tests framework assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). %all test :-assert_are_equal(get_number([2,4,6,8,10],7),true). :-assert_are_equal(get_number([],0),true). :-assert_are_equal(get_number([1],0),true). :-assert_are_equal(get_number([1,2],0),true). :-assert_are_equal(get_number([1,2,3],1),true). :-assert_are_equal(get_number([1,2,3,4],3),true). :-assert_are_equal(get_number([1,2,3,4,5],7),true). :-assert_are_equal(get_number([1,2,3,4,5,6],12),true). :-assert_are_equal(get_number([1,2,3,4,5,6,7],20),true). :-assert_are_equal(get_number([1,2,3,4,5,6,7,8],29),true). :-assert_are_equal(get_number([1,2,3,4,5,6,7,8,9],41),true). :-assert_are_equal(get_number([1,2,3,4,5,6,7,8,9,10],55),true). :-assert_are_equal(get_number([2,2,3,4],2),true). :-assert_are_equal(get_number([0,1,2,2,2],4),true). :-assert_are_equal(get_number([0,2000000000,-294967296],0),true). :-assert_are_equal(get_number([1,1,1],1),true). :-assert_are_equal(get_number([1,1,1,1],5),true). :-assert_are_equal(get_number([1,1,1,1,1],16),true). :-assert_are_equal(get_number([1,1,1,1,1,1],42),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1],99),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1],219),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1],466),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1],968),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1],1981),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1],4017),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1],8100),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1],16278),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],32647),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],65399),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],130918),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],261972),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],524097),true). :-assert_are_equal(get_number([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],1048365),true).
Como resultado decepcionante, aquí hay tal eficiencia:
get_number([2, 4, 6, 8, 10], 7)->ok:0/sec get_number([], 0)->ok:0/sec get_number([1], 0)->ok:0/sec get_number([1, 2], 0)->ok:0/sec get_number([1, 2, 3], 1)->ok:0/sec get_number([1, 2, 3, 4], 3)->ok:0/sec get_number([1, 2, 3, 4, 5], 7)->ok:0/sec get_number([1, 2, 3, 4, 5, 6], 12)->ok:0/sec get_number([1, 2, 3, 4, 5, 6, 7], 20)->ok:0/sec get_number([1, 2, 3, 4, 5, 6, 7, 8], 29)->ok:0/sec get_number([1, 2, 3, 4, 5, 6, 7, 8, 9], 41)->ok:0/sec get_number([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 55)->ok:0/sec get_number([2, 2, 3, 4], 2)->ok:0/sec get_number([0, 1, 2, 2, 2], 4)->ok:0/sec get_number([0, 2000000000, -294967296], 0)->ok:0/sec get_number([1, 1, 1], 1)->ok:0/sec get_number([1, 1, 1, 1], 5)->ok:0/sec get_number([1, 1, 1, 1, 1], 16)->ok:0/sec get_number([1, 1, 1, 1, 1, 1], 42)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1], 99)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1], 219)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1], 466)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 968)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 1981)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 4017)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 8100)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 16278)->ok:0/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 32647)->ok:1/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 65399)->ok:1/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 130918)->ok:3/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 261972)->ok:6/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 524097)->ok:12/sec get_number([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 1048365)->ok:27/sec
Recopilar una lista, incluso solo las claves de decisión, es muy engorroso, pero esta es una decisión declarativa, sin la cual no es posible contar todas las soluciones únicas.
Conclusión
Así es como se formulan las tareas en el lenguaje Prolog; simplemente transferir la declaración del problema al programa está plagado de eficiencia insuficiente. ¿O tal vez en este problema solo hay disponible una solución algorítmica? ¿Qué tan complicado es el proceso?
De nuevo dejo preguntas ...
De todos modos, la búsqueda de respuestas es interesante en nuestra profesión, ¿verdad?