Il fattoriale di un numero è un importante concetto matematico. Puoi usarlo per eseguire permutazioni e combinazioni, scrivere espressioni esponenziali e logaritmiche e calcolare la probabilità.
Lo usi per trovare il numero di modi diversi in cui puoi progettare una disposizione dei posti a sedere o scegliere le magliette per la tua vacanza alle Maldive. Ma come si calcola il fattoriale di un numero?
Qual è il fattoriale di un numero?
Il fattoriale di un numero positivo è il prodotto di tutti i numeri interi positivi minori o uguali al valore del numero stesso. Un numero seguito da un punto esclamativo (!) indica il fattoriale di un numero. Rappresenti il fattoriale di cinque come 5! e calcolalo come:
5! = 5 * 4 * 3 * 2 * 1 = 120
Un altro modo per visualizzarlo è:
5! = 5 * 4! dove 4! = 4 * 3!, 3! = 3 * 2! e così via fino ad ottenere 1! = 1 * 0! che è 1.
Utilizzerai questo concetto per costruire il nostro programma fattoriale usando un concetto popolare chiamato ricorsione.
Cos'è la ricorsione?
La ricorsione è un processo in cui una funzione chiama se stessa. Uno dei principali vantaggi di questo processo è che suddivide un problema più grande in blocchi più piccoli. Questo rende il problema più facile da risolvere.
È possibile utilizzare la ricorsione per risolvere i problemi appropriati in tre semplici passaggi:
- Trova il caso base: Se una funzione chiama sempre se stessa, il processo sarà infinito. Per evitare che ciò accada, definisci un caso base che diventi il punto di arresto logico per la tua funzione. Ad esempio, in un programma fattoriale, interrompere il calcolo a zero. Questo diventa il caso base del problema.
- Trova la relazione tra il problema e i sottoproblemi: Suddividi il problema più grande in un sottoproblema. Ad esempio, il problema è trovare il fattoriale di cinque. Supponiamo di avere la risposta del fattoriale di quattro, cioè 24. Come otterrai il fattoriale di cinque usando 24? Moltiplicando cinque stesso in esso. Questa è la relazione tra il problema e il sottoproblema.
- Generalizza la relazione trovata nel passaggio 2: Ora che hai la relazione, generalizzala in termini di n. Quindi, il fattoriale di un numero n è il prodotto di n e il fattoriale di n-1.
Puoi usare questo concetto per trovare la somma di n numeri naturali, calcola MCD, MCM, la serie di Fibonacci e controlla i numeri primi.
Pseudo codice per la funzione fattoriale mediante ricorsione
Questo è come si usa la ricorsione e scrivi lo pseudo codice per costruire il tuo programma in qualsiasi lingua. Con lingue diverse, la sintassi e l'esecuzione cambiano ma la logica rimane intatta.
funzioneFatto(N)
Se n == 0 Poi // caso base
Ritorno1
Ritorno n * Call Fact (n - 1) // relazione generalizzata
Programma fattoriale in C
C è stato il primo linguaggio di programmazione di alto livello indipendente dalla piattaforma. Ha una sintassi rigorosa, fa distinzione tra maiuscole e minuscole ed esegue il codice con la massima velocità. È un linguaggio di programmazione procedurale e quindi dichiari qualsiasi funzione in cima a principale funzione. Ecco come puoi costruire il programma fattoriale usando la ricorsione in linguaggio C:
Puoi trovare l'intero codice sorgente del programma fattoriale usando la ricorsione in C, Java e Python in questo Deposito GitHub.
- Importa il file di intestazione dell'output di input standard per visualizzare l'output sullo schermo.
#includere <stdio.h> - Definisci funzione fatto e prendere intero N come argomento.
intfatto(int N){ - Scrivi il caso base della funzione usando il Se dichiarazione e controllarne l'uguaglianza usando ==. Se n è uguale a zero, restituisce uno.
se (n == 0)
ritorno1; - Scrivi l'equazione generalizzata e restituisci il prodotto di N con una chiamata di funzione di sottoproblema n-1.
ritorno n * fatto (n - 1);
} - Dichiara la funzione principale e inizializza una variabile di tipo intero per memorizzare il numero di cui vuoi trovare il fattoriale.
intprincipale(){
int numero = 5; - Visualizzare il fattoriale del numero utilizzando il stampaf() funzione. %D è l'identificatore di formato decimale. Utilizzare ciascuno degli identificatori di formato per sostituirlo con il numero di cui si desidera trovare il fattoriale e ottenere il risultato chiamando la funzione.
stampaf("Il fattoriale di %d è %d", num, fatto (num));
ritorno0;
}
Programma fattoriale in Java
Java è un linguaggio di programmazione compilato ed è indipendente dalla piattaforma. Memorizzi tutto il codice all'interno di a classe e l'esecuzione comincia dal principale funzione. Fa distinzione tra maiuscole e minuscole e sintassi rigorosa. Il codice è un po' più lungo ma più veloce rispetto a Python. Ecco come puoi costruire il programma fattoriale usando la ricorsione in Java:
- Definire la classe principale.
classePrincipale{ - Definire una funzione statica con tipo di ritorno int che accetta una variabile n di tipo intero. Hai dichiarato un metodo statico poiché anche il metodo principale in Java è dichiarato statico. Inoltre, non è possibile chiamare un metodo non statico da un'istanza statica.
staticointfatto(int N){ - Scrivi il caso base della funzione usando il Se dichiarazione e controllarne l'uguaglianza usando ==. Se n è uguale a zero, restituisce uno.
se (n == 0)
ritorno1; - Scrivi l'equazione generalizzata e restituisci il prodotto di N con una chiamata di funzione di sottoproblema n-1.
ritorno n * fatto (n - 1);
} - Dichiarare la funzione principale in Java. Dichiara il modificatore di accesso come pubblico, quindi può essere accessibile da tutte le altre classi e metodi. Dichiari la funzione principale come statico in modo che il compilatore possa invocarlo senza istanziare la classe. Il tipo di ritorno è vuoto, e accetta argomenti di tipo Corda. Memorizza il numero di cui vuoi trovare il fattoriale.
pubblicostaticovuotoprincipale(Stringa[] argomenti){
int numero = 5; - Usa il stampaln() metodo, un'istanza di Printstream classe, definita nel Sistema class per visualizzare il fattoriale del numero.
System.out.println("Fattoriale di " + numero + " È " + fatto (num));
}
}
Programma fattoriale in Python
Scrivere codice in Python è semplicissimo e divertente. Poiché si tratta di un linguaggio indipendente dalla piattaforma interpretato, non è necessario dichiarare il tipo di dati delle variabili. Eviti anche di dover dichiarare classi e importare librerie per un programma così semplice. Il parco giochi è pronto per iniziare a programmare.
La sintassi è più semplice, con una lunghezza di codice ridotta ma richiede un po' più di tempo per l'esecuzione rispetto agli altri linguaggi. Ecco come puoi costruire il programma fattoriale usando la ricorsione in Python:
- Definire la funzione fatto che accetta come argomento n.
deffatto(N): - Scrivi il caso base della funzione usando il Se dichiarazione e controllarne l'uguaglianza usando ==. Se n è uguale a zero, restituisce uno.
se n == 0:
ritorno1 - Scrivi l'equazione generalizzata e restituisci il prodotto di N con una chiamata di funzione di sottoproblema n-1.
ritorno n * fatto (n-1) - Memorizza il numero di cui desideri trovare il fattoriale e visualizzalo utilizzando l'istruzione print.
numero = 5;
stampa("Fattoriale di", numero, "È", fatto (num))
Ci sono molte applicazioni della ricorsione
La ricorsione è un modo efficace per risolvere i problemi. È il punto cruciale dell'Intelligenza Artificiale e ha usi nel mondo reale nei giochi di puzzle come gli scacchi o il Sudoku.
È anche un potente metodo per ordinare strutture di dati come Tree o algoritmi di ordinamento come Quick sort e Merge sort. Potresti anche usare la ricorsione nella ricerca di algoritmi come la ricerca binaria, espressioni matematiche come la serie di Fibonacci e altro ancora.
