Rekursion Python

[Finux]

Hallo, 

 

etlche Infoquellen, Erklärungen, Skripte, Buchzeilen bin ich durchgegangen, und dennoch: Ich benötige Hilfe bei einer Aufgabe.

Bin angehender FiAe, arbeite aktuell ausschließlich mit Python und bin noch sehr unerfahren was Programmieren (insb. Algor. angeht), daher seht mir evtl. "Dummheiten" bitte nach. Ich schreibe ja hier um zu lernen wie ich es besser mache. Daher wären evtl. Bsp. am meisten für mich von Nutzen wenn ich sie erstmal in Python lesen kann.  Vielen Dank!

Vorab die Info: Rekursion ist eine sich selbst aufrufende Funktion. Das habe ich verstanden, und in dem folgenden Mini-Programm umgesetzt:

(Entwickle Algorithmus welcher rekursiv die Quersumme einer natürlichen Zahl berechnet)

def calc_checksum(n):
    n = sum([int(i) for i in str(n)])
    if n > 10:
        calc_checksum(n)
    else:
        print(n)

# --------------------------------------- Programmstart ------------------------------------------------------------ #
n = 123456789

calc_checksum(n)

 

Nun sitze ich an folgender Aufgabe, die mein Verständnis für rekursive Programmierung absolut zu übersteigen scheint:
(Gegeben ist eine Folge von ganzen Zahlen in einem Array. Gesucht ist die maximale Summe aller Elemente in einer Teilfolge aufeinanderfolgender Zahlen.

Die Eingangsfolge 12, -34, 56, -5, -6, 78 liefert bspw. die höchste Teilfolgensumme von 123 in der Teilfolge 56-5-6+78)

Gegeben: vollständige Liste L [12, -34, 56, -5, -6, 78]  <-- eine Teilfolge besteht nicht aus allen Elementen der vollständigen Liste!

Es gibt insgesamt 14 Kombinationsmöglichkeiten, wie sich Teilfolgen zusammensetzen können. Hier die möglichen Kombinationen:

 

23     =     [12, -34, 56, -5, -6]

29     =     [12, -34, 56, -5]

34     =     [12, -34, 56]

-22    =     [12, -34]

 

89     =     [-34, 56, -5, -6, 78]

11     =     [-34, 56, -5, -6]

17     =     [-34, 56, -5]

22     =     [-34, 56]

 

123   =     [56, -5, -6, 78]

45     =     [56, -5, -6]

51     =     [56, -5]

 

67     =     [-5, -6, 78]

-11    =     [-5, -6]

 

72     =     [-6, 78]

 

Ich möchte diese Aufgabe lösen, stoße dabei aber auf unterschiedliche Probleme:
1. Ich verstehe trotz Debuggen den Ablauf der Rekursion (Funktionsaufrufe) nicht.

2. Dadurch ist mir nicht klar, was ich tun muss um alle 14 Möglichkeiten durchlaufen zu lassen

3. Jede durchlaufene Möglichkeit möchte ich in einem Dictionary speichern. Innerhalb der Funktion "addition" überschreibt es sich logischerweise immer wieder selbst. Das Dict. global zu machen hilft mir leider auch nicht. Zumindest funktioniert es nicht. 

4. Theoretsich möchte ich ausschließlich Teilfolgen berechnen lassen. Dazu müsste ich die Funktion "addition" allerdings von außen mehr als 1 Mal aufrufen...

 Mein bisheriger Programmcode zu dieser Aufgabe sieht aktuell so aus:

Zitat

#final_dict = {}
global final_dict   """da in der Funktion addition sonst überschrieben wird, dachte ich global würde helfen..."""
# --------------------------------------- Funktion ----------------------------------------------------------------- #

def save_result(res_dict):
    final_dict.update(res_dict)

def addition(calc_elements, i):
    res_dict = {}   """resolution_dict für eine Teilfolge als Value, und dessen Gesamtsumme als Key"""
    h = 0           """h als Hilfsvariable"""
    # calc_elements = calc_elements[0:-1]
    i += 1
    if len(calc_elements) > 1:
        # print(calc_elements)
        for element in calc_elements:
            h += element
        # print(h)
        res_dict.update({h: calc_elements})
        # save_result(res_dict)
        print(res_dict, i)
        addition(calc_elements[:-1], i) """Funktion ohne letzten bekannten Listenwert zur Übergabe"""
        addition(calc_elements[1:], i)  """Funktion ohne ersten bekannten Listenwert zur Übergabe"""

    else:
        print("rdy", i)




# --------------------------------------- Programmstart ------------------------------------------------------------ #

num_list = [12, -34, 56, -5, -6, 78]

i = 0                  """soll mir Aufschluss darüber geben wo ich mich im Programmcode befinde (z.B. Durchgang Nr.i)"""
addition(num_list, i)
#print(final_dict)

 

Besten Dank schon mal an alle die sich freundlicherweise mit diesem komplizierten Problem beschäftigen!!
LG, 

Fin

[Finux]

Hallo, 

bin gerade dann letztlich doch selbst auf eine Lösung gekommen, aber wer schon dabei geschaut und eine schöne Lösung gefunden hat- ich bin neugierig- postet sie mir bitte hier rein! 

Meine finale Lösung:

# --------------------------------------- Höchste Summer einer Teilfolge von Liste mit Integer --------------------- #
"""
Aufgabe 4:  b) Gegeben sei eine Folge von n ganzen Zahlen in einem Array. Gesucht ist die maximale Summe aller
            Elemente in einer Teilfolge aufeinanderfolgender Zahlen.
            Die Eingangsfolge 12 -34 56 -5 -6 78 liefert bspw. die Summe 56 -5 -6 +78 = 123.
"""


# --------------------------------------- Funktion ----------------------------------------------------------------- #

def save_to_dict(k, v):
    dict_of_num[k] = v

def sum_list(num_list):

    pieces_add1 = num_list[:-1]
    pieces_add2 = num_list[1:]

    if len(num_list) > 2:
        if pieces_add1 not in dict_of_num.values():
            add1 = sum(num_list[:-1])
            print(add1, pieces_add1, "wurde berechnet!")
            save_to_dict(add1, pieces_add1)
            sum_list(num_list[:-1])

        if pieces_add2 not in dict_of_num.values():
            add2 = sum(num_list[1:])
            print(add2, pieces_add2, "wurde berechnet!")
            save_to_dict(add2, pieces_add2)
            sum_list(num_list[1:])
        else:
            print("Alrdy in dict!", pieces_add1, pieces_add2)
    else:
        print("rdy")



# --------------------------------------- Programmstart ------------------------------------------------------------ #

dict_of_num = {}

num_list = [12, -34, 56, -5, -6, 78]
#num_list = [4, 4, 4, 12]               # Testliste für Trigger doppelter Berechnung!

sum_list(num_list)
for result in dict_of_num.keys():
    print("DICT", result)









#ToDo: Vermeide redundante Berechnungen! (Unterschiedliche Teilfolgen mit gleichem Ergebnis müssen zugelassen sein!) // Kein return, Kein string