Arvu faktoriaal on oluline matemaatiline mõiste. Saate seda kasutada permutatsioonide ja kombinatsioonide tegemiseks, eksponentsiaalsete ja logaritmiliste avaldiste kirjutamiseks ning tõenäosuse arvutamiseks.

Kasutate seda, et leida mitmeid erinevaid viise, kuidas kujundada istekoha paigutust või valida oma puhkuseks Maldiividel t-särke. Aga kuidas saab arvutada arvu faktoriaali?

Mis on arvu faktoriaal?

Positiivse arvu faktoriaal on kõigi positiivsete täisarvude korrutis, mis on arvu enda väärtusest väiksemad või sellega võrdsed. Arv, millele järgneb hüüumärk(!), tähistab arvu faktoriaali. Te esindate viie faktoriaali kui 5! ja arvutage see järgmiselt:

5! = 5 * 4 * 3 * 2 * 1 = 120

Teine viis selle visualiseerimiseks on:

5! = 5 * 4! kus 4! = 4 * 3!, 3! = 3 * 2! ja nii edasi, kuni saad 1! = 1 * 0! mis on 1.

Kasutate seda kontseptsiooni meie faktoriaalprogrammi koostamiseks, kasutades populaarset kontseptsiooni nimega rekursioon.

Mis on rekursioon?

Rekursioon on protsess, mille käigus funktsioon kutsub ennast ise. Selle protsessi üks peamisi eeliseid on see, et see jagab suurema probleemi väiksemateks tükkideks. See muudab probleemi lahendamise lihtsamaks.

instagram viewer

Rekursiooni abil saate sobivate probleemide lahendamiseks teha kolme lihtsa sammu.

  1. Leidke põhijuhtum: Kui funktsioon kutsub end alati ise, on protsess lõpmatu. Selle vältimiseks määrake baasjuhtum, millest saab teie funktsiooni loogiline peatuspunkt. Näiteks faktoriaalprogrammis peatage arvutus nulli juures. Sellest saab probleemi aluseks.
  2. Leidke seos probleemi ja alamprobleemide vahel: Jagage suurem probleem alamprobleemiks. Näiteks on probleemiks viie faktoriaali leidmine. Oletame, et vastuseks on faktoriaal neli, see on 24. Kuidas saate 24 abil viie faktoriaali? Korrutades sellesse ennast viiega. See on seos probleemi ja alamprobleemi vahel.
  3. Üldistage 2. sammus leitud seos: Nüüd, kui teil on seos, üldistage see n-ga. Seega on arvu n faktoriaal arvu n ja n-1 faktoriaal.

Saate seda kontseptsiooni kasutada leida n naturaalarvu summa, arvutage GCD, LCM, Fibonacci seeria ja kontrollige algarve.

Rekursiooni kasutava faktorifunktsiooni pseudokood

See on kuidas te rekursiooni kasutate ja kirjutage pseudokood oma programmi koostamiseks mis tahes keeles. Erinevate keelte puhul süntaks ja täitmine muutuvad, kuid loogika jääb puutumatuks.

funktsiooniFakt(n)
 Kui n == 0 siis // põhijuhtum
Tagasi1
Tagasi n * Kõnefakt (n - 1) // üldistatud seos

Factorial programm C-s

C oli esimene kõrgetasemeline platvormist sõltumatu programmeerimiskeel. Sellel on range süntaks, see on tõstutundlik ja käivitab koodi kõige kiirema kiirusega. See on protseduuriline programmeerimiskeel ja seega deklareerite mis tahes funktsiooni peal peamine funktsiooni. Siin on, kuidas saate ehitada faktoriaalprogrammi rekursiooni abil C-keeles:

Kogu faktoriaalprogrammi lähtekoodi, kasutades rekursiooni C-s, Java-s ja Pythonis, leiate siit GitHubi hoidla.

  1. Importige standardse sisendväljundi päisefail väljundi ekraanile kuvamiseks.
    #kaasa <stdio.h>
  2. Määratlege funktsioon fakt ja võta täisarv n argumendina.
    intfakt(int n){
  3. Kirjutage funktsiooni põhitäht, kasutades kui avaldus ja kontrollige selle võrdsust kasutades ==. Kui n võrdub nulliga, tagasta üks.
     kui (n == 0)
    tagasi1;
  4. Kirjutage üldistatud võrrand ja tagastage korrutis n alamülesande funktsioonikutsega n-1.
    tagasi n * fakt (n - 1);
    }
  5. Deklareerige põhifunktsioon ja lähtestage täisarvu tüüpi muutuja, et salvestada arv, mille faktoriaali soovite leida.
    intpeamine(){
    int arv = 5;
  6. Kuvage numbri faktoriaal, kasutades nuppu printf() funktsiooni. %d on kümnendvormingu määraja. Kasutage iga vormingu spetsifikaatorit, et asendada see numbriga, mille faktoriaali soovite leida ja saada tulemus funktsiooni kutsudes.
     printf("%d faktoriaal on %d", arv, fakt (arv));
    tagasi0;
    }

Factorial programm Java keeles

Java on kompileeritud programmeerimiskeel ja platvormist sõltumatu. Kogu koodi salvestate a-sse klass ja täitmine algab peamine funktsiooni. See on tõstutundlik ja süntaksis range. Kood on Pythoniga võrreldes pisut pikem, kuid kiirem. Javas rekursiooni abil faktoriaalprogrammi saate luua järgmiselt.

  1. Määratlege põhiklass.
    klassPeamine{
  2. Määratlege staatiline funktsioon tagastustüübiga int, mis aktsepteerib täisarvu tüüpi muutujat n. Te deklareerisite staatilise meetodi, kuna Java põhimeetod on samuti deklareeritud staatiliseks. Lisaks ei saa te staatilisest eksemplarist mittestaatilist meetodit kutsuda.
    staatilineintfakt(int n){
  3. Kirjutage funktsiooni põhitäht, kasutades kui avaldus ja kontrollige selle võrdsust kasutades ==. Kui n võrdub nulliga, tagasta üks.
     kui (n == 0)
    tagasi1;
  4. Kirjutage üldistatud võrrand ja tagastage korrutis n alamülesande funktsioonikutsega n-1.
    tagasi n * fakt (n - 1);
     }
  5. Deklareerige Java põhifunktsioon. Deklareerige juurdepääsu modifikaatoriks kui avalik, nii et see on juurdepääsetav kõigi teiste klasside ja meetoditega. Te deklareerite põhifunktsiooni kui staatiline et kompilaator saaks selle välja kutsuda ilma klassi instantseerimata. Tagastamise tüüp on tühine, ja see aktsepteerib tüüpi argumente String. Salvestage number, mille faktoriaali soovite leida.
    avalikstaatilinetühinepeamine(String[] args){
    int arv = 5;
  6. Kasuta println() meetod, näide PrintStream klass, mis on määratletud Süsteem klassis, et kuvada arvu faktoriaal.
     System.out.println("Factorial of " + number + " on " + fakt (arv));
     }
    }

Factorial programm Pythonis

Pythonis koodi kirjutamine on ülilihtne ja lõbus. Kuna see on tõlgendatud platvormist sõltumatu keel, ei pea te muutujate andmetüüpe deklareerima. Samuti väldite sellise lihtsa programmi jaoks klasside deklareerimist ja teekide importimist. Mänguväljak on kodeerimise alustamiseks valmis.

Süntaks on lihtsam, väikese koodipikkusega, kuid selle käivitamine võtab veidi rohkem aega kui teiste keelte puhul. Pythonis rekursiooni abil faktoriaalprogrammi saate luua järgmiselt.

  1. Määratlege funktsiooni fakt, mis aktsepteerib argumendina n.
    deffakt(n):
  2. Kirjutage funktsiooni põhitäht, kasutades kui avaldus ja kontrollige selle võrdsust kasutades ==. Kui n võrdub nulliga, tagasta üks.
     kui n == 0:
    tagasi1
  3. Kirjutage üldistatud võrrand ja tagastage korrutis n alamülesande funktsioonikutsega n-1.
    tagasi n * fakt (n-1)
  4. Salvestage number, mille faktoriaali soovite leida, ja kuvage see printimislause abil.
    arv = 5;
    print("Factorial of", number, "on", fakt (arv))

Rekursiooni rakendusi on palju

Rekursioon on tõhus viis probleemide lahendamiseks. See on tehisintellekti tuum ja seda kasutatakse reaalses maailmas mõistatusmängudes, nagu male või Sudoku.

See on ka võimas meetod andmestruktuuride (nt puu) või sortimisalgoritmide (nt Kiirsortimine ja Ühenda sortimine) sortimiseks. Samuti võite kasutada rekursiooni otsingualgoritmides, nagu binaarne otsing, matemaatilistes avaldistes (nt Fibonacci seerias) ja mujal.