Faktoriel števila je pomemben matematični koncept. Uporabite ga lahko za izvajanje permutacij in kombinacij, pisanje eksponentnih in logaritemskih izrazov ter računanje verjetnosti.

Z njim poiščete različne načine za oblikovanje sedežnega reda ali izberete majice za počitnice na Maldivih. Toda kako lahko izračunate faktorijel števila?

Kaj je faktoriel števila?

Faktoriel pozitivnega števila je produkt vseh pozitivnih celih števil, manjših ali enakih vrednosti samega števila. Število, ki mu sledi klicaj(!), označuje faktoriel števila. Faktoriel pet predstavljate kot 5! in izračunajte kot:

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

Drug način za vizualizacijo je:

5! = 5 * 4! kje 4! = 4 * 3!, 3! = 3 * 2! in tako naprej, dokler ne dobite 1! = 1 * 0! kar je 1.

Ta koncept boste uporabili za izdelavo našega faktorialnega programa z uporabo priljubljenega koncepta, imenovanega rekurzija.

Kaj je rekurzija?

Rekurzija je proces, v katerem funkcija kliče samo sebe. Ena od glavnih prednosti tega postopka je, da večji problem razdeli na manjše dele. Tako je težavo lažje rešiti.

instagram viewer

Z rekurzijo lahko rešite ustrezne probleme v treh preprostih korakih:

  1. Poiščite osnovni primer: Če funkcija vedno kliče samo sebe, bo proces neskončen. Če želite preprečiti, da bi se to zgodilo, definirajte osnovni primer, ki postane logična točka ustavitve vaše funkcije. Na primer, v faktorskem programu ustavite izračun na nič. To postane osnovni primer težave.
  2. Poiščite povezavo med problemom in podproblemi: Razčlenite večji problem na podproblem. Težava je na primer najti faktoriel petice. Predpostavimo, da imate odgovor faktorial štiri, to je 24. Kako boste dobili faktoriel pet z uporabo 24? Tako, da vanj pomnoži pet samega sebe. To je razmerje med problemom in podproblemom.
  3. Posplošite razmerje, ki ga najdete v 2. koraku: Zdaj, ko imate relacijo, jo posplošite glede na n. Faktoriel števila n je torej produkt n in faktoriela n-1.

Ta koncept lahko uporabite za poišči vsoto n naravnih števil, izračunaj GCD, LCM, Fibonaccijevo vrsto in preveri praštevila.

Psevdo koda za faktorialno funkcijo z uporabo rekurzije

To je kako uporabljate rekurzijo in napišite psevdo kodo za izdelavo svojega programa v katerem koli jeziku. Z različnimi jeziki se sintaksa in izvedba spremenita, vendar logika ostane nedotaknjena.

funkcijoDejstvo(n)
 Če je n == 0 potem // osnovni primer
Vrnitev1
Vrnitev n * Dejstvo klica (n - 1) // posplošeno razmerje

Faktorski program v C

C je bil prvi programski jezik na visoki ravni, od platforme neodvisen. Ima strogo sintakso, razlikuje med velikimi in malimi črkami in izvaja kodo z največjo hitrostjo. Je proceduralni programski jezik in zato deklarirate katero koli funkcijo na vrhu glavni funkcijo. Tukaj je opisano, kako lahko zgradite faktorski program z uporabo rekurzije v jeziku C:

Celotno izvorno kodo faktorialnega programa z uporabo rekurzije v C, Javi in ​​Pythonu najdete v tem Repozitorij GitHub.

  1. Uvozite standardno vhodno izhodno datoteko glave za prikaz izhoda na zaslonu.
    #vključi <stdio.h>
  2. Določite funkcijo dejstvo in vzemite celo število n kot argument.
    intdejstvo(int n){
  3. Zapišite osnovni primer funkcije z uporabo če izjavo in preverite njeno enakost z uporabo ==. Če je n enako nič, vrni 1.
     če (n == 0)
    vrnitev1;
  4. Zapišite posplošeno enačbo in vrnite produkt n s klicem funkcije podproblema n-1.
    vrnitev n * dejstvo (n - 1);
    }
  5. Deklarirajte glavno funkcijo in inicializirajte spremenljivko celoštevilskega tipa, da shranite število, katerega faktorial želite najti.
    intglavni(){
    int št = 5;
  6. Prikažite faktoriel števila z uporabo printf() funkcijo. %d je specifikator decimalne oblike. Uporabite vsakega od določiteljev oblike, da ga nadomestite s številom, katerega faktorial želite najti, in dobite rezultat s klicem funkcije.
     printf("Faktoriel %d je %d", num, fact (num));
    vrnitev0;
    }

Faktorski program v Javi

Java je preveden programski jezik in je neodvisen od platforme. Vso kodo shranite znotraj a razred in izvrševanje se začne od glavni funkcijo. Razlikuje med velikimi in malimi črkami ter je skladenjsko strog. Koda je nekoliko daljša, a hitrejša v primerjavi s Pythonom. Tukaj je opisano, kako lahko zgradite faktorski program z uporabo rekurzije v Javi:

  1. Določite glavni razred.
    razredGlavni{
  2. Definirajte statično funkcijo s povratnim tipom int, ki sprejme spremenljivko n celoštevilskega tipa. Razglasili ste statično metodo kot glavno metodo v Javi, ki je prav tako deklarirana kot statična. Poleg tega ne morete poklicati nestatične metode iz statičnega primerka.
    statičnaintdejstvo(int n){
  3. Zapišite osnovni primer funkcije z uporabo če izjavo in preverite njeno enakost z uporabo ==. Če je n enako nič, vrni 1.
     če (n == 0)
    vrnitev1;
  4. Zapišite posplošeno enačbo in vrnite produkt n s klicem funkcije podproblema n-1.
    vrnitev n * dejstvo (n - 1);
     }
  5. Deklarirajte glavno funkcijo v Javi. Razglasite modifikator dostopa kot javnosti, tako da je lahko dostopen z vsemi drugimi razredi in metodami. Glavno funkcijo deklarirate kot statična tako da ga lahko prevajalnik prikliče brez instanciranja razreda. Vrnitev vrste je praznina, in sprejema argumente tipa Vrvica. Shranite število, katerega faktorial želite najti.
    javnostistatičnaprazninaglavni(Argumenti niza[]){
    int št = 5;
  6. Uporabi println() metoda, primerek PrintStream razred, opredeljen v Sistem razred za prikaz faktoriala števila.
     System.out.println("Faktoriel od " + št. + " je " + dejstvo (št.));
     }
    }

Faktorski program v Pythonu

Pisanje kode v Pythonu je zelo enostavno in zabavno. Ker gre za razložen jezik, neodvisen od platforme, vam ni treba deklarirati vrste podatkov spremenljivk. Prav tako se izognete prijavi razredov in uvozu knjižnic za tako preprost program. Igrišče je pripravljeno, da začnete kodirati.

Sintaksa je enostavnejša, z majhno dolžino kode, vendar zahteva malo več časa za izvedbo kot drugi jeziki. Tukaj je opisano, kako lahko zgradite faktorski program z uporabo rekurzije v Pythonu:

  1. Definirajte funkcijo fact, ki sprejme kot argument n.
    defdejstvo(n):
  2. Zapišite osnovni primer funkcije z uporabo če izjavo in preverite njeno enakost z uporabo ==. Če je n enako nič, vrni 1.
     če je n == 0:
    vrnitev1
  3. Zapišite posplošeno enačbo in vrnite produkt n s klicem funkcije podproblema n-1.
    vrnitev n * dejstvo (n-1)
  4. Shranite število, katerega faktorial želite poiskati, in ga prikažite s stavkom za tiskanje.
    št = 5;
    natisni("Faktoriel od", št., "je", dejstvo (št.))

Obstaja veliko aplikacij rekurzije

Rekurzija je učinkovit način reševanja problemov. Je bistvo umetne inteligence in se uporablja v resničnem svetu v ugankarskih igrah, kot sta šah ali sudoku.

Je tudi zmogljiva metoda za razvrščanje podatkovnih struktur, kot je drevo, ali algoritmov za razvrščanje, kot sta hitro razvrščanje in združevanje. Rekurzijo lahko uporabite tudi pri algoritmih iskanja, kot je binarno iskanje, matematičnih izrazih, kot je Fibonaccijeva vrsta, itd.