Hallo Arbeiter. Ich werde Ihre Aufmerksamkeit nicht lange auf sich ziehen, indem ich den deklarativen Ansatz erkläre. Ich werde versuchen, ein weiteres Problem mit der logischen Programmiersprache zu lösen, als Option für einen deklarativen Blick auf die Formulierung von Problemen und deren Lösungen.

Aufgabe 391. Perfektes Rechteck

Bestimmen Sie bei N achsenausgerichteten Rechtecken mit N> 0, ob sie alle zusammen eine exakte Abdeckung eines rechteckigen Bereichs bilden.
Jedes Rechteck wird als Punkt unten links und oben rechts dargestellt. Beispielsweise wird ein Einheitsquadrat als [1,1,2,2] dargestellt. (Die Koordinate des unteren linken Punkts ist (1, 1) und des oberen rechten Punkts ist (2, 2)).

Beispiel 1: Rechtecke = [
[1,1,3,3],
[3,1,4,2],
[3,2,4,4],
[1,3,2,4],
[2,3,3,4]]
Geben Sie true zurück. Alle 5 Rechtecke bilden zusammen eine exakte Abdeckung eines rechteckigen Bereichs.
...
Beispiel 3: Rechtecke =
[[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[3,2,4,4]]
Geben Sie false zurück. Weil es oben in der Mitte eine Lücke gibt.

Wenn ich an den Wortlaut denke, der zweite Tag vergeht, ist dies sicherlich keine einwöchige Schulung zum Einschalten von Vintage-Lampen , aber ich möchte trotzdem die Ergebnisse der Arbeit an der Aufgabe präsentieren. Es waren mehrere Versuche erforderlich, um alle verfügbaren Tests zu lösen.

Die anfänglichen Daten werden durch eine Liste dargestellt, ich erinnere Sie kurz, die Liste ist [Kopf | Schwanz], wobei Schwanz eine Liste ist, auch die Liste ist leer [] .

Wir formulieren 1

Es ist notwendig, die Gesamtfläche aller Rechtecke zu berechnen, die maximale Größe des Rechtecks ​​zu ermitteln, das sie alle beschreibt, und diese beiden Summen zu vergleichen, wenn dies bedeutet, dass alle Rechtecke die Fläche gleichmäßig abdecken. Stellen Sie gleichzeitig sicher, dass sich die Rechtecke nicht überschneiden. Wir fügen jedes neue Rechteck zur Liste hinzu. Je nach Bedingung sollte es sich nicht überlappen und alle vorherigen überschneiden.

Zu diesem Zweck verwende ich die Schwanzrekursion (auch bekannt als Rekursion beim Abstieg), die „zwingendste“ Art, einen Zyklus darzustellen. In einem solchen "Zyklus" finden wir sofort die Gesamtsumme der Flächen und den minimalen linken und maximalen rechten Winkel des beschreibenden Rechtecks, wandern, sammeln eine allgemeine Liste von Figuren und prüfen, ob es keine Schnittpunkte gibt.

So:

findsum([], Sres,Sres,LConerRes,LConerRes,RConerRes,RConerRes,_). findsum([[Lx,Ly,Rx,Ry]|T], Scur,Sres,LConerCur,LConerRes,RConerCur,RConerRes,RectList):- mincon(Lx:Ly,LConerCur,LConerCur2), maxcon(Rx:Ry,RConerCur,RConerCur2), Scur2 is Scur+(Rx-Lx)*(Ry-Ly), not(chekin([Lx,Ly,Rx,Ry],RectList)), findsum(T, Scur2,Sres,LConerCur2,LConerRes,RConerCur2,RConerRes,[[Lx,Ly,Rx,Ry]|RectList]). 

Bei Prolog sind die Variablen unbekannt, sie können nicht geändert werden, sie sind entweder leer oder haben einen Wert. Dies erfordert einige Variablen, die anfängliche und die resultierende. Wenn wir am Ende der Liste angelangt sind, wird der aktuelle Wert das Ergebnis (die erste Zeile der Regel). Im Gegensatz zu imperativen Sprachen, z Unterstützung Um die Programmzeile zu verstehen, müssen Sie sich den gesamten Pfad vorstellen, der dazu geführt hat, und alle Variablen können ihre eigene "Akkumulationshistorie" haben. Genau dort befindet sich jede Zeile des Programms nur im Kontext der aktuellen Regel, des gesamten Status, der sie beeinflusst hat da ist Einreisebestimmungen.

Also:

 %   mincon(X1:Y1,X2:Y2,X1:Y1):-X1=<X2,Y1=<Y2,!. mincon(_,X2:Y2,X2:Y2). %  maxcon(X1:Y1,X2:Y2,X1:Y1):-X1>=X2,Y1>=Y2,!. maxcon(_,X2:Y2,X2:Y2). 

Um den Winkel darzustellen, wird hier ein „strukturierter Term“ der Form X: Y verwendet. Es ist eine Gelegenheit, mehrere Werte zu einer Struktur zu kombinieren, sozusagen ein Tupel. Nur eine Operation kann ein Funktor sein. Und Clipping "!" Ermöglicht es Ihnen, keine Bedingung in der zweiten Zeile der Regel anzugeben. Dies ist eine Möglichkeit, die Effizienz von Berechnungen zu erhöhen.

Und wie sich später herausstellte, ist es am wichtigsten, die Nichtüberschneidung der Rechtecke zu überprüfen, die sich in der Liste ansammeln:

 %    chekin(X,[R|_]):-cross(X,R),!. chekin(X,[_|T]):-chekin(X,T). %     ,    cross(X,X):-!. cross(X,Y):-cross2(X,Y),!. cross(X,Y):-cross2(Y,X). %,       cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11<X22,X22=<X12,Y11<Y22,Y22=<Y12,!.%rt cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11=<X21,X21<X12,Y11<Y22,Y22=<Y12,!.%lt cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11<X22,X22=<X12,Y11=<Y21,Y21<Y12,!.%rb cross2([X11,Y11,X12,Y12],[X21,Y21,X22,Y22]):-X11=<X21,X21<X12,Y11=<Y21,Y21<Y12. %lb 

Der Schnittpunkt von Rechtecken, dies sind vier Optionen, um die Oberseite des ersten innerhalb des anderen zu treffen.

Und die abschließende Aussage:

 isRectangleCover(Rects):- [[Lx,Ly,Rx,Ry]|_]=Rects, findsum(Rects,0,S,Lx:Ly,LconerX:LconerY,Rx:Ry,RconerX:RconerY,[]),!, S=:= (RconerX-LconerX)*(RconerY-LconerY). 

Bei der Eingabe, einer Liste von Zahlen, nehmen wir den ersten für die Anfangswerte der linken und rechten Ecke, gehen um alle herum, berechnen die Gesamtfläche und überprüfen die erhaltenen Summen. Ich stelle fest, dass, wenn es einen Schnittpunkt der Rechtecke gab, die Suche nach dem Betrag "ablehnt" den "Fall" zurückgibt, was bedeutet, dass es nichts gibt, um die Beträge zu vergleichen. Das gleiche passiert, wenn die Eingabeliste keine einzige Zahl enthält, ein Fehler auftritt und nichts zu überprüfen ist ...

Als Nächstes führe ich diese Implementierung für vorhandene Tests aus und zitiere die ersten 40:

 %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). :-assert_are_equal(isRectangleCover([[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]),true). :-assert_are_equal(isRectangleCover([[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]),false). :-assert_are_equal(isRectangleCover([[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]),false). :-assert_are_equal(isRectangleCover([[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[0,0,4,1]]),false). 

 :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[6,2,8,3],[5,1,6,3],[4,0,5,1],[6,0,7,2],[4,2,5,3],[2,1,4,3],[0,1,2,2],[0,2,2,3],[4,1,5,2],[5,0,6,1]]),true). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),true). :-assert_are_equal(isRectangleCover([[0,0,4,1]]),true). :-assert_are_equal(isRectangleCover([[0,0,3,3],[1,1,2,2]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[1,1,2,2],[2,1,3,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,1,3,2],[1,0,2,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,1,1,2],[0,2,1,3],[0,3,1,4]]),true). :-assert_are_equal(isRectangleCover([[0,0,1,1],[1,0,2,1],[2,0,3,1],[3,0,4,1]]),true). :-assert_are_equal(isRectangleCover([[0,0,2,2],[1,1,3,3],[2,0,3,1],[0,3,3,4]]),false). :-assert_are_equal(isRectangleCover([[0,0,3,1],[0,1,2,3],[1,0,2,1],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[1,1,3,3],[2,2,4,4],[4,1,5,4],[1,3,2,4]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,2,1],[1,0,2,1],[0,2,2,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,2,1],[0,1,2,2],[0,2,1,3],[1,0,2,1]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[0,1,1,2],[1,0,2,1],[0,2,3,3],[2,0,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[6,2,8,3],[5,1,6,3],[6,0,7,2],[4,2,5,3],[2,1,4,3],[0,1,2,2],[0,2,2,3],[4,1,5,2],[5,0,6,1]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,4],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,3],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,5,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,1,1],[0,2,1,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,3,3],[1,1,2,2],[1,1,2,2]]),false). :-assert_are_equal(isRectangleCover([[1,1,4,4],[1,3,4,5],[1,6,4,7]]),false). :-assert_are_equal(isRectangleCover([[0,0,3,1],[0,1,2,3],[2,0,3,1],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,1,1],[1,1,2,2],[1,1,2,2]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[1,1,2,2],[1,1,2,2],[2,1,3,2],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[1,1,2,2],[2,1,3,2],[2,1,3,2],[2,1,3,2],[3,1,4,2]]),false). :-assert_are_equal(isRectangleCover([[0,1,2,3],[0,1,1,2],[2,2,3,3],[1,0,3,1],[2,0,3,1]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,2,1,3],[1,1,2,2],[2,0,3,1],[2,2,3,3],[1,0,2,3],[0,1,3,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[0,1,1,2],[0,2,1,3],[1,0,2,1],[1,0,2,1],[1,2,2,3],[2,0,3,1],[2,1,3,2],[2,2,3,3]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[2,1,4,3],[0,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1]]),false). :-assert_are_equal(isRectangleCover([[0,0,4,1],[7,0,8,2],[5,1,6,3],[6,0,7,2],[4,0,5,1],[4,2,5,3],[2,1,4,3],[-1,2,2,3],[0,1,2,2],[6,2,8,3],[5,0,6,1],[4,1,5,2]]),false). :-assert_are_equal(isRectangleCover([[0,0,1,1],[1,0,2,1],[1,0,3,1],[3,0,4,1]]),false). :-assert_are_equal(isRectangleCover([[1,2,4,4],[1,0,4,1],[0,2,1,3],[0,1,3,2],[3,1,4,2],[0,3,1,4],[0,0,1,1]]),true). 

Und dies ist nicht das Ende, die Aufgabe aus dem Abschnitt „hart“. In 41 Tests bieten sie eine Liste von 10.000 Rechtecken. In allen letzten fünf Tests bekomme ich solche Zeiten in Sekunden:

 test 41:length=10000 goal->ok:212/sec test 42:length=3982 goal->ok:21/sec test 43:length=10222 goal->ok:146/sec test 44:length=10779 goal->ok:41/sec test 45:length=11000 goal->ok:199/sec 

Ich kann die Eingabewerte nicht einbringen, sie passen nicht in den Editor. Ich werde Test 41 wie folgt anhängen.

Formulierung 2

Der vorherige Ansatz, bei dem die Liste zum Sammeln von Zahlen verwendet wird, erweist sich als sehr ineffektiv. Diese Änderung bietet sich an - anstelle der Komplexität n ^ 2 wird n * log (n) erstellt. Sie können den Baum verwenden, um die Schnittpunkte der Liste der Rechtecke zu überprüfen.

Der Binärbaum für Prolog ist ebenfalls ein strukturierter Begriff. Als Liste ist er rekursiv definiert, der Baum ist leer oder enthält einen Wert und zwei Teilbäume .

Ich benutze dafür einen dreifachen Funktor: t (LeftTree, RootValue, RightTree), und der leere Baum wird [] sein.

Ein einfacher Zahlenbaum, dessen Reihenfolge links kleiner und rechts groß ist, kann folgendermaßen ausgedrückt werden:

 add_to_tree(X,[],t([],X,[])). add_to_tree(X,t(L,Root,R),t(L,Root,NewR)):- X<Root,!,add_to_tree(X,R,NewR). add_to_tree(X,t(L,Root,R),t(NewL,Root,R)):- add_to_tree(X,L,NewL). 

In dem klassischen Buch von I. Bratko "Programmieren in Prolog für künstliche Intelligenz" werden viele Realisierungen von Bäumen 2-3, ausgeglichen durch AVL, gegeben ...

Ich schlage vor, das Problem der Anordnung von Rechtecken wie folgt zu lösen: Wenn sich das Rechteck rechts vom anderen befindet, schneiden sie sich nicht, und diejenigen, die sich links befinden, sollten auf Schnittpunkte überprüft werden. Und rechts ist dies, wenn die rechte Ecke von einer kleiner ist als die linke Ecke der zweiten:

 righter([X1,_,_,_],[_,_,X2,_]):-X1>X2. 

Und die Aufgabe, Zahlen in einem Baum zu akkumulieren und nach Schnittpunkten zu suchen, kann folgendermaßen aussehen: Wenn sich rechts von der Wurzel ein neues Rechteck befindet, müssen Sie rechts prüfen, andernfalls überprüfen Sie die Schnittpunkte links:

 treechk(X,[],t([],X,[])). treechk([X1,Y1,X2,Y2],t(L,[X1,Y11,X2,Y22],R),t(L,[X1,Yr,X2,Yr2],R)):- (Y1=Y22;Y2=Y11),!,Yr is min(Y1,Y11),Yr2 is max(Y2,Y22). %union treechk(X,t(L,Root,R),t(L,Root,NewR)):- righter(X,Root),!,treechk(X,R,NewR). treechk(X,t(L,Root,R),t(NewL,Root,R)):- not(cross(X,Root)),treechk(X,L,NewL). 

Sofort einen anderen berücksichtigen Trick Wenn die Rechtecke dieselbe Breite haben und eine gemeinsame Fläche haben, können sie zu einer zusammengefasst und nicht zum Baum hinzugefügt werden. Ändern Sie einfach die Größe des Rechtecks ​​in einem Knoten. Test 41 drängt darauf, da sind solche Daten: [[0, -1,1,0], [0,0,1,1], [0,1,1,2], [0,2,1, 3], [0,3,1,4], [0,4,1,5], [0,5,1,6], [0,6,1,7], [0,7,1, 8], [0,8,1,9], [0,9,1,10], [0,10,1,11], [0,11,1,12], [0,12,1, 13], [0,13,1,14], ..., [0,9998,1,9999]].

Wir kombinieren diese Verbesserungen mit der vorherigen Lösung, ich gebe sie vollständig, mit einigen Verbesserungen:

 treechk(X,[],t([],X,[])). treechk([X1,Y1,X2,Y2],t(L,[X1,Y11,X2,Y22],R),t(L,[X1,Yr,X2,Yr2],R)):- (Y1=Y22;Y2=Y11),!,Yr is min(Y1,Y11),Yr2 is max(Y2,Y22). %union treechk(X,t(L,Root,R),t(L,Root,NewR)):- righter(X,Root),!,treechk(X,R,NewR). treechk(X,t(L,Root,R),t(NewL,Root,R)):- not(cross(X,Root)),treechk(X,L,NewL). righter([X1,_,_,_],[_,_,X2,_]):-X1>X2. findsum([],Sres,Sres,LConerRes,LConerRes,RConerRes,RConerRes,_). findsum([[Lx,Ly,Rx,Ry]|T],Scur,Sres,LConerCur,LConerRes,RConerCur,RConerRes,RectTree):- coner(Lx:Ly,LConerCur,=<,LConerCur2), coner(Rx:Ry,RConerCur,>=,RConerCur2), Scur2 is Scur+abs(Rx-Lx)*abs(Ry-Ly), treechk([Lx,Ly,Rx,Ry],RectTree,RectTree2),!, findsum(T,Scur2,Sres,LConerCur2,LConerRes,RConerCur2,RConerRes,RectTree2). isRectangleCover(Rects):- [[Lx,Ly,Rx,Ry]|_]=Rects, findsum(Rects,0,S,Lx:Ly,LconerX:LconerY,Rx:Ry,RconerX:RconerY,[]),!, S=:= abs(RconerX-LconerX)*abs(RconerY-LconerY). coner(X1:Y1,X2:Y2,Dir,X1:Y1):-apply(Dir,[X1,X2]),apply(Dir,[Y1,Y2]),!. coner(_,XY,_,XY). cross(X,X):-!. cross(X,Y):-cross2(X,Y),!. cross(X,Y):-cross2(Y,X). cross2([X11,Y11,X12,Y12],[_,_,X22,Y22]):-X11<X22,X22=<X12, Y11<Y22,Y22=<Y12,!. %right-top cross2([X11,Y11,X12,Y12],[X21,_,_,Y22]):-X11=<X21,X21<X12, Y11<Y22,Y22=<Y12,!. %left-top cross2([X11,Y11,X12,Y12],[_,Y21,X22,_]):-X11<X22,X22=<X12, Y11=<Y21,Y21<Y12,!. %right-bottom cross2([X11,Y11,X12,Y12],[X21,Y21,_,_]):-X11=<X21,X21<X12, Y11=<Y21,Y21<Y12. %left-bottom 

Hier ist die Laufzeit von "schweren" Tests:

 goal-true->ok:0/sec 41:length=10000 goal-true->ok:0/sec 42:length=3982 goal-true->ok:0/sec 43:length=10222 goal-true->ok:2/sec 44:length=10779 goal-false->ok:1/sec 45:length=11000 goal-true->ok:1/sec 

Ich werde diese Verbesserung beenden, alle Tests werden korrekt bestanden, die Zeit ist zufriedenstellend. Wer interessiert ist, ich schlage vor, Sie versuchen es online oder hier .

Insgesamt

Artikel zur funktionalen Programmierung finden Sie im Portal mit konstanter Häufigkeit. Ich spreche einen anderen Aspekt des deklarativen Ansatzes an - die logische Programmierung. Sie können Aufgaben anhand einer logischen Beschreibung darstellen. Es gibt Fakten und Regeln, Prämissen und Konsequenzen, Beziehungen und rekursive Beziehungen. Die Aufgabenbeschreibung muss in eine Reihe von Beziehungen umgewandelt werden, die sie beschreiben. Das Ergebnis ist eine Folge der Zerlegung des Problems in einfachere Komponenten.

Ein Programm in einer deklarativen Sprache kann als eine Reihe von Anweisungen verwendet werden, die ein Ergebnis erstellen sollen, eine Lösung für ein Problem in seiner erfolgreichen Formulierung. Und die Optimierung kann beispielsweise darin bestehen, dass eine "flüchtige" Beschreibung des Verfahrens zum Steuern von Schnittpunkten von Rechtecken eine Klärung erfordert, und es ist möglich, eine Baumstruktur für effizientere Berechnungen zu konstruieren.

Und ... irgendwo ist Prolog aus den Stilen des Quellcodes verschwunden, vor einem halben Jahr habe ich ihn benutzt. Ich musste eine "Schwester" Erlang angeben. Aber ist das nicht wie "Popularität", Fortran und BASIC sind nicht auf der Liste, wie ist die Bewertung von Sprachen?