Rekursive Funktion

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Chrisseeey
User
Beiträge: 7
Registriert: Donnerstag 9. Juni 2022, 15:02

Hallo ihr Lieben!

Ich bräuchte ein wenig Verständnishilfe bei einer Aufgabe von mir in der Uni für Python.

Ich erwarte hier keine fertige Lösung, dass ist mir durchaus bewusst, dass das Forum dafür nicht da ist, ich hätte gerne einfach ein wenig Hilfe dabei, die Klausur muss ich ja auch alleine schreiben ;). Ich habe immernoch große Probleme bei Python direkt bei einem Problem auf den richtigen Lösungsweg zu kommen, und vllt kann der ein oder andere mir ja helfen, dass besser zu verstehen :)

Also es geht bei der Aufgabe um Rekursion. Die Aufgabenstellung sieht wie folgt aus:

Im String 𝑐 sei eine einfache Rechnung abgespeichert, die nur Addition (+), Multiplikation (*) und die Zahlen (1,2,3,4,5,6,7,8,9) enthält. Sie dürfen davon ausgehen, dass der String keine Leerzeichen enthält.

Beispiel:
c = "3+4*5+6+1*3"

Schreiben Sie eine Funktion calc(string), welche rekursiv das Ergebnis dieser Rechnung bestimmt und als Integer zurückgibt. Achten Sie dabei auf Punkt-vor-Strich-Rechnung!

Als vorgegebenen Code haben wir das:

Code: Alles auswählen

c = "3+4*5+6+1*3"
print(c)
print()

# Beispiele für split():

sub1, sub2 = c.split("+", 1)
print("Ergebnis mit '+':")
print("sub1=" + sub1)
print("sub2=" + sub2)
print()

sub1, sub2 = c.split("*", 1)
print("Ergebnis mit '*':")
print("sub1=" + sub1)
print("sub2=" + sub2)
print()

# Beispielende
Also: Ich brauche die Funktion def calc(string):

Mein Rekursionsende ist, wie ich verstanden habe, erreicht, wenn die Länge des Strings 1 beträgt, macht ja auch Sinn, dann ist ja alles fertig gerechnet.

Mir ist auch bewusst, dass ich zu irgendeinem Zeitpunkt die strings in integer umwandeln muss. Und das Beispiel im code mit den split würde für mich auch sinn machen. Da hab ich mir gedacht, ich würde solange die strings spliten, bis jeweils alle nurnoch aus einem string bestehen, und alle dann zusammen addieren.
Ich bin auf jedenfall schwer verwirrt und bräuchte dringend eine hilfestellung, damit ich versteh, was zu zun ist.

Wäre wirklich über jede Hilfe dankbar!

Liebe Grüße

Chrissi
Benutzeravatar
pillmuncher
User
Beiträge: 1482
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

@Chrisseeey: Du must beachten, dass Punkt (d.h. Stern) vor Strich gilt. Die rekursive Struktur der Formel 3+4*5+6+1*3 ist dann (rechtsassoziativ) +(3, +(*(4, 5), +(6, *(1, 3)))). Das muss dein Programm irgendwie abbilden, entweder durch eine rekursiv definierte Datenstruktur oder eine rekursive Funktion oder beides.

Tipp: Nimm die linke Zahl und wenn der Operator danach ein + ist, addiere die Zahl zum Ergebnis der Funktion der restlichen Zeichen. Ist es ein *, hol dir die nächste Zahl, berechne das produkt dieser zwei Zahlen und rufe die Funktion mit dem Ergebnis als erster Zahl wieder auf. Also ungefähr so:

Code: Alles auswählen

3, +, rest     ->  3 + f(rest)
4, *, 5, rest  ->  f((4 * 5) & rest)
9, +, rest     ->  9 + f(rest)
6, +, rest     ->  6 + f(rest)
1, *, 3, ∅     ->  1 * 3
In specifications, Murphy's Law supersedes Ohm's.
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@Chrisseeey: Rekursiv Probleme lösen heisst, das Ausgangsproblem in kleinere gleichartige Probleme aufzuteilen. Schau Dir doch mal die Ergebnisse zu den Hinweisen an, was da jeweils heraus kommt. Siehst Du da etwas das nach einem Teilproblem aussieht welches man mit `calc()` lösen kann, wenn es die Funktion schon gäbe?

Da wir laut Aufgabenstellung davon ausgehen können, dass nur sinnvolle Eingaben verarbeitet werden müssen, überleg Dir doch mal die kleinste Eingabe für die das funktionieren muss. Also wenn das Problem so klein ist, dass es direkt den Rekursionsanker betrifft.

Und dann erweitere das Problem um einen Schritt bei dem die Lösung nicht beim ersten, aber bereits beim ersten rekursiven Aufruf auf den Rekursionsanker trifft.

Dann musst Du Dir noch überlegen in welcher Reihenfolge man aufteilen muss, damit Punkt vor Strich gilt, und das war es eigentlich schon.

Den Rekursionsanker kann man übrigens von der Bedingung her auch anders formulieren, dann wären ganz trivial auch Leerzeichen und mehrstellige ganze Zahlen möglich.

Und ich persönlich würde statt `split(…, 1)` hier eher `partition()` verwenden, weil das garantiert immer drei Elemente liefert. Damit lässt sich das Ergebnis auch garantiert an drei sinnvolle Namen zuweisen, egal ob die das jeweilige Rechenzeichen enthalten ist oder nicht.

@pillmuncher: Ich glaube Du denkst schon zu kompliziert, denn bei Deinem Ansatz macht der Code für den Lösungsansatz mit dem `split()` keinen Sinn. Denn wenn man da einfach von links die Operatoren abtrennt, kennt man ja die festen Indizes vom linken Operanden (0) und dem Operator (1) und dem Rest (2…) und braucht kein `split()`. Ist natürlich die sinnvollere Variante, weil man die Zeichenkette letztlich überhaupt gar nicht zerlegen muss, da man einfach den aktuellen Index als Parameter mit in die rekursiven Aufrufe reichen kann.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
pillmuncher
User
Beiträge: 1482
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

@__blackjack__: In der Aufgabe steht nichts von split(). Das hat erst der OP ins Spiel gebracht.
In specifications, Murphy's Law supersedes Ohm's.
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@pillmuncher: Zitat vor dem Code „Als vorgegebenen Code haben wir das:“. Und da dort auch ein Beispiel für `c` drin ist, dachte ich das gehört zur Aufgabenstellung.

@Chrisseeey: Gehört der Code zur Aufgabenstellung als Lösungshinweis, oder ist das allgemein aus der Vorlesung?
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
dirk009
User
Beiträge: 27
Registriert: Donnerstag 3. Juni 2021, 21:49

Hallo @Chrisseeey,

hier der umgekehrte Weg - versuch mal zu verstehen, warum der Code funktioniert:

Code: Alles auswählen

def calculate(term):
    print(term)

    if '*' in term:
        index = term.index('*')
        wert = int(term[index-1]) * int(term[index+1])
        return calculate(term[:index-1] + str(wert) + term[index+2:])
    
    if '+' in term:
        position = term.index('+')
        return int(term[:position]) + calculate(term[position+1:])

    return int(term)

if __name__ == '__main__':
    
    term = "3+4*5+6+1*3"
    print(F"{term} ergibt: {calculate(term)}")
 
Ausgabe:
    
3+4*5+6+1*3
3+20+6+1*3
3+20+6+3
20+6+3
6+3
3
3+4*5+6+1*3 ergibt: 32
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@dirk009: Quasi der Mittelweg bei dem beide Operationen unterschiedlich behandelt werden. Bei "+" ist der `index()`-Aufruf überflüssig, die `position` ist da immer 1 bei den gegebenen Randbedingungen. Ich mag diesen ganzen Indexkram und an so vielen Stellen `int()` und an einer sogar wieder zurück nach `str()` nicht wirklich. Das ist alles umständlicher als es sein muss IMHO.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

__blackjack__ hat geschrieben: Mittwoch 22. Juni 2022, 17:09 Bei "+" ist der `index()`-Aufruf überflüssig, die `position` ist da immer 1 bei den gegebenen Randbedingungen.
Nicht ganz, bei calculate("2*5+3") ist das z.B. nicht so.

Trotzdem ist die Funktion falsch, calculate("2*5*3") gibt 10 aus ...
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@bords0: Doch, der einzige Teilausdruck der bis zu der Stelle kommt ist "5+3". Wenn ein "*" drin vorkommt, wird das im ``if`` davor abgefrühstückt, das heisst wenn ein "+" drin ist, dann ist garantiert an Index 1 ein "+" das auch von `index()` als erstes gefunden wird.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
pillmuncher
User
Beiträge: 1482
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

Wenn das Ganze mit split() gelöst werden soll, dann muss man halt solange mit + splitten, nbis es nicht mehr geht, und dann die einzelnen Ergebnisse solange mit * splitten, bis es nicht mehr geht, und dann einfach alles ausrechnen. Wieder mit der Formel 3+4*5+6+1*3

Code: Alles auswählen

split('3+4*5+6+1*3')  -> '3', '4*5+6+1*3'; return f('3') + f('4*5+6+1*3')
split('4*5+6+1*3')  -> '4*5', '6+1*3'; return  f('4*5') + f('6+1*3')
split('6+1*3')  -> '6', '1*3'; return  f('6') + f('1*3')
Mit der Multiplikation muss man entsprechend verfahren. Die Zahlenstrings müssen noch in Zahlen umgewandelt werden.
In specifications, Murphy's Law supersedes Ohm's.
Chrisseeey
User
Beiträge: 7
Registriert: Donnerstag 9. Juni 2022, 15:02

erst einmal danke an alle für eure Hilfe! Ich versuch das alles noch ein wenig zu entziffern und zu verstehen, aber es geht zumindest in die richtige Richtung :D

@__blackjack__ der Code den wir bekommen haben sollte als Beispiel für split dienen.

Wir haben vom Dozenten noch weitere Hinweise bekommen:

-Das Rekusionsende ist erreicht, wenn die Länge des Strings Eins beträgt (dann ist die Ziffer selbst das Ergebnis der Rechnung).
-Mit int(ziffer)kann man einen String, der nur aus einer Ziffer besteht, in einen Integer konvertieren.
-Teilen Sie den String mithilfe von sub1, sub2 = string.split(zeichen, 1) auf (𝑧𝑒𝑖𝑐ℎ𝑒𝑛 ist dabei entweder "+" oder "*"). Das resultiert z.B. für string = "2+3*4" und zeichen = "+" in sub1 = "2" und sub2 = "3*4"). Die 1 im Argument ist dabei wichtig (siehe Beispiel in der folgenden Zelle)!
-Überlegen Sie genau, ob Sie den String zuerst in einzelne Summanden ("+") oder in einzelne Faktoren ("*") aufteilen müssen!

also zuerst solange spliten, bis es nicht mehr geht? und dann die strings in int konvertieren?

Wirklich nochmals vielen dank an alle!
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

__blackjack__ hat geschrieben: Mittwoch 22. Juni 2022, 18:28 @bords0: Doch, der einzige Teilausdruck der bis zu der Stelle kommt ist "5+3". Wenn ein "*" drin vorkommt, wird das im ``if`` davor abgefrühstückt, das heisst wenn ein "+" drin ist, dann ist garantiert an Index 1 ein "+" das auch von `index()` als erstes gefunden wird.
Nein. Hast du es mal laufen lassen? Bei den Termen, die ausgegeben werden, ist gar kein "5+3" dabei. Und beim Term "10+3" hat das (erste und einzige) "+" nicht den Index 1.

Code: Alles auswählen

In [2]: calculate("2*5+3")
2*5+3
10+3
3
Out[2]: 13
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@bords0: Dann habe ich jetzt noch einen Kritikpunkt an der Funktion: die ist zu unübersichtlich. :-)
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
dirk009
User
Beiträge: 27
Registriert: Donnerstag 3. Juni 2021, 21:49

bords0 hat geschrieben: Mittwoch 22. Juni 2022, 18:03 ...
Trotzdem ist die Funktion falsch, calculate("2*5*3") gibt 10 aus ...
Der Fehler war für den OP zum Finden gedacht :wink:
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

Um noch ein bisschen konstruktiv zu sein, noch ein kleiner Hinweis.
Die Funktion ist recht einfach zu schreiben. Man muss "einfach nur" abarbeiten, was alles an Aufgaben zu tun ist:

1. Funktionskopf (1 Zeile)
2. Rekursionsende erkennen und behandeln (2 Zeilen)
3. "Plus" erkennen und (mit Rekursion) behandeln (3-4 Zeilen)
4. "Mal" (mit Rekursion) behandeln (2 Zeilen)

Alles in allem 8-9 Zeilen. (Natürlich kann man auch ausführlich und länger schreiben, aber einen besonderen Sinn sehe ich darin nicht.)

Wenn du Schwierigkeiten hast, mach erst mal 1. und 2.

Danach dann 3., wenn es da Schwierigkeiten gibt, kannst du deinen Code posten.
Das ist m.E. die Stelle, an der es "Klick" machen muss, wenn man Rekursion verstehen will.

4. Sollte dann einfach sein.
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Eine Umsetzung in der ersten Programmiersprache mit der ich Kontakt hatte, die rekursive Aufrufe kannte. COMAL auf dem C64 so gegen Ende der 80er:

Code: Alles auswählen

0010 // Rekursive Auswertung eines Ausdrucks mit '+' und '*' unter
0020 // unter Beruecksichtigung von Punkt-vor-Strich.
0030 
0040 tests
0050 END 
0060 
0070 FUNC eval(REF expr$) CLOSED
0080   i#:=LEN(expr$)-1
0090   DIM left$ OF i#, right$ OF i#, op$ OF 1
0100   op$:="+"; i#:=op$ IN expr$
0110   IF NOT i# THEN op$:="*"; i#:=op$ IN expr$
0120   IF i# THEN
0130     left$:=expr$(:i#-1); right$:=expr$(i#+1:)
0140     a:=eval(left$); b:=eval(right$)
0150     CASE op$ OF
0160     WHEN "+"
0170       RETURN a+b
0180     WHEN "*"
0190       RETURN a*b
0200     ENDCASE 
0210   ELSE 
0220     RETURN VAL(expr$)
0230   ENDIF 
0240 ENDFUNC eval
0250 
0260 PROC tests CLOSED
0270   IMPORT eval
0280   WHILE NOT EOD DO
0290     READ expr$,expected
0300     result:=eval(expr$)
0310     PRINT expr$;"=";result;
0320     IF result=expected THEN
0330       PRINT "Ok"
0340     ELSE 
0350       PRINT "<>";expected
0360     ENDIF 
0370   ENDWHILE 
0380   
0390   DATA "1",1,"2+3",5,"3*4",12,"3+4*5+6+1*3",32,"4711+42*23",5677
0400 ENDPROC tests
Testlauf:

Code: Alles auswählen

run
1 = 1 Ok
2+3 = 5 Ok
3*4 = 12 Ok
3+4*5+6+1*3 = 32 Ok
4711+42*23 = 5677 Ok

end at 0050
Die zweite Sprache war dann etwas später Turbo Pascal auf dem PC.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
pillmuncher
User
Beiträge: 1482
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

Hier in SWI-Prolog:

Code: Alles auswählen

[library(dcg/basics)].

digit(N) --> [D], { code_type(D, digit), number_chars(N, [D]) }.

expr(R) --> term(N), addterm(M), {R is N + M}.
addterm(0) --> [].
addterm(R) --> [+], expr(R).
term(R) --> digit(N), multfactor(M), {R is N * M}.
multfactor(1) --> [].
multfactor(R) --> [*], term(R).

calc(Term, Result) :-
    string_chars(Term, Chars),
    phrase(expr(Result), Chars), !.
In specifications, Murphy's Law supersedes Ohm's.
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Bei folgender Lösung stellt sich die Frage ob eine Unterroutine die sich mit GOSUB selbst aufruft, aber die Verwaltung der ”lokalen Variable” manuell mit einem Array passiert, tatsächlich als rekursive Funktion durchgeht. Wahrscheinlich nicht, aber zumindest löst es die Rechenaufgaben in CBM BASIC. 🤓

Code: Alles auswählen

   10 SP=-1:DIM S(50):REM THE STACK
   50 REM TESTS
   60 READ E$,E:IF E$="" THEN END
   70 GOSUB 100:PRINT E$;" =";N;
   80 IF N=E THEN PRINT " OK":GOTO 50
   90 PRINT " <>";E:GOTO 50
  100 REM EVALUATE
  110 I=1
  120 GOSUB 500:SP=SP+1:S(SP)=N
  130 IF I>=LEN(E$) THEN N=S(SP):SP=SP-1:RETURN
  140 OP$=MID$(E$,I,1):I=I+1
  150 IF OP$<>"+" THEN 170
  160 GOSUB 120:S(SP)=S(SP)+N:GOTO 130
  170 IF OP$<>"*" THEN PRINT "EXPECTED OPERATOR":END
  180 GOSUB 500:S(SP)=S(SP)*N:GOTO 130
  500 REM GET NUMBER
  510 IF I>LEN(E$) THEN PRINT "UNEXPECTED END":END
  520 N=ASC(MID$(E$,I,1))-ASC("0"):IF N<1 OR N>9 THEN PRINT "EXPECTED DIGIT":END
  530 I=I+1:RETURN
10000 DATA "1",1,"2+3",5,"3*4",12,"3+4*5+6+1*3",32,,0
Das Programm setzt den Ansatz von Pillmuncher um sich nacheinander die Operationen der Reihe nach anzuschauen und falls nötig die Addition über den Stack zurück zu stellen, bis die Multiplikationen durchgeführt sind.

Der Ansatz der in der Aufgabe vorgeschlagen wird, ist Speicher- und Laufzeittechnisch auch ziemlicher Wahnsinn, was einem auf so kleinen, langsamen Plattformen mit wenig Speicher natürlich schneller auffällt und auch zum Problem wird, wenn man solche Sachen mit quadratischem Speicher- und damit auch Laufzeitbedarf implementiert. Bei Rechnern mit Gigahertz und Gigabytes fällt es natürlich nicht auf.

Wobei man auch den Ansatz mit aufteilen der Zeichenkette mit linearem Speicherverbrauch hinbekommen würde, wenn man nicht tatsächlich die Zeichenkette aufteilt/kopiert, sondern nur einen ”view” in die Zeichenkette verwendet, der konstanten Speicher braucht.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Qubit
User
Beiträge: 128
Registriert: Dienstag 7. Oktober 2008, 09:07

Schöne kleine Übungsaufgabe.
Mein Vorschlag:

Code: Alles auswählen

def calc(parse_string):
  result = 0

  if len(parse_string) > 1:

    if "*" in parse_string:
      mul1, mul2 = parse_string.split("*", 1)
      result = calc(mul1) * calc(mul2)

    if "+" in parse_string:
      add1, add2 = parse_string.split("+", 1)
      result = calc(add1) + calc(add2)

  else:
    result = int(parse_string)
  return result

if __name__ == '__main__':

  TERM = '3+4*5+6+1*3'
  print(f"{TERM} = { calc(TERM) }")
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

Eingerückt wird immer mit 4 Leerzeichen pro Ebene, zwei sind zu wenig.
Das result = 0 am Anfang wird nie benutzt, kann also weg.
Es ist sehr undurchsichtig, dass erst der Term an * gesplittet wird, und daraus ein Ergebnis berechnet wird, dann aber, falls doch noch ein + im Term ist, dieses (falsche) Ergebnis verworfen wird und das richtige berechnet wird.
Warum nennst Du unten den Term zwar `TERM`, in der Funktion das Argument dann `parse_string`?
Antworten