Übung Problem: Rekursion Pascalsches Dreieck

Code-Stücke können hier veröffentlicht werden.
Antworten
Reibend
User
Beiträge: 2
Registriert: Mittwoch 19. September 2018, 19:42

Mittwoch 19. September 2018, 21:16

Guten Abend liebe Gemeinde,

zurzeit arbeite ich mich seit ein paar Wochen in Python rein (habe zumindest etwas Erfahrung in Java und VB) und gehe einige klassische Übungsaufgaben durch. Zurzeit knabber ich einem Problem, bei dem ich das Gefühl, eher Tomaten auf den Augen zu haben und mich festgebissen zu haben. Ihr kennt das sicherlich, ihr wollt etwas lösen, habt das Gefühl, ihr müsste nur eine Kleinigkeit ändern oder umdenken, was aber aufgrund des Gedankenkäfigs nicht gelingen will.

Nun gut, es geht um das pascalsche Dreieck - Klassiker der Mathematik. Die Aufgabe besteht darin, eine rekursive Funktion mit einer beliebigen Anzahl an Zeilen, die vom Eingabeparameter abhängt. So weit, so gut. Jedoch wollte mir rekursiv (iterativ ist nicht das Problem) kein wirkliches Dreieck gelingen. Beim Blick in die Musterlösungen des Autors kam eher Ernüchterung:

Code: Alles auswählen

def pascal(n):
    if n == 1:
        return [1]
    else:
        line = [1]
        previous_line = pascal(n-1)
        for i in range(len(previous_line)-1):
            line.append(previous_line[i] + previous_line[i+1])
        line += [1]
    return line

print(pascal(6))
Und ich sitze da und denke und denke und grübel, wie ich das verdammte Dreieck hinbekomme. Die Lösung wird angesehen und ich sehe..."Das ist ja gar kein Dreieck!" Obwohl in der Aufgabe nur geschrieben wird, dass das Dreieck erzeugt werden sollte - und keine einfache Zeile.

Und da kam der innere Hund durch - der Wille, mich da durchzubeißen. Erster Entwurf:

Code: Alles auswählen

def pascal(n):

    if n == 1:
        print("[1]")
        return [1]

    else:
            line = [1]
            previous_line = pascal(n-1)
            for i in range(len(previous_line)-1):
                line.append(previous_line[i] + previous_line[i+1])
            line += [1]
            
            print(line)
            return line

input=int(input("Wie viele Zeilen? "))
pascal(input)
Ok, die Berechnungen habe ich, aber wie ein Dreieck sieht das immer noch nicht aus. Dadurch, dass die Funktion rekursiv aufgesetzt wird, kann ich "n" nun schlecht als Zähler benutzen und anhand dessen die Spaces vor den Zeilen hochzählen. Also habe ich provisorisch (womöglich furchtbarer Stil) einen zweiten Parameter eingebaut und anhand dessen die Spaces gesetzt:

Code: Alles auswählen

def pascal(n,m=0):

    out = ""
    for c in range(m):
        out += " "

    if n == 1:
        print(out+"[1]")
        return [1]

    else:
            line = [1]
            previous_line = pascal(n-1,m+1)
            for i in range(len(previous_line)-1):
                line.append(previous_line[i] + previous_line[i+1])
            line += [1]

            line=eval(str(line))
            print(out+str(line))
            return line

input=int(input("Wie viele Zeilen? "))
pascal(input)
Nun...irgendwie funktioniert es, aber wie ihr sehen könnt, ergibt das ab einer gewissen Anzahl an Zeilen eher eine 2D-Sturmfront als ein Dreieck, was schlicht daran liegt, dass der Zähler "m" linear hochgezählt wird, während die Zeilen überproportional breiter werden.

Und genau hier habe ich mich verrannt und würde mich über jeglichen Input freuen. Wie wäre rekursiv hier ein Dreieck zu lösen, das auch entsprechend wie ein Dreieck aussieht?

Freue mich auf die Rückmeldungen! Vielen Dank schon mal!
Sirius3
User
Beiträge: 11982
Registriert: Sonntag 21. Oktober 2012, 17:20

Mittwoch 19. September 2018, 21:53

Du müßtest ja wissen, wie die letzte Zeile aussieht, um zu wissen, wie viele Stellen dort die Zahlen haben.

Zum Code: `eval` hat in einem normalen Programm nichts zu suchen. Es ist ja auch unsinnig aus einer Liste deren Stringrepresentation zu bauen, um sie dann wieder mit eval in eine identische Liste parsen zu lassen.

Man könnte die Breite vorgeben:

Code: Alles auswählen

def pascal(n, m=0):
    line = [1]
    if n > 1:
        previous_line = pascal(n-1, m)
        line.extend(a + b
            for a, b in zip(previous_line, previous_line[1:])
        )
        line += [1]
    print("{!r:^{}s}".format(line, m))
    return line

pascal(10, 40)
Reibend
User
Beiträge: 2
Registriert: Mittwoch 19. September 2018, 19:42

Mittwoch 19. September 2018, 22:31

Völlig richtig erkannt, und vielen herzlichen Dank für die schnelle Hilfe, weiß ich sehr zu schätzen. Das hilft ungemein weiter.

Wünsche noch einen angenehmen Abend soweit!
Antworten