Schreiben Sie eine Funktion, die eine Ziffernfolge und einen Zielwert angibt. Sie gibt aus, wo + und s zwischen den Ziffern stehen, damit sie genau mit dem Zielwert kombiniert werden. Beachten Sie, dass es mehrere Antworten geben kann, egal, welche Sie drucken.number combination algorithm
Beispiele:
"1231231234",11353 -> "12*3+1+23*123*4"
"3456237490",1185 -> "3*4*56+2+3*7+490"
"3456237490",9191 -> "no solution"
Dies kann entweder durch Rückzieher oder durch dynamische Programmierung gelöst werden.
Wenn Sie einen N-Stellenwert haben, gibt es N-1 mögliche Steckplätze für die Operatoren + oder *. So rohe Gewalt gibt es 3^(N-1) Möglichkeiten. Alle diese Tests sind ineffizient.
ABER
Ihre Beispiele sind alle 10 Ziffern. 3^9 = 19683, also rohe Gewalt ist FEIN! Keine Notwendigkeit, einen Züchter zu bekommen.
Alles, was Sie tun müssen, ist durch alle 19683 Fälle zu durchlaufen, jedes Mal eine Zeichenfolge für diesen Fall erstellen und den Ausdruck zu bewerten. Die Auswertung des Ausdrucks ist eine einfache Aufgabe. Das Iterieren ist einfach (benutze einfach einen inkrementierenden Wert, du kannst den Status des ersten Slots durch (i% 3) lesen, was dir "no operator" "+" oder "*" gibt, der Status des zweiten Slots ist (i/3)% 3, der Zustand des dritten Steckplatzes ist (i/9)% 3 usw.
Selbst mit grober Syntaxanalyse sind CPUs schnell.
Die Brute-Force-Option beginnt nach etwa 20 Ziffern hässlich zu werden, und Sie müssten wechseln, um cleverer zu werden.
Der „gescheiter“ -Ansatz (dynamische Programmierung verwendet wird) ist im Grunde diese:
Für jede Teilkette der ursprünglichen Zeichenfolge, alle möglichen Werte herauszufinden, es schaffen. (z. B. in Ihrem ersten Beispiel "12" kann entweder 1 + 2 = 3 oder 1 * 2 = 2)
Es kann viele verschiedene Kombinationen geben, aber viele von ihnen werden Duplikate sein. (Außerdem sollten Sie alle Kombinationen ignorieren, die größer als das Ziel sind).
Wenn Sie also ein "+" oder ein "*" hinzufügen, können Sie sich vorstellen, dass es zwei Teilstrings des Strings kombiniert. (Und da Sie die möglichen Werte für jeden Teilstring haben, können Sie sehen, ob eine solche Kombination möglich ist)
Diese Werte können auf ähnliche Weise generiert werden: Versuchen Sie, den Teilstring auf alle möglichen Arten aufzuteilen, und kombinieren Sie die verschiedenen Werte in jeder Hälfte der Teilzeichenfolge.
Die Gesamtzahl der "Zustände" ist dann etwas wie | S |^2 * Ziel - für Ihren Beispielfall ist es schlechter als die Brute-Force-Methode. Wenn Sie jedoch eine Zeichenfolge der Länge 1000 und ein Ziel von beispielsweise 5000 hätten, wäre das Problem mit der dynamischen Programmierung lösbar.
Google Code Jam hatte eine erweiterte Version dieses Problems im vergangenen Jahr (in Round 1C), Ugly Numbers genannt. Sie können diesen Link aufrufen und auf "Wettbewerbsanalyse" klicken, um einige Lösungsansätze für dieses Problem zu erhalten, die auf eine große Anzahl von Ziffern erweitert werden können.
Wenn dies für die Gaming-Programmierer-Position ist, verwenden Sie nicht den Brute-Force-Ansatz. Ich habe das gemacht, aber das ist vor ein paar Jahren gescheitert. Später von jemandem in diesem dynamischen Programmierung Ansatz gehört, ist derjenige, der den Job bekommt.
+1 für die Schätzung der Umstellung von Brute-Force zu Cleverness. – RBerteig