Introduzione
Con questo bel tempo, non hai proprio voglia di passare un'ora in aula.
Annoiato, entri in aula e noti sulla lavagna una forma triangolare stranamente soddisfacente.
Mentre aspetti l'arrivo del tuo insegnante di matematica, non puoi fare a meno di notare alcuni schemi nel triangolo: i valori esterni sono tutti uno, ogni riga successiva ha un valore in più della precedente e il triangolo è simmetrico.
Strano!
Poco dopo esserti seduto, il tuo insegnante entra in aula e ti spiega che questo è il famoso triangolo di Pascal.
Nell'ora successiva, il tuo insegnante ti svela alcune cose straordinarie nascoste in questo triangolo:
- Si può usare per calcolare in quanti modi puoi scegliere K elementi da N valori.
- Contiene la successione di Fibonacci.
- Se colori i numeri dispari e pari in modo diverso, ottieni un bellissimo schema chiamato triangolo di Sierpiński.
L'insegnante esorta te e i tuoi compagni a cercare altri utilizzi, e ti assicura che ce ne sono molti altri!
Proprio in quel momento suona la campanella.
Ti rendi conto che per l'ultima ora sei stato completamente assorbito dallo studio del triangolo di Pascal.
Prendi in fretta il portatile dallo zaino ed esci, pronto a goderti il sole e le meraviglie del triangolo di Pascal.
Istruzioni
Il tuo compito è produrre le prime N righe del triangolo di Pascal.
Il triangolo di Pascal è un array triangolare di numeri interi positivi.
Nel triangolo di Pascal, il numero di valori in una riga è uguale al numero della riga stessa (che inizia da uno).
Quindi la prima riga ha un valore, la seconda ne ha due, e così via.
La prima riga, quella più in alto, ha un unico valore: 1.
I valori delle righe successive si calcolano sommando i numeri immediatamente a destra e a sinistra della posizione attuale nella riga precedente.
Se la riga precedente non ha un valore a sinistra o a destra della posizione attuale (cosa che succede solo per le posizioni più a sinistra e più a destra), considera il valore di quella posizione come zero (di fatto, «ignorandolo» nella somma).
Esempio
Vediamo le prime 5 righe del triangolo di Pascal:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
La riga più in alto ha un solo valore, che è 1.
I valori più a sinistra e più a destra hanno una sola posizione precedente da considerare, che è, rispettivamente, la posizione alla loro destra e alla loro sinistra.
Dato che il valore più in alto è 1, ne consegue che anche tutti i valori più a sinistra e più a destra sono 1.
Tutti gli altri valori hanno due posizioni da considerare.
Per esempio, il valore centrale della quinta riga (1 4 6 4 1) è 6, dato che i valori alla sua sinistra e alla sua destra nella riga precedente sono 3 e 3:
