El factorial d’un enter positiu és el producte d’un enter i tots els enters inferiors, és a dir, el factorial del nombre n (representat per n!) Estaria donat per
n! = 1 * 2 * 3 * 4 *. . . . . * n
El factorial de 0 es defineix com a 1 i no es defineix per als enters negatius. Hi ha diverses maneres de trobar-lo que s’enumeren a continuació.
- Programa Factorial en Doutilitzant el bucle For
- Utilització del programa factorialFuncions
- Programa Factorialmitjançant la recursió
Comencem.
Ús factorial per a bucle
És la forma més senzilla i senzilla de trobar el factorial d’un nombre. Visiteu primer el codi -
#include int main () {int I, num, fact = 1 // definint factorial com a 1 ja que el valor mínim és 1 printf ('Introduïu un número per calcular el seu factorial') scanf ('% d', & num) si (num<0) //if the input is a negative integer { printf (“Factorial is not defined for negative numbers.”) } else { for(i=1i0, therefore fact value remains 1 { fact = fact * i // keeps on multiplying and storing in the value of factorial till the input integer is reached } printf(“Factorial of %d = %dn”, num, fact) } return 0 //since we have defined the main() method with a return value of integer type }Sortida-
Factorial de 5 = 120
Explicació -
El nombre del factorial que es troba es pren com a entrada i s’emmagatzema en una variable i es comprova si és negatiu o no. Si l'enter introduït és negatiu, es mostrarà el missatge adequat. El valor de factorial està predefinit a 1, ja que el seu valor mínim és 1. El bucle for s'executa per a enters enters positius (excepte 0 per a la qual la condició de prova és falsa i, per tant, el fet continua sent nul). Al bucle for, el valor de factorial es multiplica amb cada enter i s'emmagatzema successivament fins que s'arriba al nombre d'entrada. Per exemple, per a l'entrada = 5, el flux va a bucle i es realitzen els següents passos:
fet = 1, i = 1 -> fet = 1 * 1 = 1 -> i = 2
fet = 1, i = 2 -> fet = 1 * 2 = 2 -> i = 3
fet = 2, i = 3 -> fet = 2 * 3 = 6 -> i = 4
fet = 6, i = 4 -> fet = 6 * 4 = 24 -> i = 5
fet = 24, i = 5 -> fet = 24 * 5 = 120 -> i = 6
Ara 6> 5, per tant, la condició de prova es fa falsa i el bucle s’acaba. Es mostra el valor de factorial.
Funcions d'ús factorial
Aquest enfocament es coneix com un enfocament modular i s’ha de seguir per a la programació, ja que és força eficient. Un dels seus avantatges és que quan hem de fer canvis al codi, en lloc de canviar el codi complet, només podem modificar la funció en qüestió. A continuació es mostra el codi per trobar la factorial d’un número mitjançant aquest enfocament
#include factorial llarg (int num) // funció per al càlcul factorial que pren un valor enter com a paràmetre i retorna un valor de tipus int {int i long fact = 1 for (i = 1 i<= num i++) fact = fact * i return fact //returns to function call } int main() //execution begins from main() method { int num printf('Enter a number to calculate its factorialn') scanf('%d', &num) if(num<0) //if the input is a negative integer { printf('Factorial is not defined for negative numbers.') } printf('Factorial of %d = %dn', num, factorial(num)) //call to factorial function passing the input as parameter return 0 }
Sortida - Factorial de 5 = 120
Explicació-
La lògica del programa és la mateixa excepte que s’utilitza una funció diferent per calcular el factorial i retornar el valor al mètode principal des d’on comença l’execució.
Factorial mitjançant recursivitat
La recursió és el procés en què una funció s'anomena a si mateixa i la funció corresponent s'anomena funció recursiva. Consta de dues parts: una condició base i una trucada recursiva. La solució a la condició base es proporciona mentre que la solució al valor més gran es pot resoldre convertint-la a valors més petits fins que s’arriba i s’utilitza la solució base.
A continuació es mostra el codi per trobar factorials mitjançant la recursió: -
#include int fact (int) // function prototype int main () {int num printf ('Introduïu el número el factorial del qual s'ha de trobar:') scanf ('% d', & num) if (num<0) { printf('ERROR. Factorial is not defined for negative integers') } printf('Factorial of %d is %d', num, fact(num)) //first call is made return 0 } int fact(int num) { if(num==0) //base condition { return 1 } else{ return(num*fact(num-1)) //recursive call } } Sortida - Factorial de 5 = 120
Explicació -Suposem que l'usuari introdueix 5 com a entrada, i al mètode main () el valor de num és 5. A mesura que el flux va a la sentència printf (línia 12) es fa una funció de crida al fet (5). Ara bé, de fet (5) num és 5 que no és igual a 0, per tant, el flux va a la sentència else on a la declaració de retorn es fa una trucada recursiva i es fa el fet (4). El procés es repeteix fins que s’arriba a la condició base, és a dir, s’arriba a num = 0 i es torna 1. Ara el flux passa al fet (1) des d'on es retorna 1 (pel que fa al fet (1) num = 1) * 1 (valor retornat del fet (0)). Aquest procés es repeteix fins a obtenir el valor requerit.
Complexitat temporal i espacial: iteració V / S de recursió
Per recursivitat
Respecte complexitat horària , sabem que el factorial 0 és l'única comparació. Per tant, T (0) = 1. Per al factorial de qualsevol altre nombre, el procés implica una comparació, una multiplicació, una resta i una trucada de funció. Per tant
T (n) = T (n-1) +3
= T (n-2) +6
= T (n-3) +9
= & hellip.
= T (n-k) + 3k
Com que sabem T (0) = 1 i per a k = n, (n-k) = 0
Per tant T (n) = T (0) + 3n
= 1 + 3n
Per tant, la complexitat temporal del codi és O (n).
Respecte complexitat espacial, es crea una pila per a cada trucada que es mantindrà fins que el seu valor siguicalculat i retornat. Per exemple, per a n = 5 s’hauran de mantenir les piles següents
f (5) -> f (4) -> f (3) -> f (2) -> f (1) -> f (0)
Com podem veure, s’hauran de mantenir 5 piles fins que s’arribi a una trucada a f (0) el valor de la qual siguiconegut i és retornat. Per tant, per a n factorials, s’hauran de mantenir n piles. Així, la complexitat de l'espaiés O (n). També és evident per les imatges anteriors que per a n = 5, hauran de ser 5 pilesmantingut. Per tant, per a n factorials, s’hauran de mantenir n piles. Per tant, la complexitat de l'espai és O (n).
trobar la longitud de la matriu javascript
Per a la iteració
Respecte complexitat temporal, hi ha n iteracions dins del bucle, per tant la complexitat temporal és O (n).
Respecte complexitat espacial, per a la solució iterativa només cal mantenir una pila i s'utilitza una variable sencera. Per tant, la complexitat de l’espai és O (1).
Això és tot per a aquest article. Espero que hagueu entès el concepte del programa factorial en Do juntament amb les complexitats temporals.
Si teniu alguna pregunta, no dubteu a fer-vos totes les vostres preguntes a la secció de comentaris del programa factorial en C i el nostre equip estarà encantat de respondre-us.