Ich versuche ein C ++ - Programm zu schreiben, das wie das Spiel 24 funktioniert. Für diejenigen, die nicht wissen, wie es gespielt wird, versuchen Sie im Grunde, durch die vier algebraischen Operatoren von + vier beliebige Zahlen zu finden , -, /, * und Klammern.
Sagen Sie als Beispiel, jemand gibt 2,3,1,5 ein ((2 + 3) * 5) - 1 = 24
Es war relativ einfach, die Funktion zu codieren, um zu bestimmen, ob drei Zahlen 24 ergeben können, wegen der begrenzten Anzahl von Positionen für Klammern, aber ich kann nicht herausfinden, wie es effizient codiert, wenn vier Variablen eingegeben werden.
Ich habe jetzt einige Permutationen, aber ich kann immer noch nicht alle Fälle aufzählen, weil ich nicht weiß, wie ich für die Fälle codieren soll, in denen die Operationen gleich sind.
Was ist der einfachste Weg, das RPN zu berechnen? Ich bin auf viele Seiten wie diese gestoßen: Ссылка aber als Anfänger bin ich mir nicht sicher, wie ich es umsetzen soll.
%Vor%Also, der einfache Weg ist, durch alle möglichen Kombinationen zu permutieren. Dies ist ein wenig schwierig, die Reihenfolge der Zahlen kann wichtig sein, und sicherlich ist die Reihenfolge der Operationen.
Eine Beobachtung ist, dass Sie versuchen, alle möglichen Ausdrucksbäume mit bestimmten Eigenschaften zu erzeugen. Eine Eigenschaft ist, dass der Baum immer genau 4 Blätter hat. Das bedeutet, dass der Baum auch immer genau 3 interne Knoten haben wird. Es gibt nur 3 mögliche Formen für einen solchen Baum:
%Vor%In jedem Punkt für A können Sie eine der vier Operationen ausführen. In jedem Punkt für N können Sie eine der Nummern haben. Aber jede Zahl kann nur für ein N erscheinen.
Dies als eine Brute-Force-Suche zu kodieren sollte nicht zu schwer sein, und ich denke, dass, nachdem Sie die Dinge so gemacht haben, es einfacher wird, über Optimierungen nachzudenken.
Zum Beispiel sind + und * kommutativ. Dies bedeutet, dass Spiegel, die die linken und rechten Kinder dieser Operationen spiegeln, keine Wirkung haben. Es könnte möglich sein, die Suche durch all diese Flips zu reduzieren.
Jemand anders erwähnte die RPN-Notation. Die Bäume bilden das direkt ab. Hier ist eine Liste aller möglichen Bäume in RPN:
%Vor%Das sind 4 * 3 * 2 = 24 Möglichkeiten für Zahlen, 4 * 4 * 4 = 64 Möglichkeiten für Operationen, 24 * 64 * 5 = 7680 Gesamtmöglichkeiten für eine gegebene Menge von 4 Zahlen. Einfach zählbar und in einem modernen System in Sekundenbruchteilen auswertbar. Verdammt, selbst im Basic auf meinem alten Atari 8 bit würde ich wetten, dass dieses Problem bei einer gegebenen Gruppe von 4 Zahlen nur Minuten dauern würde.
Sie können einfach die umgekehrte polnische Notation verwenden, um die möglichen Ausdrücke zu generieren, die die Notwendigkeit von Klammern überflüssig machen sollten. p>
Eine absolut naive Möglichkeit wäre, alle möglichen Folgen von 4 Ziffern und 3 Operatoren zu generieren (ohne Beachtung der Gültigkeit als RPN), vorausgesetzt, es ist in RPN und versucht es zu bewerten. Sie werden einige Fehlerfälle (wie in ungültigen RPN-Strings) treffen. Die Gesamtzahl der Möglichkeiten (wenn ich richtig berechnet habe) ist ~ 50.000.
Ein schlauer Weg sollte es auf ~ 7500 bringen Ich glaube (64 * 24 * 5, um genau zu sein): Erzeuge eine Permutation der Ziffern (24 Wege), erzeuge ein Triplett von 3 Operatoren (4 ^ 3 = 64) Weisen Sie nun die Operatoren zwischen die Ziffern, um sie als RPN gültig zu machen (es gibt 5 Möglichkeiten, siehe Omnifariöse Antwort).
Sie sollten Permutationsgeneratoren und RPN-Rechner leicht im Internet finden können.
Hoffe das hilft!
PS: Nur zur Info: RPN ist nichts anderes als die Postorder-Traversierung des entsprechenden Ausdrucksbaums, und für d Ziffern ist die Zahl d! * 4 ^ (d-1) * Wählen Sie (2 (d-1), (d-1)) / d. (Der letzte Begriff ist eine katalanische Nummer).
Bearbeitet : Die folgende Lösung ist falsch . Wir müssen auch die Zahlen berücksichtigen, die nur mit x_2 und x_4 und nur mit x_1 und x_4 möglich sind. Dieser Ansatz kann immer noch funktionieren, aber er wird etwas komplexer (und noch weniger effizient) sein. Entschuldigung ...
Angenommen wir haben vier Zahlen x_1, x_2, x_3, x_4. Schreiben Sie
%Vor%Dann können wir den Satz, an dem wir interessiert sind, umschreiben, den ich aufrufen werde
%Vor%als
%Vor%Also soll ein Algorithmus alle möglichen Zahlen in S erzeugen, und dann jede Zahl s in S verwenden, um einen Teil von T zu erzeugen. (Dies wird relativ leicht auf n statt nur 4 verallgemeinern.)
Hier ist ein grobes, nicht getestetes Codebeispiel:
%Vor% Wenn Sie denselben Operator zweimal verwenden dürfen, möchten Sie die Operatoren wahrscheinlich nicht in die Zahlen mischen. Verwenden Sie stattdessen möglicherweise drei 0 als Platzhalter für die Operationen (keine der 4 Zahlen sind 0, oder?) Und verwenden Sie eine andere Struktur, um zu bestimmen, welche Operationen verwendet werden.
Die zweite Struktur könnte ein vector<int> sein, initialisiert mit drei 1en, gefolgt von drei Nullen. Die Nullen entsprechen den Nullen in der Zahl vector . Wenn einer 0 vorangestellte 1 vorangestellt ist, lautet die entsprechende Operation + , wenn vor einer 1 steht, ist es - , usw. Beispiel:
Gehen Sie die Operationsmöglichkeiten mit next_permutation in einer inneren Schleife vor.
Übrigens, Sie können auch früh zurückkehren, wenn die Anzahl-Permutation ein ungültiger Postfix-Ausdruck ist. Alle Permutationen des obigen Beispiels kleiner als 6708090 sind ungültig, und alle größeren sind gültig, also könntest du mit 9876000 anfangen und dich mit prev_permutation nach unten arbeiten.
Eine Sache, die dies schneller als normal machen könnte, ist die Parallelisierung. Schau dir OpenMP an. Mit diesem wird mehr als eine Überprüfung auf einmal durchgeführt (Ihre "alg" -Funktion). Wenn Sie also eine Dual / Quad-Core-CPU haben, sollte Ihr Programm schneller sein.
Das heißt, wenn, wie oben vorgeschlagen, das Problem NP-vollständig ist, wird es schneller, nicht unbedingt schnell.
Ich habe so etwas schon mal geschrieben. Sie benötigen einen rekursiven Evaluator. Call evaluate, wenn du "(" rufe wieder auswerten, ansonsten mit Ziffern und Operatoren laufen bis du auf ") triffst, gib nun das Ergebnis der - + * / -Operationen zurück, die die Instanz über dir auswerten
Tags und Links c++