Introduzione
Con questo bel tempo, non hai proprio voglia di passare un'ora in aula.
Seccato, entri in aula e noti sulla lavagna una forma triangolare stranamente soddisfacente.
Mentre aspetti che arrivi l'insegnante di matematica, non puoi fare a meno di notare alcuni schemi nel triangolo: i valori esterni sono tutti 1, ogni riga successiva ha un valore in più della precedente e il triangolo è simmetrico.
Strano!
Poco dopo che ti sei seduto, entra l'insegnante e ti spiega che questo triangolo è il famoso triangolo di Pascal.
Nel corso dell'ora successiva, l'insegnante ti svela alcune cose sorprendenti 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 pari e i numeri dispari in modo diverso, ottieni un bellissimo schema chiamato triangolo di Sierpiński.
L'insegnante esorta te e i tuoi compagni a cercare altri usi e ti assicura che ce ne sono molti altri!
In quel momento suona la campanella.
Ti rendi conto che per l'ultima ora sei stato completamente assorbito nell'apprendere cose sul triangolo di Pascal.
Afferri 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:
