Faktorialet til et tall er et viktig matematisk konsept. Du kan bruke den til å utføre permutasjoner og kombinasjoner, skrive eksponentielle og logaritmiske uttrykk og beregne sannsynlighet.
Du bruker den til å finne antall forskjellige måter du kan designe en sittegruppe på, eller velge t-skjorter for ferien til Maldivene. Men hvordan kan du beregne faktoren til et tall?
Hva er faktoren til et tall?
Faktorialet til et positivt tall er produktet av alle positive heltall mindre enn eller lik verdien av selve tallet. Et tall etterfulgt av et utropstegn(!) angir faktoren til et tall. Du representerer faktoren på fem som 5! og regner det ut som:
5! = 5 * 4 * 3 * 2 * 1 = 120
En annen måte å visualisere det på er:
5! = 5 * 4! hvor 4! = 4 * 3!, 3! = 3 * 2! og så videre til du får 1! = 1 * 0! som er 1.
Du vil bruke dette konseptet til å bygge vårt faktorielle program ved å bruke et populært konsept kalt rekursjon.
Hva er rekursjon?
Rekursjon er en prosess der en funksjon kaller seg selv. En av hovedfordelene med denne prosessen er at den deler et større problem i mindre biter. Dette gjør problemet lettere å løse.
Du kan bruke rekursjon til å løse passende problemer i tre enkle trinn:
- Finn grunntilfellet: Hvis en funksjon alltid kaller seg selv, vil prosessen være uendelig. For å forhindre at dette skjer, definer et grunntilfelle som blir det logiske stopppunktet for funksjonen din. For eksempel, i et faktorprogram, stopp beregningen ved null. Dette blir grunnlaget for problemet.
- Finn sammenhengen mellom problemet og delproblemene: Bryt ned det større problemet til et delproblem. For eksempel er problemet å finne faktoren på fem. Anta at du har svaret på faktor på fire, det vil si 24. Hvordan får du faktoren på fem ved å bruke 24? Ved å multiplisere fem selv inn i det. Dette er forholdet mellom problemet og delproblemet.
- Generaliser relasjonen funnet i trinn 2: Nå som du har relasjonen, generaliser den i form av n. Så, faktorialet til et tall n er produktet av n og faktorialet av n-1.
Du kan bruke dette konseptet til finn summen av n naturlige tall, beregne GCD, LCM, Fibonacci-serien, og sjekk primtall.
Pseudokode for faktorfunksjonen ved bruk av rekursjon
Dette er hvordan du bruker rekursjon og skriv pseudokoden for å bygge programmet ditt på et hvilket som helst språk. Med forskjellige språk endres syntaksen og utførelsen, men logikken forblir intakt.
funksjonFaktum(n)
Hvis n == 0 deretter // base case
Komme tilbake1
Komme tilbake n * Anropsfakta (n - 1) // generalisert relasjon
Faktorprogram i C
C var det første plattformuavhengige programmeringsspråket på høyt nivå. Den har streng syntaks, skiller mellom store og små bokstaver og kjører kode med den raskeste hastigheten. Det er et prosessuelt programmeringsspråk, og derfor erklærer du hvilken som helst funksjon på toppen av hoved- funksjon. Slik kan du bygge det faktorielle programmet ved å bruke rekursjon i C-språk:
Du kan finne hele kildekoden til det faktorielle programmet ved å bruke rekursjon i C, Java og Python i denne GitHub-depot.
- Importer standard inndatautdata-header-filen for å vise utdataene på skjermen.
#inkludere <stdio.h> - Definer funksjon faktum og ta heltall n som et argument.
intfaktum(int n){ - Skriv grunntallet for funksjonen ved å bruke hvis uttalelse og kontroller dens likhet ved hjelp av ==. Hvis n er lik null, returner én.
hvis (n == 0)
komme tilbake1; - Skriv den generaliserte ligningen og returner produktet av n med et funksjonskall av underproblem n-1.
komme tilbake n * faktum (n - 1);
} - Erklær hovedfunksjonen og initialiser en variabel av heltallstype for å lagre tallet du ønsker å finne faktoren til.
inthoved-(){
int num = 5; - Vis faktoren til tallet ved å bruke printf() funksjon. %d er desimalformatspesifikasjonen. Bruk hver av formatspesifikasjonene for å erstatte den med tallet du ønsker å finne faktoren til, og få resultatet ved å kalle funksjonen.
printf("Faktor for %d er %d", num, faktum (num));
komme tilbake0;
}
Faktorprogram i Java
Java er et kompilert programmeringsspråk og er plattformuavhengig. Du lagrer all koden i en klasse og utførelsen starter fra hoved- funksjon. Den skiller mellom store og små bokstaver og syntaksstreng. Koden er litt lengre, men raskere sammenlignet med Python. Slik kan du bygge det faktorielle programmet ved å bruke rekursjon i Java:
- Definer hovedklassen.
klasseHoved{ - Definer en statisk funksjon med returtype int som aksepterer en variabel n av heltallstype. Du erklærte en statisk metode da hovedmetoden i Java også erklæres som statisk. I tillegg kan du ikke kalle en ikke-statisk metode fra en statisk forekomst.
statiskintfaktum(int n){ - Skriv grunntallet for funksjonen ved å bruke hvis uttalelse og kontroller dens likhet ved hjelp av ==. Hvis n er lik null, returner én.
hvis (n == 0)
komme tilbake1; - Skriv den generaliserte ligningen og returner produktet av n med et funksjonskall av underproblem n-1.
komme tilbake n * faktum (n - 1);
} - Deklarer hovedfunksjonen i Java. Erklær tilgangsmodifikatoren som offentlig, slik at den kan være tilgjengelig for alle de andre klassene og metodene. Du erklærer hovedfunksjonen som statisk slik at kompilatoren kan starte den uten å instansiere klassen. Returtypen er tomrom, og den aksepterer argumenter av typen String. Lagre nummeret du vil finne faktoren til.
offentligstatisktomromhoved-(String[] args){
int num = 5; - Bruke println() metode, en forekomst av PrintStream klasse, definert i System klasse for å vise faktoren til tallet.
System.out.println("Faktoriell av " + num + " er " + faktum (antall));
}
}
Faktorprogram i Python
Å skrive kode i Python er superenkelt og morsomt. Siden det er et tolket plattformuavhengig språk, trenger du ikke å deklarere datatypen for variabler. Du slipper også å måtte deklarere klasser og importere biblioteker for et så enkelt program. Lekeplassen er klar til å begynne å kode.
Syntaksen er enklere, med en liten kodelengde, men tar litt mer tid å utføre enn de andre språkene. Slik kan du bygge det faktorielle programmet ved å bruke rekursjon i Python:
- Definer funksjon faktum som aksepterer som argument n.
deffaktum(n): - Skriv grunntallet for funksjonen ved å bruke hvis uttalelse og kontroller dens likhet ved hjelp av ==. Hvis n er lik null, returner én.
hvis n == 0:
komme tilbake1 - Skriv den generaliserte ligningen og returner produktet av n med et funksjonskall av underproblem n-1.
komme tilbake n * faktum (n-1) - Lagre nummeret du ønsker å finne faktoren til, og vis det ved å bruke utskriftserklæringen.
antall = 5;
skrive ut("Faktoriell av", num, "er", faktum (antall))
Det er mange anvendelser av rekursjon
Rekursjon er en effektiv måte å løse problemer på. Det er kjernen i kunstig intelligens og har virkelige bruksområder i puslespill som sjakk eller Sudoku.
Det er også en kraftig metode for sortering av datastrukturer som tre eller sorteringsalgoritmer som Hurtigsortering og Slå sammen sortering. Du kan også bruke rekursjon i søkealgoritmer som binært søk, matematiske uttrykk som Fibonacci-serien og mer.
