Python Liste Summe von Integer?
Wie kann ich mit einer rekursiven Funktion eine Unterliste einer Liste ausgeben, dessen Elemente sich zu einer Zahl s aufsummieren? Also zB summenListe(l, s).
Dabei ist der Parameter l die Liste und s die Zahl zu die sich die Elemente aufsummieren sollen.
3 Antworten
Falls es nicht möglich sein sollte, soll die Funktion den Rückgabewert None liefern. Danke schonmal für die Antwort!
Das ist eine ungenaue Fragestellung. Das kann eine ziemlich simple oder etwas schwierigere Aufgabe sein. In der einfachsten Interpretation - von vorn schrittweise durcharbeiten, bis zumindest die Zahl erreicht wird, könnte es z.B. so aussehen:
def sum_sub(n: int, l: list):
first, *rest = l
if first >= n:
return [first]
else:
return [first] + sum_sub(n-first, rest)
Auf der Grundstruktur kannst du nun aufbauen - wenn du doch nur exakte Summen willst, ist das einfach zu machen indem du das zu große first ggf. weglässt. Und den Fehlerfall (Summe nicht erreichbar) kannst du auch noch einbauen.
Ja, aber vor allem sollst es du selbst schreiben, damit du etwas lernst. Oben habe ich dir eine einfache Grundstruktur gegeben - bei Rekursion braucht man manchmal etwas Zeit, um sich reinzudenken, das sollte damit helfen. Jetzt überleg dir wie du die exakte Summe erzwingen kannst.
Die Aufgabenstellung könnte noch schwieriger sein, indem etwa die kürzeste Liste verlangt wird, die die Summe ergibt...
Das heißt, es soll bspw. eine Liste
[ 1, 2, 3, 4 ]
geben und der Algorithmus generiert eine Liste, die mir bspw. für die Summe 6 eine Liste generiert, die sich aus den entsprechenen Summanden zusammensetzt, die aber auch in der ersten Liste gegeben sein müssen?
[ 1, 2, 3 ]
Ein leichter Lösungsansatz wäre im Grunde ein normaler Durchlauf durch die Liste. Wenn die gewünschte Summe oder das Ende der Liste erreicht wurde, muss die Rekursion abgebrochen werden.
Je Schritt prüfst du, ob die aktuelle Zahl in die derzeit geforderte Summe passt. Wenn ja, wird die Zahl der Liste zugefügt, und (falls die Summe dann noch nicht erreicht ist) die Differenz zur Summe an den nächsten rekursiven Aufruf weitergegeben. Wenn die aktuelle Zahl größer als die derzeit geforderte Summe ist, geht es einen Schritt weiter.
Fraglich wäre allerdings, wie spezielle Anwendungsfälle wie dieser gelöst werden sollten: Die Endsumme soll 5 betragen. Die Liste würde [ 1, 2 ] beinhalten, weitere Elemente könnten nicht hinzugefügt werden.
falls es nicht möglich sein sollte, soll die Funnktion den Rückgabewert None liefern aber danke schonmal!
Na das lässt sich dann doch noch ziemlich einfach ergänzen.
Bau dir zunächst den einfachen Durchlauf und lasse dir alle Elemente zur Prüfung auf der Konsole ausgeben. Erweitere dies danach um die Abfragen und die fehlende Logik zum Aufbau der Ergebnisliste.
Aber wenn meine rekursive Funktion sowohl den Rückgabewert None als auch List hat, wie kann ich dann zB beim Befehl
if l[i] <= s:
return sum_sub(l, i-1, s-l[i]) + [l[i]]
sicherstellen, dass meine Liste nicht mit None "addiert" wird?
Ich soll eine Liste zurückgeben, die exakt die Summe dieser Zahl bildet. Wenn das nicht möglich ist, None zurückgeben.