Pascal's Triangle

Q: Qual è la complessità temporale della generazione del triangolo di Pascal?

O(n²) per n righe: il triangolo ha circa n²/2 elementi e ciascuno richiede un'addizione. È ottimale, poiché devi scrivere ogni elemento dell'output. Lo spazio aggiuntivo oltre all'output è O(1) .

Q: Qual è la relazione tra il triangolo di Pascal e i coefficienti binomiali?

La voce k della riga r , contando da 0, è C(r, k) , il numero di modi per scegliere k elementi tra r . La regola della somma è l’identità C(r, k) = C(r-1, k-1) + C(r-1, k) , e la somma della riga r è 2^r , il numero di sottoinsiemi di r elementi.

Q: Riesci a calcolare una riga senza costruire le righe che la precedono?

Sì. Inizia da 1 e ottieni ogni elemento successivo da quello precedente: C(r, k) = C(r, k-1) × (r-k+1) / k . Moltiplica prima di dividere, così la divisione è esatta, e usa un intero a 64 bit per il prodotto. La riga r richiede quindi O(r) tempo.

FacileProgrammazione dinamica

+10

Nel triangolo di Pascal, la prima riga è [1]. Ogni riga successiva ha una voce in più, inizia e finisce con 1 e ogni voce intermedia è la somma delle due voci direttamente sopra di essa. Ricevi un numero intero numRows. Restituisci le prime numRows righe del triangolo, partendo dalla riga superiore, con ogni riga come array di numeri interi.

Funzione

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

numRowsinteger: quante righe del triangolo costruire
Restituisceinteger-2d-array: le prime numRows righe, prima la riga superiore

Vincoli

1 ≤ numRows ≤ 30
Ogni valore delle prime 30 righe rientra in un intero con segno a 32 bit. Il più grande è 77558760, al centro della riga 30.

Esempi

Input: numRows = 5
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Spiegazione: Ogni voce interna somma le due sopra di essa. Quarta riga: 3 = 1 + 2 e 3 = 2 + 1. Quinta riga: 4 = 1 + 3, 6 = 3 + 3, 4 = 3 + 1.

Input: numRows = 1
Output: [[1]]
Spiegazione: Con una sola riga, il triangolo è solo la sua cima, [1].

Per approfondire

Riesci a mantenere un solo array e ad aggiornarlo sul posto, riga dopo riga? In quale direzione deve procedere il ciclo interno, e perché?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Un elemento è la somma di due elementi della riga precedente. Applicare questa regola da zero per ogni elemento ricalcola gli stessi valori, e il lavoro raddoppia a ogni riga. Le righe che restituisci sono le risposte memorizzate a quei problemi più piccoli, quindi costruisci il triangolo dall’alto verso il basso, ogni riga a partire da quella precedente.

Calcola ricorsivamente ogni voce

Corretto, ma non termina sui test più grandi

Intuizione

Numera righe e posizioni a partire da 0. La definizione diventa una funzione: entry(row, col) è 1 ai bordi, dove col è 0 o row, e altrimenti entry(row-1, col-1) + entry(row-1, col). È corretta perché è la definizione.

La ricorsione si ferma solo ai bordi, che restituiscono 1, quindi un elemento di valore v richiede circa 2v chiamate. La riga r arriva a un totale di 2^r, quindi 30 righe richiedono circa 2^31 chiamate, più di due miliardi.

Algoritmo

Scrivi entry(row, col): restituisci 1 se col è 0 oppure col è uguale a row.
Altrimenti restituisci entry(row-1, col-1) + entry(row-1, col).
Per ogni row da 0 a numRows-1, raccogli entry(row, col) per ogni col da 0 a row.
Restituisci l'elenco delle righe.

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

Costruisci ogni riga a partire da quella sopra

Intuizione

La ricorsione continua a chiedere valori delle righe precedenti, e tu costruisci comunque quelle righe. Calcola quindi le righe dall’alto verso il basso e, mentre riempi la riga r, leggi la riga r-1, che è già pronta. Ogni valore richiede un’addizione: la tabella delle risposte più piccole è il risultato stesso.

Iniziare ogni riga con r + 1 uni imposta entrambi i bordi, quindi le righe 0 e 1, che non hanno posizioni interne, non richiedono casi speciali. Il triangolo contiene 1 + 2 + ... + n, circa n²/2, valori, quindi il lavoro è O(n²) senza memoria oltre a quella del risultato: 465 valori per 30 righe invece di due miliardi di chiamate.

Algoritmo

Inizia con una lista vuota di righe.
Per ogni row da 0 a numRows-1, crea row + 1 uni.
Per ogni col da 1 a row-1, impostalo sulla somma delle posizioni col-1 e col della riga precedente.
Aggiungi la riga e continua. Restituisci la lista.

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

Trappole e casi limite

Restituire numRows + 1 righe. Numerando da 0, l'ultima riga necessaria è numRows-1.
Eseguire il ciclo interno sui bordi. La posizione 0 non ha un elemento genitore a sinistra e la posizione row non ne ha uno a destra, quindi leggerle causa un accesso fuori dai limiti.
Un intervallo che non funziona con righe piccole. In Swift, 1..<row causa un arresto anomalo quando row è 0, e in R 2:(row-1) conta all'indietro fino a 1 quando row è 2.
Calcolare le voci usando i fattoriali. C(29, 14) rientra in un int, ma 29! supera il limite anche di un intero a 64 bit.
Aggiungere lo stesso array per ogni riga e poi modificarlo. Tutte le righe della risposta diventano l'ultima.

Domande frequenti3

Qual è la complessità temporale della generazione del triangolo di Pascal?

O(n²) per n righe: il triangolo ha circa n²/2 elementi e ciascuno richiede un'addizione. È ottimale, poiché devi scrivere ogni elemento dell'output. Lo spazio aggiuntivo oltre all'output è O(1).

Qual è la relazione tra il triangolo di Pascal e i coefficienti binomiali?

La voce k della riga r, contando da 0, è C(r, k), il numero di modi per scegliere k elementi tra r. La regola della somma è l’identità C(r, k) = C(r-1, k-1) + C(r-1, k), e la somma della riga r è 2^r, il numero di sottoinsiemi di r elementi.

Riesci a calcolare una riga senza costruire le righe che la precedono?

Sì. Inizia da 1 e ottieni ogni elemento successivo da quello precedente: C(r, k) = C(r, k-1) × (r-k+1) / k. Moltiplica prima di dividere, così la divisione è esatta, e usa un intero a 64 bit per il prodotto. La riga r richiede quindi O(r) tempo.

def generate(numRows):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

numRows = 5

Output atteso

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