Ich bin kürzlich auf diese Frage gestoßen: "Sie erhalten einen booleschen Ausdruck, der aus einer Zeichenfolge der Symbole 'true', 'false', 'und', 'oder' und 'xor' besteht. Zählen Sie die Anzahl der Möglichkeiten, die in Klammern zu setzen Ausdruck so, dass er als wahr ausgewertet wird. Beispielsweise gibt es zwei Möglichkeiten, 'wahr und falsch x oder wahr' in Klammern zu setzen, sodass er als wahr ausgewertet wird. "
Ich wusste, dass es sich um ein dynamisches Programmierproblem handelt, deshalb habe ich versucht, selbst eine Lösung zu finden, die wie folgt lautet. Angenommen, wir haben einen Ausdruck als ABC .... D wobei '.' stellt eine der Operationen dar und oder, oder xor und die Großbuchstaben stehen für wahr oder falsch. Nehmen wir an, die Anzahl der Möglichkeiten für diesen Ausdruck der Größe K, ein wahres Ergebnis zu erzeugen, ist N. Wenn diesem Ausdruck ein neuer boolescher Wert E hinzugefügt wird, gibt es zwei Möglichkeiten, diesen neuen Ausdruck 1 in Klammern zu setzen. ((ABC .... D) .E) dh. mit allen möglichen Klammern von ABC .... D fügen wir am Ende E hinzu. 2. (ABC (DE)) dh. bewerte zuerst DE und finde dann die Anzahl der Möglichkeiten, wie dieser Ausdruck der Größe K wahr werden kann.
Angenommen, T [K] ist die Anzahl der Wege, auf denen der Ausdruck mit der Größe K wahr ist, dann ist T [k] = val1 + val2 + val3, wobei val1, val2, val3 wie folgt berechnet werden.
1) wenn E mit D gruppiert ist.
i) Der Wert von D wird nicht geändert
ii) es kehrt den Wert von D um
im ersten Fall ist val1 = T [K] = N. (Da dies auf den anfänglichen ABC ... D-Ausdruck reduziert wird). Im zweiten Fall wird dp [K] mit umgekehrtem Wert von D neu bewertet, und das ist val1.
2) wenn E mit dem gesamten Ausdruck gruppiert ist.
// val2 enthält die Anzahl von 'true' E wird mit Ausdrücken erzeugt, die 'true' unter allen in Klammern gesetzten Instanzen von ABC ergeben ...... D i) wenn true.E = true, dann val2 = N.
ii) wenn true.E = false, dann ist val2 = 0
// val3 enthält die Anzahl von 'true', die E mit Ausdrücken erzeugt, die 'false' unter allen in Klammern gesetzten Instanzen von ABC ergeben haben ...... D.
iii) wenn false.E = true, dann ist val3 = (2 ^ (K-2) - N) = M dh. Anzahl der Möglichkeiten, wie der Ausdruck mit der Größe K ein falsches Ergebnis erzeugt [2 ^ (K-2) ist die Anzahl der Möglichkeiten, einen Ausdruck der Größe K in Klammern zu setzen].
iv) wenn false.E = false, dann ist val3 = 0
Dies ist die Grundidee, an die ich gedacht hatte, aber als ich nach ihrer Lösung suchte http://people.csail.mit.edu/bdean/6.046/dp/dp_9.swf, war der Ansatz dort völlig anders. Kann mir jemand sagen, was ich falsch mache und wie ich DP besser lösen kann, damit ich Lösungen wie die oben angegebene finden kann?
Danke im Voraus.
quelle
true and (false xor true) = (true and false) xor true(leicht zu erkennen, indem beide auf reduziert werdenfalse xor true).Antworten:
Die Antwort lautet wie bei vielen Dingen:
Üben, üben, üben.
Übrigens glaube ich, dass Sie in Ihrer Lösung in eine Sackgasse geraten sind, indem Sie sehr früh einen trivialen Fehler gemacht haben: "Es gibt zwei Möglichkeiten, diesen neuen Ausdruck in Klammern zu setzen" - gibt es nicht mehr als zwei? Wie wäre es
(A.B.(C.D.E))zum Beispiel?quelle
Ich stimme Occulus zu, dass Übung am dringendsten erforderlich ist, und möchte hinzufügen, dass Sie beim Erkennen der Muster bei Problemen, die mit DP gelöst werden können, aufpassen müssen (dies wird in CLRS ziemlich gut erklärt).
Spoj-Probleme mit dynamischer Programmierung finden Sie hier :)
quelle