Factorialul unui număr este un concept matematic important. Îl puteți folosi pentru a efectua permutări și combinații, pentru a scrie expresii exponențiale și logaritmice și pentru a calcula probabilitatea.

Îl folosești pentru a găsi numărul de moduri diferite în care poți proiecta un aranjament de scaune sau pentru a alege tricouri pentru vacanța ta în Maldive. Dar cum poți calcula factorialul unui număr?

Care este factorialul unui număr?

Factorialul unui număr pozitiv este produsul tuturor numerelor întregi pozitive mai mici sau egale cu valoarea numărului însuși. Un număr urmat de un semn de exclamare (!) indică factorialul unui număr. Reprezentați factorialul de cinci ca 5! si calculeaza-l ca:

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

Un alt mod de a-l vizualiza este:

5! = 5 * 4! unde 4! = 4 * 3!, 3! = 3 * 2! si tot asa pana obtineti 1! = 1 * 0! care este 1.

Veți folosi acest concept pentru a construi programul nostru factorial folosind un concept popular numit recursivitate.

Ce este recursiunea?

Recursiunea este un proces în care o funcție se autoinvocă. Unul dintre principalele avantaje ale acestui proces este că împarte o problemă mai mare în bucăți mai mici. Acest lucru face problema mai ușor de rezolvat.

instagram viewer

Puteți folosi recursiunea pentru a rezolva problemele adecvate în trei pași simpli:

  1. Găsiți cazul de bază: Dacă o funcție se numește întotdeauna pe sine, procesul va fi infinit. Pentru a preveni acest lucru, definiți un caz de bază care să devină punctul de oprire logic pentru funcția dvs. De exemplu, într-un program factorial, opriți calculul la zero. Acesta devine cazul de bază al problemei.
  2. Găsiți relația dintre problemă și subprobleme: Împărțiți problema mai mare într-o subproblemă. De exemplu, problema este de a găsi factorialul de cinci. Să presupunem că aveți răspunsul factorial de patru, adică 24. Cum veți obține factorialul de cinci folosind 24? Înmulțindu-se cinci în ea. Aceasta este relația dintre problemă și subproblemă.
  3. Generalizați relația găsită la Pasul 2: Acum că aveți relația, generalizați-o în termeni de n. Deci, factorialul unui număr n este produsul lui n și factorialul lui n-1.

Puteți folosi acest concept pentru a găsiți suma a n numere naturale, calculați GCD, LCM, seria Fibonacci și verificați numerele prime.

Pseudocod pentru funcția factorială utilizând recursiunea

Aceasta este cum folosești recursiunea și scrieți pseudocodul pentru a vă construi programul în orice limbă. Cu diferite limbi, sintaxa și execuția se schimbă, dar logica rămâne intactă.

funcţieFapt(n)
 Dacă n == 0 apoi // caz de baza
Întoarcere1
Întoarcere n * Fapt apel (n - 1) // relaţie generalizată

Program factorial în C

C a fost primul limbaj de programare de nivel înalt, independent de platformă. Are o sintaxă strictă, diferențiază majuscule și minuscule și execută codul cu cea mai rapidă viteză. Este un limbaj de programare procedural și, prin urmare, declarați orice funcție pe deasupra principal funcţie. Iată cum puteți construi programul factorial folosind recursiunea în limbajul C:

Puteți găsi întregul cod sursă al programului factorial folosind recursiunea în C, Java și Python în aceasta Depozitul GitHub.

  1. Importați fișierul antet de ieșire standard de intrare pentru a afișa rezultatul pe ecran.
    #include <stdio.h>
  2. Definiți funcția fapt și luați număr întreg n ca argument.
    intfapt(int n){
  3. Scrieți cazul de bază al funcției folosind dacă declarație și verificați egalitatea acesteia folosind ==. Dacă n este egal cu zero, returnează unul.
     dacă (n == 0)
    întoarcere1;
  4. Scrieți ecuația generalizată și returnați produsul lui n cu un apel de funcție de subproblemă n-1.
    întoarcere n * fapt (n - 1);
    }
  5. Declarați funcția principală și inițializați o variabilă de tip întreg pentru a stoca numărul al cărui factorial doriți să îl găsiți.
    intprincipal(){
    int num = 5;
  6. Afișați factorialul numărului folosind printf() funcţie. %d este specificatorul de format zecimal. Utilizați fiecare dintre specificatorii de format pentru a-l înlocui cu numărul al cărui factori doriți să găsiți și obțineți rezultatul apelând funcția.
     printf("Factorialul lui %d este %d", num, fapt (num));
    întoarcere0;
    }

Program factorial în Java

Java este un limbaj de programare compilat și este independent de platformă. Stocați tot codul în interiorul a clasă iar execuţia începe de la principal funcţie. Este sensibil la majuscule și cu sintaxa strictă. Codul este puțin mai lung, dar mai rapid în comparație cu Python. Iată cum puteți construi programul factorial folosind recursiunea în Java:

  1. Definiți clasa principală.
    clasăPrincipal{
  2. Definiți o funcție statică cu tipul returnat int care acceptă o variabilă n de tip întreg. Ați declarat o metodă statică, deoarece metoda principală în Java este, de asemenea, declarată ca fiind statică. În plus, nu puteți apela o metodă non-statică dintr-o instanță statică.
    staticintfapt(int n){
  3. Scrieți cazul de bază al funcției folosind dacă declarație și verificați egalitatea acesteia folosind ==. Dacă n este egal cu zero, returnează unul.
     dacă (n == 0)
    întoarcere1;
  4. Scrieți ecuația generalizată și returnați produsul lui n cu un apel de funcție de subproblemă n-1.
    întoarcere n * fapt (n - 1);
     }
  5. Declarați funcția principală în Java. Declarați modificatorul de acces ca public, deci poate fi accesibil prin toate celelalte clase și metode. Declari funcția principală ca static astfel încât compilatorul să îl poată invoca fără a instanția clasa. Tipul de returnare este gol, și acceptă argumente de tip Şir. Stocați numărul al cărui factori doriți să îl găsiți.
    publicstaticgolprincipal(Șir[] argumente){
    int num = 5;
  6. Folosește println() metoda, o instanță a PrintStream clasa, definită în Sistem clasă pentru a afișa factorialul numărului.
     System.out.println("Factorial de " + num + " este " + fapt (num));
     }
    }

Program factorial în Python

Scrierea codului în Python este foarte ușor și distractiv. Deoarece este un limbaj interpretat independent de platformă, nu trebuie să declarați tipul de date al variabilelor. De asemenea, evitați să declarați clase și să importați biblioteci pentru un program atât de simplu. Locul de joacă este gata pentru ca tu să începi codificarea.

Sintaxa este mai ușoară, cu o lungime mică a codului, dar durează puțin mai mult timp pentru a se executa decât în ​​celelalte limbi. Iată cum puteți construi programul factorial folosind recursiunea în Python:

  1. Definiți fapta funcției care acceptă ca argument n.
    deffapt(n):
  2. Scrieți cazul de bază al funcției folosind dacă declarație și verificați egalitatea acesteia folosind ==. Dacă n este egal cu zero, returnează unul.
     dacă n == 0:
    întoarcere1
  3. Scrieți ecuația generalizată și returnați produsul lui n cu un apel de funcție de subproblemă n-1.
    întoarcere n * fapt (n-1)
  4. Stocați numărul al cărui factori doriți să găsiți și afișați-l folosind instrucțiunea print.
    num = 5;
    imprimare("Factorial de", num, "este", fapt (num))

Există multe aplicații ale recursiunii

Recursiunea este o modalitate eficientă de rezolvare a problemelor. Este esențialul inteligenței artificiale și are utilizări în lumea reală în jocuri puzzle, cum ar fi șah sau Sudoku.

Este, de asemenea, o metodă puternică de sortare a structurilor de date, cum ar fi Tree sau algoritmi de sortare, cum ar fi Sortare rapidă și Sortare prin îmbinare. De asemenea, puteți utiliza recursiunea în algoritmi de căutare precum căutarea binară, expresii matematice precum seria Fibonacci și multe altele.