Pascal's Triangle

Q: Wie hoch ist die Zeitkomplexität beim Erzeugen des Pascalschen Dreiecks?

O(n²) für n Zeilen: Das Dreieck hat etwa n²/2 Einträge, und jeder Eintrag erfordert eine Addition. Das ist optimal, da du jeden Eintrag der Ausgabe schreiben musst. Der zusätzliche Speicherplatz über die Ausgabe hinaus beträgt O(1) .

Q: Wie hängt das Pascalsche Dreieck mit Binomialkoeffizienten zusammen?

Der Eintrag k der Zeile r , von 0 an gezählt, ist C(r, k) , die Anzahl der Möglichkeiten, k Elemente aus r auszuwählen. Die Summenregel ist die Identität C(r, k) = C(r-1, k-1) + C(r-1, k) , und die Summe der Zeile r ergibt 2^r , die Anzahl der Teilmengen von r Elementen.

Q: Kannst du eine Zeile berechnen, ohne die Zeilen darüber aufzubauen?

Ja. Beginne mit 1 und ermittle jeden nächsten Eintrag aus dem vorherigen: C(r, k) = C(r, k-1) × (r-k+1) / k . Multipliziere vor dem Teilen, damit die Division ohne Rest aufgeht, und verwende für das Produkt eine 64-Bit-Ganzzahl. Zeile r benötigt dann O(r) Zeit.

LeichtDynamische Programmierung

+10

Im Pascalschen Dreieck ist die erste Zeile [1]. Jede spätere Zeile hat einen Eintrag mehr, beginnt und endet mit 1, und jeder Eintrag dazwischen ist die Summe der beiden Einträge direkt darüber. Du erhältst eine Ganzzahl numRows. Gib die ersten numRows Zeilen des Dreiecks zurück, beginnend mit der obersten Zeile, wobei jede Zeile ein Array aus Ganzzahlen ist.

Funktion

generate(numRows: integer) → integer-2d-array

numRowsinteger: wie viele Zeilen des Dreiecks erstellt werden sollen
Gibt zurückinteger-2d-array: die ersten numRows Zeilen, oberste Zeile zuerst

Einschränkungen

1 ≤ numRows ≤ 30
Jeder Eintrag der ersten 30 Zeilen passt in eine vorzeichenbehaftete 32-Bit-Ganzzahl. Der größte ist 77558760 und befindet sich in der Mitte von Zeile 30.

Beispiele

Eingabe: numRows = 5
Ausgabe: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Erklärung: Jeder innere Eintrag addiert die beiden Einträge darüber. Zeile vier: 3 = 1 + 2 und 3 = 2 + 1. Zeile fünf: 4 = 1 + 3, 6 = 3 + 3, 4 = 3 + 1.

Eingabe: numRows = 1
Ausgabe: [[1]]
Erklärung: Mit einer Zeile besteht das Dreieck nur aus seiner Spitze, [1].

Weiterführende Frage

Kannst du nur ein Array behalten und es Zeile für Zeile an Ort und Stelle aktualisieren? In welche Richtung muss die innere Schleife laufen und warum?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Ein Eintrag ist die Summe zweier Einträge in der darüberliegenden Zeile. Wenn du diese Regel für jeden Eintrag von Grund auf neu auswertest, berechnest du dieselben Werte erneut, und der Aufwand verdoppelt sich mit jeder Zeile. Die Zeilen, die du zurückgibst, sind die gespeicherten Antworten auf diese kleineren Probleme. Baue das Dreieck also von oben nach unten auf, jede Zeile ausgehend von der Zeile darüber.

Berechne jeden Eintrag rekursiv

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Nummeriere Zeilen und Positionen ab 0. Die Definition wird zu einer Funktion: entry(row, col) ist an den Rändern 1, wobei col 0 oder row ist, und andernfalls entry(row-1, col-1) + entry(row-1, col). Sie ist korrekt, weil sie der Definition entspricht.

Die Rekursion endet nur an den Rändern, die 1 zurückgeben. Daher benötigt ein Eintrag mit dem Wert v etwa 2v Aufrufe. Zeile r summiert sich auf bis zu 2^r, also benötigen 30 Zeilen etwa 2^31 Aufrufe, mehr als zwei Milliarden.

Algorithmus

Schreibe entry(row, col): Gib 1 zurück, wenn col 0 ist oder col gleich row ist.
Gib andernfalls entry(row-1, col-1) + entry(row-1, col) zurück.
Sammle für jede row von 0 bis numRows-1 entry(row, col) für jedes col von 0 bis row.
Gib die Liste der Zeilen zurück.

def pascalEntry(row, col):
    if col == 0 or col == row:
        return 1  # the edges of the triangle
    return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)


def generate(numRows):
    triangle = []
    for row in range(numRows):
        triangle.append([pascalEntry(row, col) for col in range(row + 1)])
    return triangle

Erstelle jede Zeile aus der darüberliegenden Zeile

Idee

Die Rekursion fragt immer wieder Einträge aus früheren Zeilen ab, und diese Zeilen werden ohnehin erstellt. Berechne die Zeilen also von oben nach unten, und lies beim Füllen der Zeile r die Zeile r-1, die bereits fertig ist. Jeder Eintrag erfordert eine Addition: Die Tabelle mit kleineren Ergebnissen ist die Ausgabe selbst.

Wenn du jede Zeile zunächst mit r + 1 Einsen füllst, sind beide Ränder gesetzt; für die Zeilen 0 und 1, die keine inneren Positionen haben, ist daher kein Sonderfall nötig. Das Dreieck hat 1 + 2 + ... + n, also etwa n²/2, Einträge. Der Aufwand beträgt somit O(n²), ohne zusätzlichen Speicherbedarf über die Ausgabe hinaus: 465 Einträge für 30 Zeilen statt zwei Milliarden Aufrufe.

Algorithmus

Beginne mit einer leeren Liste von Zeilen.
Erstelle für jede row von 0 bis numRows-1 row + 1 Einsen.
Setze für jede col von 1 bis row-1 den Wert auf die Summe der Positionen col-1 und col der vorherigen Zeile.
Füge die Zeile hinzu und fahre fort. Gib die Liste zurück.

def generate(numRows):
    triangle = [[1]]
    for row in range(1, numRows):
        above = triangle[-1]
        values = [1] * (row + 1)  # both edges are 1
        for col in range(1, row):
            values[col] = above[col - 1] + above[col]
        triangle.append(values)
    return triangle

Stolperfallen und Grenzfälle

Es werden numRows + 1 Zeilen zurückgegeben. Bei Nummerierung ab 0 ist die letzte benötigte Zeile numRows-1.
Die innere Schleife läuft über die Ränder. Position 0 hat keinen linken Elternknoten und Position row keinen rechten, daher führt ihr Auslesen zu einem Zugriff außerhalb der Grenzen.
Ein Bereich, der bei kleinen Zeilen fehlschlägt. Swift's 1..<row stürzt ab, wenn row 0 ist, und R's 2:(row-1) zählt bis 1 herunter, wenn row 2 ist.
Einträge mit Fakultäten berechnen. C(29, 14) passt in einen int, aber 29! führt selbst bei einer 64-Bit-Ganzzahl zu einem Überlauf.
Für jede Zeile dasselbe Array anhängen und es dann ändern. Jede Zeile in der Antwort wird dadurch zur letzten.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität beim Erzeugen des Pascalschen Dreiecks?

O(n²) für n Zeilen: Das Dreieck hat etwa n²/2 Einträge, und jeder Eintrag erfordert eine Addition. Das ist optimal, da du jeden Eintrag der Ausgabe schreiben musst. Der zusätzliche Speicherplatz über die Ausgabe hinaus beträgt O(1).

Wie hängt das Pascalsche Dreieck mit Binomialkoeffizienten zusammen?

Der Eintrag k der Zeile r, von 0 an gezählt, ist C(r, k), die Anzahl der Möglichkeiten, k Elemente aus r auszuwählen. Die Summenregel ist die Identität C(r, k) = C(r-1, k-1) + C(r-1, k), und die Summe der Zeile r ergibt 2^r, die Anzahl der Teilmengen von r Elementen.

Kannst du eine Zeile berechnen, ohne die Zeilen darüber aufzubauen?

Ja. Beginne mit 1 und ermittle jeden nächsten Eintrag aus dem vorherigen: C(r, k) = C(r, k-1) × (r-k+1) / k. Multipliziere vor dem Teilen, damit die Division ohne Rest aufgeht, und verwende für das Produkt eine 64-Bit-Ganzzahl. Zeile r benötigt dann O(r) Zeit.

def generate(numRows):
    # Schreibe hier den Code

Test #1

Test #2

Argument

numRows = 5

Erwartete Ausgabe

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]