[PYTHON] Versuchen Sie, sich der Teilsumme zu stellen
Guten Abend. Es ist lange her (* ´ω ｀)
Diese Herausforderung stammt aus einem Array, das beliebige Elemente enthält Wählen Sie Elemente nach dem Zufallsprinzip aus und addieren Sie sie. Es geht aber nicht nur ums Aufsummieren Es muss addiert werden, um den Zielwert zu erreichen.
Wählen Sie zum Beispiel eine Kombination aus dem Array, so dass die Summe 20 ist !! Es ist so etwas.
Etwas (; ´ ･ ω ･)
Es scheint ziemlich berühmt und grundlegender Inhalt zu sein, Ich persönlich hatte es schwer (lacht)
Plötzlich, Ich werde den Code setzen.
Partial_sum.py
def solve(Nlist, target, i=0, sum=0):
if i == len(Nlist):
return sum == target
if (solve(Nlist, target, i + 1, sum)):
return True
if (solve(Nlist, target, i + 1, sum + Nlist[i])):
return True
return False
Nlist = [1,3,5,12,7]
target = 11
print(solve(Nlist, target))
Es ist einfacher als Sie denken, aber es ist kompliziert. Zum Beispiel, Zuerst werde ich nur hier schauen.
Partial_sum.py
#Beginnen Sie hier!!
Nlist = [1,3,5,12,7]
target = 11
# ↓[1,3,4...] ↓ 11
print(solve(Nlist, target))
Wirf Nlist und ziele auf lösen. Als Bild ein Array mit Elementen und einem Zielgesamtwert Wirf einfach das Ganze und sag hallo !! Werfen wir einen Blick hinein zu lösen.
Partial_sum.py
#Ich bin ein Bild von Ihrem aktuellen Standort.
#Summe ist die Summe der aktuellen Zahlen.
#Sie sind bei 0,Der Gesamtwert ist ebenfalls 0
def solve(Nlist, target, i=0, sum=0):
#Nlist ist 5 in der Länge, anfangs i==Da es 0 ist, Pass!!
if i == len(Nlist):
return sum == target
#Das?!Es gibt auch eine Lösung in der if-Anweisung. Ich weiß es nicht!!
#Hören wir auf zu lesen(Lol)
if (solve(Nlist, target, i + 1, sum)):
Ich weiß nicht, ich will es rauswerfen (lacht).
Nein! Lauf weg. .. Die Antwort lautet: Wenn Ihre if-Anweisung eine Rekursion enthält, Es durchläuft den rekursiven Prozess und leitet wahr oder falsch ab. Dies bestimmt, ob es in der if-Anweisung enthalten ist oder nicht. Hmm, dumm (lacht)
Möchtest du vorerst gehen? Von lösen (Nlist, Ziel, i + 1, Summe) in if Für ein Abenteuer, um herauszufinden, was vor uns liegt.
Lass uns in der Reihenfolge (`) ノ gehen
i=0.py
def solve(Nlist, target, i=0, sum=0):
#pass!
if i == len(Nlist):
return sum == target
#Die rekursive Verarbeitung wird fortgesetzt, bis die bedingte Anweisung der if-Anweisung entweder True oder False ist.
if (solve(Nlist, target, i + 1, sum)):
return True
i=1.py
#solve(Nlist,target,1(=0+1),0)Ich bin in den rekursiven Prozess eingetreten.
def solve(Nlist, target, i=1, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#Es ist auch ein rekursiver Prozess. Lass uns ohne Angst gehen!!
if (solve(Nlist, target, i + 1, sum)):
return True
i=2.py
#solve(Nlist,target,2(=1+1),0)Ich bin in den rekursiven Prozess eingetreten.
def solve(Nlist, target, i=2, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#Es ist auch ein rekursiver Prozess. Lass uns ohne Angst gehen!!
if (solve(Nlist, target, i + 1, sum)):
return True
i=3.py
#solve(Nlist,target,3(=2+1),0)Ich bin in den rekursiven Prozess eingetreten.
def solve(Nlist, target, i=3, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#Es ist auch ein rekursiver Prozess. Lass uns ohne Angst gehen!!
if (solve(Nlist, target, i + 1, sum)):
return True
i=4.py
#solve(Nlist,target,4(=3+1),0)Ich bin in den rekursiven Prozess eingetreten.
def solve(Nlist, target, i=4, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#Es ist auch ein rekursiver Prozess. Lass uns ohne Angst gehen!!
if (solve(Nlist, target, i + 1, sum)):
return True
i=5.py
#solve(Nlist,target,5(=4+1),0)Ich bin in den rekursiven Prozess eingetreten.
def solve(Nlist, target, i=5, sum=0):
#i == len(Nlist) ==Schließlich habe ich es in 5 in die if-Anweisung am Anfang eingefügt.
if i == len(Nlist):
#Aber leider Summe(0) != target(11)。False
return sum == target
Ich verstehe, ich bin zu i = 5 gegangen, aber es hat sich als falsch herausgestellt. Was passiert danach? .. Das Ergebnis von i = 5 war vorerst False Nehmen wir es zurück zur vorherigen Ebene, i = 4.
i=4.py
def solve(Nlist, target, i=4, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#Die bedingte Aussage in if-Minuten war Flase. Das heißt, die if-Anweisung hier ist bestanden!!
#Gehen wir zur nächsten if-Anweisung!!
if (solve(Nlist, target, i + 1, sum)):
return True
#Hier ich=4 Also lasst uns ersetzen
# (solve(Nlist, target, 4 + 1, sum + Nlist[4]))
# (solve(Nlist, target, 5 , 0 + 7 ) //Nlist = [1,3,5,12,7]
if (solve(Nlist, target, i + 1, sum + Nlist[i])):
return True
Ja, fahren Sie mit der nächsten if-Anweisung fort. Lassen Sie uns noch einmal überprüfen, ob i = 5 ist, mit einer neuen bedingten Anweisung.
i=5.py
#solve(Nlist,target,5,7)Ich bin in den rekursiven Prozess eingetreten.
def solve(Nlist, target, i=5, sum=7):
#i == len(Nlist) == 5 ,Fügen Sie es in die if-Anweisung ein.
if i == len(Nlist):
#Aber leider Summe(7) != target(11)。False
return sum == target
Ich denke, dass die Abbildung bis zu diesem Punkt wie die folgende aussehen wird.
Ein guter Mensch kann dies mit seinem Kopf tun,
Ich konnte es nicht selbst machen, also schrieb ich es auf Papier und organisierte es.
Zurück zur Geschichte, es scheint, dass nichts getan wurde, bis i = 4.
Lassen Sie uns dieses Ergebnis nun an i = 3 melden.
i=3.py
#solve(Nlist,target,3(=2+1),0)Ich bin in den rekursiven Prozess eingetreten.
def solve(Nlist, target, i=3, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#Falsch also pass!!
#Die Summe war noch nie 11 aus der vorherigen Verarbeitung
if (solve(Nlist, target, i + 1, sum)):
return True
# (solve(Nlist, target, 3 + 1, sum + Nlist[3])): //Nlist = [1,3,5,12,7]
# (solve(Nlist, target, 4 , 0 + 12 )):
#Ersetzen Sie die folgenden Bedingungen und geben Sie ein neues if ein!!
if (solve(Nlist, target, i + 1, sum + Nlist[i])):
return True
i=4.py
#solve(Nlist,target,4(=3+1),12)Ich bin in den rekursiven Prozess eingetreten.
def solve(Nlist, target, i=4, sum=12):
#pass!!
if i == len(Nlist):
return sum == target
#Es ist ein rekursiver Prozess. Lass uns ohne Angst gehen!!
if (solve(Nlist, target, i + 1, sum)):
return True
i=5.py
#solve(Nlist,target,5(=4+1),12)Ich bin in den rekursiven Prozess eingetreten.
def solve(Nlist, target, i=5, sum=12):
#i == len(Nlist) == 5 ,Fügen Sie es in die if-Anweisung ein.
if i == len(Nlist):
#Aber leider Summe(12) != target(11)。False
return sum == target
Es war falsch, ich werde einen Bericht zurückgehen.
i=4.py
#solve(Nlist,target,4(=3+1),12)Ich bin in den rekursiven Prozess eingetreten.
def solve(Nlist, target, i=4, sum=12):
#pass!!
if i == len(Nlist):
return sum == target
#Falsch mit Pass!
if (solve(Nlist, target, i + 1, sum)):
return True
#Next↓
if (solve(Nlist, target, i + 1, sum + Nlist[i]))://Nlist = [1,3,5,12,7]
return True
i=5.py
#solve(Nlist,target,5(=4+1),12 + 7)Ich bin in den rekursiven Prozess eingetreten.
def solve(Nlist, target, i=5, sum=19):
#i == len(Nlist) == 5 ,Fügen Sie es in die if-Anweisung ein.
if i == len(Nlist):
#Aber leider Summe(19) != target(11)。False
return sum == target
Machen wir eine Figur.
Ich möchte die Holzstruktur sehen (lacht)
Es ist eine lange Aufgabe, aber es ist in Ordnung, wenn Sie die folgenden Punkte beachten.
** 1. Verfolgen Sie die bedingte Anweisung (rekursiv) der if-Anweisung so lange, bis True und False angezeigt werden. 2. Wenn Wahr oder Falsch angezeigt wird, kehren Sie zur vorherigen Ebene zurück und folgen Sie der Operation genau gemäß der Beschreibung in Lösung **
Ich habe es brillant geschrieben, aber ich wusste es überhaupt nicht Um zu sehen, was sich ändert Ich mischte Pirnt wie folgt.
Partial_sum.py
def solve(Nlist, target, i=0, sum=0):
print(f"i:{i},sum:{sum}") #Zeigen Sie den aktuellen Wert zur besseren Übersicht während der rekursiven Verarbeitung an
if i == len(Nlist):
#Fügen Sie für die rekursive Verarbeitung die bedingte Anweisung ein, wenn Sie am Anfang zur untersten Ebene kommen.
#Drucken Sie also den Kommentar aus, den Sie kennen, wenn Sie diese if-Anweisung eingeben
print(f"Result:i={i},sum={sum}")
print() #Zeilenumbrüche, um vom nächsten Prozess zu trennen
return sum == target
if (solve(Nlist, target, i + 1, sum)):
return True
if (solve(Nlist, target, i + 1, sum + Nlist[i])):
return True
return False
Nlist = [1,3,5,12,7]
target = 11
print(solve(Nlist, target))
Mal sehen, das Ausführungsergebnis !!
Ausführungsergebnis.py
i:0,sum:0
i:1,sum:0
i:2,sum:0
i:3,sum:0
i:4,sum:0
i:5,sum:0
Result:i=5,sum=0
#↑ Vergleiche mit der obigen Abbildung. ich,Entspricht die Änderung der Summe nicht der Zahl?
#Result:i=5,sum=Gibt False zurück, da die Summe nicht 11 ist, da 0 steht
#Ich nach der Rückkehr=Ich bin um 4 zurück.
#Fahren Sie nach der Rückkehr mit der nächsten IF-Anweisung fort.
#Daher ist die nächste Anzeige unten=Es wird zum Zeitpunkt von 5 pirnt.
#Wenn Sie nicht verstehen, kehren Sie bitte zur obigen Seite zurück.
i:5,sum:7
Result:i=5,sum=7
#↑sum(=7) !=Da es 11 ist, ist es falsch.
#Deshalb habe ich=Die beiden if-Anweisungen bei 4 sind beide False.
#Als nächstes ist ich=Es kehrt zum Zeitpunkt 3 zur if-Anweisung zurück, die Verarbeitung ist jedoch dieselbe wie oben.
i:4,sum:12
i:5,sum:12
Result:i=5,sum=12
i:5,sum:19
Result:i=5,sum=19
i:3,sum:5
i:4,sum:5
i:5,sum:5
Result:i=5,sum=5
i:5,sum:12
Result:i=5,sum=12
i:4,sum:17
i:5,sum:17
Result:i=5,sum=17
i:5,sum:24
Result:i=5,sum=24
i:2,sum:3
i:3,sum:3
i:4,sum:3
i:5,sum:3
Result:i=5,sum=3
i:5,sum:10
Result:i=5,sum=10
i:4,sum:15
i:5,sum:15
Result:i=5,sum=15
i:5,sum:22
Result:i=5,sum=22
i:3,sum:8
i:4,sum:8
i:5,sum:8
Result:i=5,sum=8
i:5,sum:15
Result:i=5,sum=15
i:4,sum:20
i:5,sum:20
Result:i=5,sum=20
i:5,sum:27
Result:i=5,sum=27
i:1,sum:1
i:2,sum:1
i:3,sum:1
i:4,sum:1
i:5,sum:1
Result:i=5,sum=1
i:5,sum:8
Result:i=5,sum=8
i:4,sum:13
i:5,sum:13
Result:i=5,sum=13
i:5,sum:20
Result:i=5,sum=20
i:3,sum:6
i:4,sum:6
i:5,sum:6
Result:i=5,sum=6
i:5,sum:13
Result:i=5,sum=13
i:4,sum:18
i:5,sum:18
Result:i=5,sum=18
i:5,sum:25
Result:i=5,sum=25
i:2,sum:4
i:3,sum:4
i:4,sum:4
i:5,sum:4
Result:i=5,sum=4
i:5,sum:11
Result:i=5,sum=11
True
Wie oben erwähnt, nach Erreichen der Grenze, wo ein Übergang nicht möglich ist Die Methode zum Wiederholen des Vorgangs, einen Schritt zurückzugeben und bis zur Grenze zu arbeiten, wird als ** Tiefenprioritätssuche ** bezeichnet. Das Material sagt, dass es relativ einfach zu schreiben ist, Nein, es ist großartig für Anfänger !! (ﾟ Д ﾟ)
Es scheint, dass die Zukunft noch lang ist (* ´ω ｀)
Recommended Posts