Factorial
Il fattoriale di un numero intero non negativo n, scritto n!, è il prodotto di tutti i numeri interi da 1 fino a n. Per esempio, 4! = 1 × 2 × 3 × 4 = 24. Per definizione 0! = 1. La tua funzione riceve n e restituisce n!.
Funzione
- ninteger
- il numero intero di cui calcoli il fattoriale
- Restituisceinteger
- il prodotto di tutti i numeri interi da 1 a n, che è 1 quando n è 0
Vincoli
0 ≤ n ≤ 12- The answer rientra in un intero con segno a 32 bit: il più grande è
12! = 479001600.
Esempi
- Input
- n = 5
- Output
- 120
- Spiegazione
- Moltiplica
1 × 2 × 3 × 4 × 5. Il prodotto progressivo è 1, 2, 6, 24 e termina a 120.
- Input
- n = 0
- Output
- 1
- Spiegazione
- Non c’è nulla da moltiplicare e un prodotto senza fattori è
1. Ecco perché0! = 1.
+11 test nascosti all’invio
Per approfondire
100! ha 158 cifre. Riesci a contare quanti zeri finali ha senza calcolarlo?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Scrivi
4!e5!come prodotti. In che modo5!è correlato a4!?5! = 5 × 4!. In generalen! = n × (n-1)!, e la catena si ferma a0! = 1.Mantieni un prodotto progressivo che inizi da
1e moltiplicalo per ogni numero da2an. Iniziare da 1 dà anche la risposta corretta per0e1.
Soluzione
Il fattoriale ha due descrizioni equivalenti, e ciascuna si traduce in codice. Come prodotto, n! = 1 × 2 × ... × n, che è un ciclo. Come definizione ricorsiva, 0! = 1 e n! = n × (n-1)!, che è una funzione che chiama sé stessa. Entrambe eseguono circa n moltiplicazioni. È meglio concludere con il ciclo, perché non richiede uno stack di chiamate.
Ricorsione dalla definizione
Intuizione
Il fattoriale è definito tramite un fattoriale più piccolo: n! = n × (n-1)!. Se sai già che 4! = 24, allora 5! = 5 × 24 = 120. Una funzione ricorsiva scrive quella frase come codice. Per ottenere factorial(n), richiede factorial(n-1) e moltiplica il risultato per n.
Le chiamate hanno bisogno di un punto in cui fermarsi, il caso base: factorial(0) restituisce 1 senza effettuare alcuna chiamata. Ogni chiamata diminuisce n di uno, quindi partendo da 5 le chiamate sono 5, 4, 3, 2, 1, 0. Poi i risultati risalgono la catena: 1, 1, 2, 6, 24, 120.
Ci sono n + 1 chiamate e n moltiplicazioni, quindi il tempo è O(n). Ogni chiamata resta in attesa sullo stack finché non viene restituito il risultato della chiamata sottostante, quindi lo stack contiene n + 1 frame, il che richiede spazio O(n). Con n ≤ 12 è una quantità minima, ma lo stesso schema con un input grande causa un overflow dello stack.
Algoritmo
- Se
nè0, restituisci1. Questo è il caso base. - Altrimenti, chiama la funzione su
n-1. - Moltiplica quel risultato per
ne restituiscilo.
def factorial(n):
if n == 0:
return 1 # base case: 0! = 1
return n * factorial(n - 1)Moltiplicare in un ciclo
Intuizione
Espandi la ricorsione e ottieni un prodotto progressivo. Inizia con result = 1 e moltiplicalo per 2, poi per 3 e così via fino a n. Per n = 5 il risultato è 1, 2, 6, 24, 120.
Partire da 1 copre anche gli input più piccoli. Per n = 0 e n = 1 il ciclo da 2 a n viene eseguito zero volte e la funzione restituisce il valore iniziale 1, che è la risposta corretta per entrambi.
Il ciclo esegue n-1 moltiplicazioni, richiede un tempo O(n) e occupa uno spazio O(1) per conservare un numero. Non c'è uno stack di chiamate che possa andare in overflow, ed è per questo che gli intervistatori si aspettano questa versione dopo aver mostrato quella ricorsiva.
Algoritmo
- Imposta
result = 1. - Fai un ciclo con
kda2an, inclusi entrambi. - Moltiplica
resultperka ogni passaggio. - Restituisci
result.
def factorial(n):
result = 1
for k in range(2, n + 1):
result *= k
return result
Trappole e casi limite
Il codice del fattoriale è breve, quindi i bug si nascondono nei casi limite.
- Iniziare il prodotto da
0. Ogni moltiplicazione lo mantiene a 0. Il valore iniziale di un prodotto è1. - Interrompere la ricorsione solo quando
n == 1. Se viene chiamata con0, la funzione non raggiunge mai il caso base: prosegue con -1, -2 e così via, fino a causare un overflow dello stack. Impostan == 0come caso base. - Usare il ciclo con
k < ninvece dik ≤ n. In questo modo si omette l'ultimo fattore e si restituisce(n-1)!, quindi5dà 24 invece di 120. - Ignorare l'overflow.
13! = 6227020800non entra in un intero con segno a 32 bit. In Java e C# il prodotto va silenziosamente in overflow e restituisce un numero errato; in C l'overflow con segno ha un comportamento indefinito e una build di debug di Rust genera un panic. Un intero a 64 bit può contenere fino a20!; oltre, servono interi a precisione arbitraria. - In Swift, scrivere
for k in 2...n. Un intervallo chiuso il cui estremo finale è minore di quello iniziale causa un arresto anomalo in fase di esecuzione quandonè 0 o 1.
Domande frequenti4
Qual è la complessità temporale del calcolo di un fattoriale?
Sia il ciclo sia la ricorsione eseguono una moltiplicazione per ogni numero fino a n, quindi il tempo è O(n). Il ciclo richiede uno spazio aggiuntivo pari a O(1). La ricorsione mantiene un frame dello stack per ogni chiamata finché non viene restituito il caso base, quindi usa uno spazio pari a O(n).
Perché 0! è uguale a 1?
0! è il prodotto di nessun numero, e un prodotto senza fattori è 1, così come una somma senza addendi è 0. Inoltre, mantiene valida la regola n! = n × (n-1)! per n = 1: 1! = 1 × 0! = 1. Anche il conteggio concorda: esiste esattamente un modo per disporre zero elementi.
Per il fattoriale è meglio la ricorsione o un ciclo?
Eseguono le stesse moltiplicazioni e restituiscono la stessa risposta. La versione ricorsiva si legge come la definizione matematica, motivo per cui è un classico primo esercizio sulla ricorsione. Il ciclo usa memoria costante e non può causare un overflow dello stack delle chiamate, quindi è la scelta migliore nel codice reale.
Qual è il fattoriale più grande che può essere contenuto in un intero?
12! = 479001600 è il fattoriale più grande che può essere rappresentato con un intero con segno a 32 bit. 20! = 2432902008176640000 è il più grande per un intero con segno a 64 bit. Oltre quel limite servono numeri di dimensione illimitata, come int di Python, BigInteger di Java o BigInt di JavaScript.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def factorial(n):
# Scrivi il codice quiCaso 1
Caso 2
Input
n = 5
Atteso
120