Voyageurs, bonjour.
Si vous lisez ceci, je suggère de continuer le matériel "divertissant" que j'ai écrit auparavant. Si vous avez suivi une petite pensée, qui s'est ramifiée en trois articles, mais le message principal était, seulement pour montrer de l'intérêt pour l'approche déclarative. Pour une raison quelconque, ce n'est pas génial, comme si eSCuel n'était pas devenu accessible au public et obligatoire, car sans lui, il est impossible de penser, mais comment traiter les données différemment. Certes, il vaut mieux formuler la tâche et ne pas se soucier de ce que cela signifie.
Passons aux choses sérieuses, j'ai déjà écrit à propos d'essayer de vous amuser, donc je vais continuer à montrer un exemple d'utilisation du prologue, bien que les articles précédents aient montré que l'intérêt pour le python et même aller suscitera l'intérêt de quelques milliers de personnes à la fois, cet intérêt pour les nouvelles d'une nouvelle batterie Tesla, est vue sur la stotysch, et pour écrire des programmes sur le portail razrabotnichestskom pas si peu, vu derrière ce comportement ont été notés à la lecture des commentaires, et peut - être cinq d'entre eux, après la deuxième lecture de cette proposition esch Il confond l'idée qu'il devrait en savoir plus ...
Il s'est avéré que l'hypothèse d'intérêt n'est pas remplie, puis je montre juste comment utiliser le prologue, c'est un outil moderne, en développement et librement distribué, il peut être pris et formulé, seulement pour qu'il puisse être formulé pour voir un avantage.
Je dirai que le voyage dans le temps n'existe pas, mais nous irons il y a une semaine, il y avait un Prolog intéressant sur trois parties de la bande, c'est là que le sujet de la résolution d'un nouveau problème rencontré au hasard a été abordé, je prends ce site intéressant et la tâche la plus difficile (seulement ne pas transformer une chaîne en nombre)), je vais essayer de le faire dans le Prolog .
Arrêtez de susciter l'intérêt, en commençant ...
Une séquence de nombres est appelée arithmétique si elle se compose d'au moins trois éléments et si la différence entre deux éléments consécutifs est la même.
Par exemple, ce sont des séquences arithmétiques:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
La séquence suivante n'est pas arithmétique.
1, 1, 2, 5, 7
Dans l'ensemble, la différence entre les deux voisins doit être préservée, il suffit de vérifier cela?
Lisez la suite:
Un tableau indexé zéro A composé de N nombres est donné. Une tranche de sous-séquence de ce tableau est toute séquence d'entiers (P0, P1, ..., Pk) telle que 0 ≤ P0 <P1 <... <Pk <N.
Une tranche de sous-séquence (P0, P1, ..., Pk) du tableau A est appelée arithmétique si la séquence A [P0], A [P1], ..., A [Pk-1], A [Pk] est arithmétique . En particulier, cela signifie que k ≥ 2.
La fonction doit renvoyer le nombre de tranches de sous-séquences arithmétiques dans le tableau A.
Wow, vous devez savoir combien de tranches vous pouvez rencontrer, combien d'options de sous-listes vous pouvez trouver, afin que la différence entre les éléments adjacents ne diffère pas.
C'est comme si les sous-listes étaient dans un grand ensemble de toutes les permutations de la liste d'entrée.
Exemple:
Entrée: [2, 4, 6, 8, 10]
Sortie: 7
Explication:
Toutes les tranches de sous-séquences arithmétiques sont:
[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]
Je sais comment exprimer une sous-liste dans un prologue, ceci:
sublists(InputList, SubList):- append(Prefix,Root,InputList), append(SubList,Suffix,Root).
Comment vérifier que la liste du type souhaité est nécessaire pour archiver des triplets:
is_seq(A,B,C]):-AB =:=BC. is_seq(A,B,C|Tail]):-AB =:=BC, is_seq(B,C|Tail]).
Si nous rejetons les permutations de tous les éléments de la liste, il s'avère que ce n'est pas seulement une sous-liste des éléments se trouvant à proximité, c'est une telle sous-liste qui a été formée avec un saut d'éléments.
Ensuite, mettez-le comme ceci:
seq(_,[]). seq([H|T],[H|T1]):-seq(T,T1). seq([_|T],T1):-seq(T,T1).
Une telle règle renverra toutes les sous-listes possibles de la liste, mais elle peut commencer à partir d'un élément, ou la sauter, à partir du suivant, toute quantité peut également être éliminée à la fin.
Au total, nous obtenons un nombre surestimé de solutions, il est immédiatement clair qu'une liste vide reviendra plusieurs fois, et les répétitions ne peuvent pas être évitées lorsque des éléments sont supprimés de la fin.
Après avoir examiné les tests proposés pour ce problème, il s'est avéré qu'il pouvait y avoir des valeurs en double à l'entrée, que pour une telle liste [0,1,2,2,2], il devrait y avoir 4 solutions. Chaque 2-ka peut être pris séparément, et cela doit être considéré comme une tranche distincte, donc trois options [0,1,2] et une [2,2,2] conviennent.
C'est malchanceux, car le générateur de séquence produira des valeurs en double, mais comment rendre le calcul unique? Vous devrez les marquer, rendre les listes différentes les unes des autres. Je vais construire la solution entière sur la base de la génération de listes, de la vérification de la condition et du comptage du nombre de solutions. Et que faire des répétitions de décisions ...
Je vais faire une simple numérotation des éléments, laisser la liste se transformer en une liste de composants Valeur / Index, un terme structuré, c'est ainsi qu'ils l'appellent. Pour l'exemple ci-dessus, ce serait [0 / 1,1 / 2,2 / 3,2 / 4,2 / 5]. Les séquences générées par cette entrée seront toutes différentes.
Ainsi, vous pouvez transformer la liste en une liste marquée:
label([],[],_). label([A|T],[A/N|T1],N):-N1 is N+1, label(T,T1,N1).
Eh bien et le point le plus important, vérifier l'arithmétique is_seq, après une série de tentatives, en tenant compte de la liste marquée, cette règle s'est transformée en une expression assez compliquée. Ici, nous vérifions que les triplets de nombres correspondent à la condition, et calculons la clé de cette solution particulière, pour exclure les solutions uniques, une clé était nécessaire, cela aidera à collecter toutes les clés dans une liste puis à les compter.
À l'entrée est une liste marquée, la sortie sera la valeur clé, calculez-la comme un entier dont les chiffres sont la somme de Value + Index pour chaque élément.
%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).
Pour compter toutes les solutions, j'utiliserai la capacité intégrée pour atteindre l'objectif et rassembler toutes les solutions uniques dans la liste setof (). La simple compilation d'une liste de toutes les séquences s'est avérée complètement inefficace, d'où l'idée d'une clé comme valeur plus 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).
Bien entendu, les performances n'étaient pas particulièrement exprimées dans une telle solution.
Voici un tel texte complet du programme, avec une liste de tests, qui est repêché sur le site avec la tâche (ce n'est qu'une partie des tests):
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).
Résultat décevant, voici une telle efficacité:
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
La collecte d'une liste, même uniquement des clés de décision, est très lourde, mais il s'agit d'une décision déclarative, sans laquelle il n'est pas possible de compter toutes les solutions uniques.
Conclusion.
C'est ainsi que les tâches dans le langage Prolog sont formulées; le simple transfert de l'énoncé du problème au programme est lourd d'une efficacité insuffisante. Ou peut-être que dans ce problème, seule une solution algorithmique est disponible? Le processus est-il compliqué?
Encore une fois, je laisse des questions ...
Tout de même, la recherche de réponses est intéressante dans notre métier, non?