1. Schreiben Sie eine Funktion (pascals_triangle), die für gegebenes n eine Liste b von Listen zunehmender
Länge zur Repräsentation des Pascalschen Dreiecks zurückgibt. Für n ∈ N0 gilt b[n][0] =
b[n][n] = 1 und für k ∈ N, 0 < k < n gilt b[n][k] = b[n−1][k−1]+b[n−1][k]. Die
Liste besteht also am Ende aus Listen, die die Zeilen des Dreiecks von oben nach unten
darstellen.
2. Erzeugen Sie nun eine eindimensionale (unverschachtelte) Liste zur sukzessiven Speicherung der ersten n Zeilen des Pascalschen Dreiecks. Welche Länge muss die Liste besitzen? Implementieren Sie hierzu die Funktion pascals_triangle_flat, die die geforderte Liste zurückgibt und erläutern Sie Ihre Überlegungen bezüglich der Länge der Liste.
Hinweis: Im Falle der Beispielliste b von oben ergäbe sich:
c = [1,1,1,1,2,1,1,3,3,1,1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1]
3. Siehe Aufgabenblatt
Comment prefix | # |
---|---|
Given input | 0 5 7 9 |
Expected output | # exercise 1 [[1]] [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]] [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 15, 6, 1], [1, 7, 21, 35, 35, 21, 7, 1]] [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 15, 6, 1], [1, 7, 21, 35, 35, 21, 7, 1], [1, 8, 28, 56, 70, 56, 28, 8, 1], [1, 9, 36, 84, 126, 126, 84, 36, 9, 1]] # exercise 2 [1] [1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1] [1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1, 1, 6, 15, 20, 15, 6, 1, 1, 7, 21, 35, 35, 21, 7, 1] [1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1, 1, 6, 15, 20, 15, 6, 1, 1, 7, 21, 35, 35, 21, 7, 1, 1, 8, 28, 56, 70, 56, 28, 8, 1, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1] |