Rekursiv programmieren (integerbaum)

[d_rose]

Hallo zusammen, nein hier soll mir niemand die Lösung vors Gesicht klatschen, dazu bin ich selber zu stolz, ich will das selber hinkriegen.
Aber langsam bin ich am verzweifeln.
Falls mir jemand den geringsten Ansatz zu dieser Aufgabe nennen kann, dem wäre ich sehr dankbar.
Das größte Problem das sich mir stellt ist, wie ich es dem PC verklickere, die korrekten Zahlen mit der korrekten zu multiplizieren und das auch noch dann rekursiv.

Also zum 1. Beispiel würde die Rechnung folgendermaßen aussehen : 1 * 81 + 2 * (-16-7) + 3 * (111-26) = 290

Arrays oder ähnliches hatten wir bisher noch nicht in den Vorlesungen.

[__deets__]

fangen wir mit ein paar einfachen Fragen an: wie unterscheidest du, ob du einen Blatt- oder einen Teilbaumknoten vor dir hast?

[Sirius3]

@d_rose: Arrays braucht man in Python recht selten. Was Du meinst, sind wahrscheinlich Listen, aber hier hast Du Tuple. Ohne zu wissen, wie man mit Tupeln arbeitet, wirst Du die Aufgabe nicht lösen können.

Ansonsten fang an, aufzuschreiben, wie Du das auf dem Papier lösen würdest, Schritt für Schritt.

[Chr0medome]

@d_rose
Falls ihr in den Vorlesungen schon OOP behandelt habt, könntest du’s damit mal probieren.

Jedoch ist es wichtig (wie sirius3 und __deets__ bereits angedeutet haben) sich erstmal in irgendeiner Weise einen Überblick über die Problematik zu machen und schriftlich festzuhalten.

[d_rose]

fangen wir mit ein paar einfachen Fragen an: wie unterscheidest du, ob du einen Blatt- oder einen Teilbaumknoten vor dir hast?

das Problem ist an der Sache wir haben dazu nichts in en Vorlesungen besprochen.
wenn ihr mir nicht glaubt kann ich euch die Vorlesungen schicken, es steht wirklich nichts in den Folien drinne.
Ein Kollege der etwas weiter im Studium ist ist der Meinung das es sich nicht um richtige Binärbäume hält.
das einzige Muster das ich in der Sache erkenne ist, das das Element das zwischen 2 Elemente steht eine ebene höher liegt.
Zu tupeln weis ich das sie unveränderbar sind.

[Sirius3]

@d_rose: Jammern hilft im Studium nicht weiter. Denn im Job bekommt man auch Aufgaben, wo man erstmal nicht weiß, wie's geht. Ob das nun ein "richtiger" Binärbaum ist, oder nicht, spielt auch keine Rolle. Er ist in der Aufgabe nunmal so definiert (jeder Knoten hat genau zwei Nachfolger, ergo Binärbaum).
Daher nochmal die Frage, wie würdest Du das Problem mit Papier und Bleistift lösen, und wo hakt es dann in der Umsetzung nach Python?

[__deets__]

Der Kollege hat schonmal keine Ahnung. Das ist ein binärbaum. Das ihr keine Handreichung gehabt habt, wie man Tupel von anderen Typen unterscheidet (oder allgemein Typen) ist schwer Vorstellbar. Aber gut. Es gibt zwei Ansätze:

- schau dir mal isinstance an.
- zerleg einen Baum in seine Bestandteile mit Tupel unpacking.

links, mitte, rechts = baum

Wenn das ein Blatt-Knoten ist (also nur eine Zahl) geht das schief. Wie kann man das ausnutzen?

Last but not least: deine Erkenntnis ist richtig, aber zielführender ist es, genau anders herum zu denken: de Elemente links und rechts sind TIEFER als das eine in der Mitte.

Da du offensichtlich noch kämpfst damit, das überhaupt als Baum zu sehen: nimm dir die Beispiele & mal sie selbst auf. Dabei ergibt sich schon für dein eigenes Verhalten ein rekursives Vorgehen.

[d_rose]

@d_rose: Jammern hilft im Studium nicht weiter. Denn im Job bekommt man auch Aufgaben, wo man erstmal nicht weiß, wie's geht. Ob das nun ein "richtiger" Binärbaum ist, oder nicht, spielt auch keine Rolle. Er ist in der Aufgabe nunmal so definiert (jeder Knoten hat genau zwei Nachfolger, ergo Binärbaum).
Daher nochmal die Frage, wie würdest Du das Problem mit Papier und Bleistift lösen, und wo hakt es dann in der Umsetzung nach Python?

also vom job bin ich sehr sehr sehr sehr sehr weit entfernt. und jammern würde ich dazu auch nicht sagen, letztendlich frag ich nach Ansätzen.
Jammern ist für mich sich zu beklagen und keine Lösung zu suchen.
Es ist auch nicht so das ich direkt nachdem ich die aufgabe lese, mich hier an das Forum wende.
Ich hab meine stunden reingesteck bin leider null vorangekommen.
Das ist aber der Deadline egal deswegen wende ich mich hier an das Forum.
Ich weis ja nicht wie lange du dabei bist, für mich sind es 1 1/2 Monate bisher.
Für ein bisschen mehr Hineinversetzungsgefühl wäre ich sehr dankbar.

[snafu]

Jammern ist, wenn man ein Vielfaches der Zeilen dafür verwendet, wie schwer die Aufgabe doch sei, anstatt sich mit den fachlichen Nachfragen zu beschäftigen und zu sagen, wie weit man schon mit der Lösung gekommen ist - am besten mit Code. Hast du eigentlich verstanden, nach welchem Muster die Bäume beschrieben sind und welche Bedeutung die Klammern dabei haben? Und dann wäre die Frage, ob ihr als Eingabe einen String verarbeiten sollt oder ob das bereits als Tupel vorliegt. Sonst müsste man natürlich erstmal den String parsen, bevor man sinnvoll anfangen kann.

[Sirius3]

@d_rose: ich will Dir ja nicht absprechen, dass Du Dich intensiv mit dem Problem beschäftigst, Sätze, wie, "das haben wir aber nicht in der Vorlesung gehabt" habe ich aber schon viel zu oft gehört, und fast immer war es eine Ausrede.

Daher nochmal die Frage, wie würdest Du das Problem mit Papier und Bleistift lösen, und wo hakt es dann in der Umsetzung nach Python?

[d_rose]

@d_rose: ich will Dir ja nicht absprechen, dass Du Dich intensiv mit dem Problem beschäftigst, Sätze, wie, "das haben wir aber nicht in der Vorlesung gehabt" habe ich aber schon viel zu oft gehört, und fast immer war es eine Ausrede.

Daher nochmal die Frage, wie würdest Du das Problem mit Papier und Bleistift lösen, und wo hakt es dann in der Umsetzung nach Python?

also mit Stift und Papier folgendermaßen :
erstmal würde ich die zahl der Elemente innerhalb des tupels zählen, wobei ich eingebette Tutel selber als 1 Element zähle.
In dem Fall ((111,-16,-26),81,-7) wären es 3 Elemente also hat der Baum 3 Stufen.
Das einzige Muster das ich nun erkenne ist das die Elemente links und rechts eine stufe niedriger Stehen.
Alos gucke ich nachdem "Mittlersten" , wenn das überhaupt ein Ausdruck ist , Ausschau halten und mich von da aus orientieren.
Eins weiter Rechts ist die -7 platziert,also ist sie im Baum ein ebene tiefer und rechts von 81 aus platziert.
So nun befinden sich links 3 Werte in ein Element gepackt.
Das mittig positionierte Elemente darin ist die -16, also muss die links und eine ebene tiefer von 81 aus sein.
und zum Schluss folgen die die werte links und rechts um -16 welche dementsprechend eine ebene unter -16 links und rechts platziert werden.
Rechnerisch dann irgendwie so :
Mistigste Elemente * 1 + (Links+Rechts) * 2 und sowas weiter
ich hab versucht es mit den Index Positionen zu lösen aber komme nicht auf einen Anfang, denn mit den tatsächlichen Zahlenwerten hat der Baum ja so richtig nicht zu tun.
Ich würde ja Gerne einen Code reinschicken aber, wie gesagt mir fehlt irgendwie der Ansatz dazu.

[Sirius3]

Ehrlich gesagt verstehe ich Deine Erklärung nicht. Und das ist führt dann auch dazu, dass Du es schwierig Python erklären kannst.
Laut Definition hat jedes Tuple drei Elemente, nämlich den Linken Teilbaum, den Knoten-Wert und den rechten Teilbaum. Daraus abzuleiten, dass der Baum drei Stufen hat, ist falsch. Ob Deine Erklärung passt oder nicht, mußt Du auch am zweiten Beispiel testen.
Rekursion bedeutet, dass man das selbe Muster auf Teile anwendet. Hier also, mache was mit dem linken Teilbaum, mache was mit dem rechten Teilbaum, berechne das Ergebnis aus links, mitte, rechts.

[__deets__]

Du baust das ganze nicht rekursiv auf. Du versuchst stattdessen, da irgendwie durch eine Betrachtung des Ganzen weiter zu kommen. Das kann zum Ziel fuehren, soll es aber nicht - du sollst ja lernen, rekursive Strukturen zu verarbeiten und mental in die richtigen, rekursiven Funktionsaufrufe einzusortieren.

Und da sieht das ganze dann anders aus:

- gegeben ein baum, und eine tiefe n
- wenn der baum ein Blatt ist, dann liefere n * baum zurueck.
- sonst teile den baum in links, rechts, mitte auf, und liefere n * mitte + rekursion(links, n + 1) + rekursion(rechts, n + 1) zurueck.

Damit habe ich dir fast schon den Code geliefert.

[snafu]

Und wenn er es wirklich verstanden hat, dann erkennt er bestimmt auch den sicherlich absichtlich eingebauten Tippfehler beim Pseudocode.

[d_rose]

Ehrlich gesagt verstehe ich Deine Erklärung nicht. Und das ist führt dann auch dazu, dass Du es schwierig Python erklären kannst.
Laut Definition hat jedes Tuple drei Elemente, nämlich den Linken Teilbaum, den Knoten-Wert und den rechten Teilbaum. Daraus abzuleiten, dass der Baum drei Stufen hat, ist falsch. Ob Deine Erklärung passt oder nicht, mußt Du auch am zweiten Beispiel testen.
Rekursion bedeutet, dass man das selbe Muster auf Teile anwendet. Hier also, mache was mit dem linken Teilbaum, mache was mit dem rechten Teilbaum, berechne das Ergebnis aus links, mitte, rechts.

Tatsächlich geht meine Beobachtung auch im zweiten Beispiel auf denn es sind 5 Elemente im tupel ohne jetzt die Elemente die eingebettet sind zu beachten und der Baum dazu hat 5 Ebenen.

[__blackjack__]

@d_rose: Wo zählst Du da 5 Elemente? Kannst Du die bitte mal konkret auflisten und wie Du darauf kommst?

[d_rose]

@d_rose: Wo zählst Du da 5 Elemente? Kannst Du die bitte mal konkret auflisten und wie Du darauf kommst?

Sorry nehme es zurück. Hab mich verguckt:

[d_rose]

Du baust das ganze nicht rekursiv auf. Du versuchst stattdessen, da irgendwie durch eine Betrachtung des Ganzen weiter zu kommen. Das kann zum Ziel fuehren, soll es aber nicht - du sollst ja lernen, rekursive Strukturen zu verarbeiten und mental in die richtigen, rekursiven Funktionsaufrufe einzusortieren.

Und da sieht das ganze dann anders aus:

- gegeben ein baum, und eine tiefe n
- wenn der baum ein Blatt ist, dann liefere n * baum zurueck.
- sonst teile den baum in links, rechts, mitte auf, und liefere n * mitte + rekursion(links, n + 1) + rekursion(rechts, n + 1) zurueck.

Damit habe ich dir fast schon den Code geliefert.

Jetzt will ich nicht unverschämt rüberkommen , aber wie definiere ich die Bedingung , "wenn der baum ein Blatt ist".
Also was ist das Kriterium für ein Blatt.

[__deets__]

Habe ich dir schon in meinem zweiten oder so Post geschrieben, wie das gehen kann.

[d_rose]

Code: Alles auswählen

a = ((111,-16,-26),81,-7)

def summiere (baum,ebene):
    summe = 0
    y = 0
    x = 0
    z = 0
  
    if  isinstance(baum,int) == True  :
        summe = baum * ebene
    else   :
        x , y , z = baum
    return (y * ebene + summiere(x,ebene+1) + summiere(z,ebene+1))

print(summiere(a,1))

Bitte zerstört mich nicht haha
Jetzt haut der mir den Error raus : Maximum recursion depth exceeded while calling a python object