[PYTHON] Fordern Sie Problem 5 heraus, das Softwareentwickler in 1 Stunde lösen sollten

Das ursprüngliche Problem ist hier: [Fünf Programmierprobleme, die jeder Softwareentwickler in weniger als 1 Stunde lösen sollte](https://blog.svpino.com/2015/05/07/five-programming-problems-every- Software-Ingenieur-sollte-in-weniger-1-Stunde-lösen können) Japanische Übersetzung: 5 Probleme, die einen Programmierer disqualifizieren, wenn sie nicht innerhalb von 1 Stunde gelöst werden

Ich habe versucht, Problem 5 mit Python herauszufordern.

• Problem 5: Schreiben Sie ein Programm, das die Zahlen 1, 2, ..., 9 in dieser Reihenfolge "+", "-" oder eine beliebige Kombination ausgibt, die 100 ergibt, ohne etwas zu tun. Zum Beispiel 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100. * *

Denkweise

Definieren Sie die Funktion f (n, M) als eine Funktion, die alle Arten zurückgibt, in denen das Ergebnis der Berechnung M ist, wobei Sie Zahlen von 1 bis n verwenden (Rückgabewerte sind eine Liste). Dann lautet die gewünschte Antwort f (9, 100). Wenn die Berechnung unverändert funktioniert (Beispiel: n = 3, M = 123), lautet eine der Antworten M als Zeichenfolge. Zusätzlich kann f (n, M) in kleinere n zerlegt werden. Sie finden alle Berechnungsmethoden, indem Sie die Zerlegung rekursiv wiederholen.

Beispiel: Für f (3, 9)

Erstens gilt die Formel nicht so wie sie ist (123 ≠ 9). f (3, 9) kann auf die folgenden vier Arten zerlegt werden (im Allgemeinen gibt es (n-1) * 2 Arten der Zerlegung). f(2, 6) "+3" f(2, 12) "-3" f(1, -14) "+23" f(1, 32) "-23"

Von diesen können f (1, -14) und f (1, 32) nicht weiter zerlegt werden, und die Gleichung gilt nicht so wie sie sind, so dass sie nicht geeignet sind. f (2, 6) kann weiter in f (1, 5) "+1" und f (1, 7) "-1" zerlegt werden, aber keine der Gleichungen gilt. Da f (2, 12) ein Muster ist, in dem die Gleichung so bleibt, wie sie ist, ist "12" eine Lösung. Es kann auch in f (1, 11) +1 und f (1, 13) -1 zerlegt werden, aber keines ist geeignet. Daher wird "12-3" als einzige Lösung gesucht.

Wenn f (9, 100) berechnet wird, werden vom Fragesteller 11 Muster präsentiert (Lösung zu Problem 5. -Einige-andere-Gedanken-über-diese-Art-von-Fragen)) hat die gleiche Lösung.

Die Verwendung einer solchen rekursiven Funktion ist jedoch etwas unangenehm, und im Fall von Python tritt ein Ausführungsfehler auf, wenn die rekursive Tiefe 1000 überschreitet (Referenz. % 20script /% E3% 82% A2% E3% 82% A4% E3% 83% 87% E3% 83% B3% E3% 83% 86% E3% 82% A3% E3% 83% 86% E3% 82% A3)). In diesem Beispiel überschreitet die Tiefe 9 nicht, daher ist dies in Ordnung. Im Antwortbeispiel war es auch ein Mechanismus, der andere Zahlen als 1 bis 9 verarbeiten kann, aber es ist schwach, dass ich es mit meiner Methode nicht tun kann.

def fun5(n, M):
    digits = "123456789"[0:n]
    out = []
    if int(digits) == M:
        out += [ digits ] 
    for i in xrange(1, n):
        out += map(lambda z: z + "+" + digits[-i:n], fun5(n - i, M - int(digits[-i:n])) )
        out += map(lambda z: z + "-" + digits[-i:n], fun5(n - i, M + int(digits[-i:n])) )
    return out    

print fun5(2, 3)
print fun5(5, 168)
print fun5(9, 100)
#['1+2']
#['123+45']
#['1+23-4+56+7+8+9', '12+3-4+5+67+8+9', '1+2+34-5+67-8+9', '1+2+3-4+5+6+78+9', '123-4-5-6-7+8-9', '123+45-67+8-9', '1+23-4+5+6+78-9', '12-3-4+5-6+7+89', '12+3+4+5-6-7+89', '123-45-67+89', '123+4-5+67-89']