Reisende, hallo.
Wenn Sie dies lesen, schlage ich vor, das "unterhaltsame" Material fortzusetzen, das ich zuvor geschrieben habe. Wenn Sie einem kleinen Gedanken gefolgt sind, der sich in drei Artikel verzweigte, aber die Hauptbotschaft war - nur um Interesse an dem deklarativen Ansatz zu zeigen. Aus irgendeinem Grund ist es nicht großartig, als ob eSCuel nicht öffentlich verfügbar und obligatorisch geworden wäre, denn ohne es ist es unmöglich, darüber nachzudenken, wie die Daten anders verarbeitet werden können. Es ist zwar besser, die Aufgabe zu formulieren und sich keine Gedanken darüber zu machen, was dies bedeutet.
Kommen wir zur Sache, ich habe vorher geschrieben, dass ich versuchen soll, Sie zu amüsieren, und ich werde weiterhin ein Beispiel für die Verwendung des Prologs zeigen, obwohl die vorherigen Artikel gezeigt haben, dass das Interesse an Python und sogar Go sofort das Interesse für ein paar tausend Menschen wecken wird, das Interesse an Nachrichten über eine neue Batterie Tesla ist stotysch Ansichten und für Programme auf dem Portal razrabotnichestskom nicht so wenige, hinter diesem Verhalten gesehen wurden zur Kenntnis genommen , die Kommentare zu lesen, und vielleicht fünf von ihnen, nach der zweiten Lesung dieses Vorschlags esch schreiben Es verwirrt die Idee, dass es sollte mehr lesen ...
Es stellte sich heraus, dass die Hypothese von Interesse nicht erfüllt ist, und dann zeige ich nur, wie man den Prolog verwendet. Es ist ein modernes, sich entwickelndes und frei verteiltes Werkzeug. Es kann nur genommen und formuliert werden, um einen Vorteil zu erkennen.
Ich werde sagen, dass es keine Zeitreise gibt, aber wir werden vor einer Woche gehen. Es gab einen interessanten Prolog über drei Teile auf dem Band. Hier wurde das Thema der Lösung eines zufällig aufgetretenen neuen Problems angesprochen. Ich nehme diese interessante Seite und die schwierigste Aufgabe (nur) Ich verwandle einen String nicht in eine Zahl. Ich werde versuchen, dies im Prolog zu tun.
Hör auf, Interesse zu wecken, fang an ...
Eine Folge von Zahlen wird als Arithmetik bezeichnet, wenn sie aus mindestens drei Elementen besteht und wenn die Differenz zwischen zwei aufeinanderfolgenden Elementen gleich ist.
Dies sind beispielsweise arithmetische Folgen:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
Die folgende Sequenz ist nicht arithmetisch.
1, 1, 2, 5, 7
Alles in allem sollte der Unterschied zwischen den beiden Nachbarn erhalten bleiben, müssen Sie dies nur überprüfen?
Lesen Sie weiter:
Es wird ein nullindexiertes Array A gegeben, das aus N Zahlen besteht. Ein Teilsequenzschnitt dieses Arrays ist eine beliebige Folge von ganzen Zahlen (P0, P1, ..., Pk), so dass 0 ≤ P0 <P1 <... <Pk <N.
Eine Teilsequenzscheibe (P0, P1, ..., Pk) des Arrays A wird als Arithmetik bezeichnet, wenn die Folge A [P0], A [P1], ..., A [Pk-1], A [Pk] arithmetisch ist . Dies bedeutet insbesondere, dass k ≥ 2 ist.
Die Funktion sollte die Anzahl der arithmetischen Teilsequenzscheiben im Array A zurückgeben.
Wow-Formulierung, Sie müssen herausfinden, wie viele Slices Sie treffen können, wie viele Optionen für Unterlisten Sie finden können, damit sich der Unterschied zwischen benachbarten Elementen nicht unterscheidet.
Es ist, als ob sich die Unterlisten in einem großen Satz aller Permutationen der Eingabeliste befinden.
Beispiel:
Eingabe: [2, 4, 6, 8, 10]
Ausgabe: 7
Erklärung:
Alle arithmetischen Teilsequenzscheiben sind:
[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]
Ich weiß, wie man eine Unterliste in einem Prolog ausdrückt:
sublists(InputList, SubList):- append(Prefix,Root,InputList), append(SubList,Suffix,Root).
So überprüfen Sie, ob die Liste des gewünschten Typs erforderlich ist, um Dreiergruppen einzuchecken:
is_seq(A,B,C]):-AB =:=BC. is_seq(A,B,C|Tail]):-AB =:=BC, is_seq(B,C|Tail]).
Wenn wir die Permutationen aller Elemente der Liste verwerfen, stellt sich heraus, dass dies nicht nur eine Unterliste der in der Nähe stehenden Elemente ist, sondern eine solche Unterliste, die unter Weglassen der Elemente erstellt wurde.
Dann sagen Sie es so:
seq(_,[]). seq([H|T],[H|T1]):-seq(T,T1). seq([_|T],T1):-seq(T,T1).
Eine solche Regel gibt alle möglichen Unterlisten aus der Liste zurück, kann jedoch von einem Element ausgehen oder vom nächsten überspringen. Am Ende kann auch eine beliebige Menge verworfen werden.
Insgesamt erhalten wir eine überschätzte Anzahl von Lösungen, es ist sofort klar, dass eine leere Liste viele Male zurückgegeben wird, und Wiederholungen können nicht vermieden werden, wenn Elemente vom Ende entfernt werden.
Nach Durchsicht der vorgeschlagenen Tests für dieses Problem stellte sich heraus, dass es am Eingang doppelte Werte geben könnte. Für eine solche Liste [0,1,2,2,2] sollten 4 Lösungen vorhanden sein. Jedes 2-ka kann separat genommen werden, und dies sollte als separate Scheibe betrachtet werden, daher sind drei Optionen [0,1,2] und eine [2,2,2] geeignet.
Dies ist ein Pech, da der Sequenzgenerator doppelte Werte erzeugt, aber wie kann die Berechnung nur eindeutig gemacht werden? Sie müssen sie markieren und die Listen voneinander unterscheiden. Ich werde die gesamte Lösung auf der Grundlage der Erstellung von Listen, der Überprüfung des Zustands und der Zählung der Anzahl der Lösungen erstellen. Und was tun mit Wiederholungen von Entscheidungen ...
Ich werde die Elemente einfach nummerieren und die Liste in eine Liste der Komponenten verwandeln. Wert / Index, ein strukturierter Begriff, so nennen sie ihn. Für das obige Beispiel wäre dies [0 / 1,1 / 2,2 / 3,2 / 4,2 / 5]. Die durch diese Eingabe erzeugten Sequenzen sind alle unterschiedlich.
Sie können die Liste also in eine markierte Liste verwandeln:
label([],[],_). label([A|T],[A/N|T1],N):-N1 is N+1, label(T,T1,N1).
Nun, und der wichtigste Punkt, die Überprüfung auf is_seq-Arithmetik, nach einer Reihe von Versuchen unter Berücksichtigung der markierten Liste, wurde diese Regel zu einem ziemlich komplizierten Ausdruck. Hier überprüfen wir, ob die Dreifachzahlen der Bedingung entsprechen, und berechnen den Schlüssel dieser bestimmten Lösung, um eindeutige Lösungen auszuschließen. Es wurde ein Schlüssel benötigt. Dies hilft, alle Schlüssel in einer Liste zu sammeln und sie dann zu zählen.
Bei der Eingabe befindet sich eine markierte Liste. Die Ausgabe ist der Schlüsselwert. Berechnen Sie sie als Ganzzahl, deren Ziffern die Summe aus Wert + Index für jedes Element sind.
%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).
Um alle Lösungen zu zählen, werde ich die integrierte Fähigkeit nutzen, um das Ziel zu erreichen und alle eindeutigen Lösungen in der setof () -Liste zu sammeln. Das einfache Zusammenstellen einer Liste aller Sequenzen erwies sich als völlig ineffektiv. Von hier aus kam die Idee eines Schlüssels als einfacheren Wert:
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).
Natürlich wurde die Leistung in einer solchen Lösung nicht besonders ausgedrückt.
Hier ist ein so vollständiger Text des Programms mit einer Liste von Tests, die von der Site mit der Aufgabe ausgefeilt werden (dies ist nur ein Teil der 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).
Als enttäuschendes Ergebnis ist hier eine solche Effizienz:
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
Das Sammeln einer Liste, auch nur von Entscheidungsschlüsseln, ist sehr umständlich, aber dies ist eine deklarative Entscheidung, ohne die es nicht möglich ist, alle eindeutigen Lösungen zu zählen.
Fazit.
Auf diese Weise werden Aufgaben in der Prolog-Sprache formuliert. Die einfache Übertragung der Problemstellung auf das Programm ist mit unzureichender Effizienz behaftet. Oder ist in diesem Problem nur eine algorithmische Lösung verfügbar? Wie kompliziert ist der Prozess?
Wieder hinterlasse ich Fragen ...
Trotzdem ist die Suche nach Antworten für unseren Beruf interessant, oder?