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:
Come viene implementato questo esercizio in Python: la ricorsione
Questo esercizio è pensato per essere completato usando recursion, invece dei cicli.
Una funzione ricorsiva è una funzione che chiama se stessa: è utile quando si risolvono problemi definiti in termini di se stessi.
Per evitare la ricorsione infinita (o, più precisamente, per evitare di far traboccare lo stack), si usa quello che viene chiamato «caso base».
Quando si raggiunge il caso base, viene restituito un valore non ricorsivo, il che permette alla chiamata di funzione precedente di risolversi e restituire il suo valore, e così via, risalendo lo stack a ritroso finché la prima chiamata alla funzione non restituisce la risposta.
Potremmo scrivere una funzione ricorsiva per calcolare 5! (cioè 5 * 4 * 3 * 2 * 1) in questo modo:
def factorial(number):
if number <= 1: # base case
return 1
return number * factorial(number - 1) # recursive case
print(factorial(5)) # returns 120
Infine, va notato che Python limita il numero di volte in cui si possono effettuare chiamate ricorsive (1000 per impostazione predefinita) e non ottimizza la ricorsione in coda.
I messaggi delle eccezioni
A volte è necessario sollevare un'eccezione.
Quando lo fai, dovresti sempre includere un messaggio di errore significativo per indicare qual è l'origine dell'errore.
Rende il codice più leggibile e aiuta molto durante il debug.
Nei casi in cui sai che l'origine dell'errore sarà di un certo tipo, puoi scegliere di sollevare uno dei tipi di errore integrati, ma dovresti comunque includere un messaggio significativo.
Questo esercizio richiede in particolare di usare l'istruzione raise per «lanciare» diversi ValueError quando alla funzione rows() viene passato un numero negativo.
I test passeranno solo se usi raise sull'exception e ci alleghi un messaggio.
Per sollevare un ValueErrors con un messaggio, scrivi il messaggio come argomento al tipo exception:
# if the rows function is passed a negative number.
raise ValueError("number of rows is negative")
