Olá, viajantes.

Se você está lendo isso, sugiro continuar o material "divertido" que escrevi antes. Se você seguisse um pouco de reflexão, que se ramificava em três artigos, mas a mensagem principal era apenas mostrar interesse na abordagem declarativa. Por alguma razão, não é ótimo, como se o eSCuel não se tornasse publicamente disponível e obrigatório, porque sem ele é impossível pensar em como os dados podem ser processados ​​de maneira diferente. É verdade que é melhor formular a tarefa e não se preocupar com o que isso significa.

Vamos ao que interessa, escrevi antes sobre tentar diverti-lo, por isso continuarei mostrando um exemplo de uso do prólogo, embora artigos anteriores tenham mostrado que o interesse em python e até mesmo vá despertar interesse imediatamente para algumas milhares de pessoas, que se interessam por notícias sobre uma nova bateria a Tesla, é vista stotysch, e para escrever programas no razrabotnichestskom portal não tão poucos, visto por trás deste comportamento foram observados na leitura dos comentários, e talvez cinco deles, após a segunda leitura desta proposta esch Isso confunde a idéia de que ele deve ler mais ...

Verificou-se que a hipótese de interesse não é cumprida e, em seguida, apenas mostro como usar o prólogo, é uma ferramenta moderna, em desenvolvimento e distribuída gratuitamente, que pode ser tomada e formulada, apenas para que possa ser formulada para obter uma vantagem.

Eu diria que a viagem no tempo não existe, mas iremos a uma semana atrás, houve um Prolog interessante sobre três partes da fita, onde foi abordado o tópico de resolver um novo problema encontrado aleatoriamente, eu escolho este site interessante e a tarefa mais difícil (apenas não transformando uma string em um número)), tentarei fazer isso no Prolog .

Pare de aumentar o interesse, começando ...

Tarefa 446 aritmética-fatias-ii-subsequência

Uma sequência de números é chamada aritmética se consistir em pelo menos três elementos e se a diferença entre dois elementos consecutivos for a mesma.
Por exemplo, estas são sequências aritméticas:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
A sequência a seguir não é aritmética.
1, 1, 2, 5, 7

Em suma, a diferença entre os dois vizinhos deve ser preservada, basta verificar isso?
Continue lendo:

É fornecida uma matriz A indexada a zero, consistindo em N números. Uma fatia de subsequência dessa matriz é qualquer sequência de números inteiros (P0, P1, ..., Pk) tal que 0 ≤ P0 <P1 <... <Pk <N.
Uma fatia de subsequência (P0, P1, ..., Pk) da matriz A é chamada aritmética se a sequência A [P0], A [P1], ..., A [Pk-1], A [Pk] for aritmética . Em particular, isso significa que k ≥ 2.
A função deve retornar o número de fatias de subsequência aritmética na matriz A.

Uau, você precisa descobrir quantas fatias pode encontrar, quantas opções de sublistas você encontra, para que a diferença entre itens adjacentes não seja diferente.

É como se as sublistas estivessem em um grande conjunto de todas as permutações da lista de entrada.

Exemplo:
Entrada: [2, 4, 6, 8, 10]
Saída: 7
Explicação:
Todas as fatias de subsequência aritmética são:
[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]

Eu sei como expressar uma sublist em um prólogo, isto:

sublists(InputList, SubList):- append(Prefix,Root,InputList), append(SubList,Suffix,Root). 

Como verificar se a lista do tipo desejado é necessária para o check-in triplo:

 is_seq(A,B,C]):-AB =:=BC. is_seq(A,B,C|Tail]):-AB =:=BC, is_seq(B,C|Tail]). 

Se descartamos as permutações de todos os elementos da lista, acontece que essa não é apenas uma sub-lista dos elementos que estão próximos, é uma sub-lista que foi formada com a omissão dos elementos.

Em seguida, coloque assim:

 seq(_,[]). seq([H|T],[H|T1]):-seq(T,T1). seq([_|T],T1):-seq(T,T1). 

Essa regra retornará todas as sublistas possíveis da lista, mas pode começar de um elemento ou ignorá-lo do próximo, e também qualquer quantidade pode ser descartada no final.

No total, obtemos um número superestimado de soluções; fica imediatamente claro que uma lista vazia retornará muitas vezes e as repetições não podem ser evitadas quando os elementos são descartados do final.

Depois de revisar os testes propostos para esse problema, verificou-se que poderia haver valores duplicados na entrada, que, para essa lista [0,1,2,2,2], deveria haver 4 soluções. Cada 2-ka pode ser tomado separadamente, e isso deve ser considerado como uma fatia separada; portanto, três opções [0,1,2] e uma [2,2,2] são adequadas.

Isso é má sorte, porque o gerador de sequência produzirá valores duplicados, mas como tornar o cálculo único? Você precisará marcá-los, diferenciar as listas. Criarei toda a solução com base na geração de listas, verificação da condição e contagem do número de soluções. E o que fazer com repetições de decisões ...

Vou fazer uma numeração simples dos elementos, deixar a lista se transformar em uma lista de componentes Valor / Índice, um termo estruturado, é assim que eles chamam. Para o exemplo acima, isso seria [0 / 1,1 / 2,2 / 3,2 / 4,2 / 5]. As seqüências geradas por esta entrada serão todas diferentes.

Portanto, você pode transformar a lista em uma marcada:

 label([],[],_). label([A|T],[A/N|T1],N):-N1 is N+1, label(T,T1,N1). 

Bem, e o ponto mais importante, ao procurar a aritmética is_seq, após uma série de tentativas, levando em consideração a lista marcada, essa regra se transformou em uma expressão bastante complicada. Aqui, verificamos que os triplos números correspondem à condição e calculamos a chave dessa solução específica. Para excluir soluções exclusivas, era necessária uma chave. Isso ajudará a coletar todas as chaves de uma lista e depois contá-las.

Na entrada, há uma lista marcada, a saída será o valor da chave, calcule-o como um número inteiro cujos dígitos são a soma do 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 as soluções, usarei a capacidade incorporada para cumprir a meta e coletar todas as soluções exclusivas na lista setof (). Simplesmente compilar uma lista de todas as seqüências acabou sendo completamente ineficaz; daí surgiu a ideia de uma chave como um valor mais simples:

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

Obviamente, o desempenho não foi particularmente expresso em tal solução.

Aqui está um texto completo do programa, com uma lista de testes, que é extraída do site com a tarefa (isso é apenas parte dos testes):

 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, aqui está uma eficiência:

 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 

Coletar uma lista, mesmo que apenas chaves de decisão, é muito complicado, mas é uma decisão declarativa, sem a qual não é possível contar todas as soluções exclusivas.

Conclusão

É assim que as tarefas na linguagem Prolog são formuladas; simplesmente transferir a declaração do problema para o programa é repleto de eficiência insuficiente. Ou talvez neste problema apenas uma solução algorítmica esteja disponível? Quão complicado é o processo?

Mais uma vez deixo perguntas ...

Mesmo assim, a busca por respostas é interessante em nossa profissão, certo?