Aký je faktoriál čísla?
- Faktoriál nezáporného celého čísla je vynásobením všetkých kladných celých čísel menších alebo rovných n. Napríklad faktoriál 6 je 6*5*4*3*2*1, čo je 720.
- Faktoriál je reprezentovaný číslom a ! značka na konci. Je široko používaný v permutáciách a kombináciách na výpočet celkových možných výsledkov. Francúzsky matematik Christian Kramp prvýkrát použil výkričník.
Vytvorme faktoriálny program pomocou rekurzívnych funkcií. Kým sa hodnota nebude rovnať nule, rekurzívna funkcia bude volať sama seba. Faktorial možno vypočítať pomocou nasledujúceho rekurzívneho vzorca.
n! = n * (n – 1)!
n! = 1, ak n = 0 alebo n = 1
Nižšie je uvedená implementácia:
C++
// C++ program to find> // factorial of given number> #include> using> namespace> std;> > // Function to find factorial> // of given number> unsigned>int> factorial(unsigned>int> n)> > >if> (n == 0> > // Driver code> int> main()> {> >int> num = 5;> >cout <<>'Factorial of '> ><< num <<>' is '> << factorial(num) << endl;> >return> 0;> }> // This code is contributed by Shivi_Aggarwal> |
>
zapuzdrenie v jave
>
C
// C program to find factorial of given number> #include> > // function to find factorial of given number> unsigned>int> factorial(unsigned>int> n)> {> >if> (n == 0)> >return> 1;> >return> n * factorial(n - 1);> }> > int> main()> {> >int> num = 5;> >printf>(>'Factorial of %d is %d'>, num, factorial(num));> >return> 0;> }> |
>
>
Java
// Java program to find factorial of given number> class> Test {> >// method to find factorial of given number> >static> int> factorial(>int> n)> >{> >if> (n ==>0>)> >return> 1>;> > >return> n * factorial(n ->1>);> >}> > >// Driver method> >public> static> void> main(String[] args)> >{> >int> num =>5>;> >System.out.println(>'Factorial of '> + num> >+>' is '> + factorial(>5>));> >}> }> |
>
>
Python3
# Python 3 program to find> # factorial of given number> > # Function to find factorial of given number> def> factorial(n):> > >if> n>=>=> 0>:> >return> 1> > >return> n>*> factorial(n>->1>)> > # Driver Code> num>=> 5>;> print>(>'Factorial of'>, num,>'is'>,> factorial(num))> > # This code is contributed by Smitha Dinesh Semwal> |
>
>
C#
// C# program to find factorial> // of given number> using> System;> > class> Test {> >// method to find factorial> >// of given number> >static> int> factorial(>int> n)> >{> >if> (n == 0)> >return> 1;> > >return> n * factorial(n - 1);> >}> > >// Driver method> >public> static> void> Main()> >{> >int> num = 5;> >Console.WriteLine(>'Factorial of '> >+ num +>' is '> + factorial(5));> >}> }> > // This code is contributed by vt_m> |
>
>
PHP
// PHP program to find factorial // of given number // function to find factorial // of given number function factorial($n) { if ($n == 0) return 1; return $n * factorial($n - 1); } // Driver Code $num = 5; echo 'Factorial of ', $num, ' is ', factorial($num); // This code is contributed by m_kit ?>> |
>
>
Javascript
> // Javascript to find factorial> // of given number> > // function to find factorial> // of given number> function> factorial(n) {> >if> (n == 0)>return> 1;> >return> n * factorial(n - 1);> }> > // Driver Code> let num = 5;> document.write(>'Factorial of '> + num +>' is '> + factorial(num));> > // This code is contributed by Saurabh Jaiswal> > > |
>
>Výkon
c# dátum a čas
Factorial of 5 is 120>
Časová zložitosť: O(n)
Pomocný priestor: O(n)
Iteračné riešenie na nájdenie faktoriálu čísla:
Faktorial je možné vypočítať aj iteračne, pretože rekurzia môže byť pre veľké čísla nákladná. Tu sme ukázali iteračný prístup využívajúci slučky for a while.
Prístup 1: Použitie slučky For
Na vyriešenie problému postupujte podľa nasledujúcich krokov:
- Pomocou cyklu for napíšeme program na nájdenie faktoriálu čísla.
- V programe bude použitá celočíselná premenná s hodnotou 1.
- Pri každej iterácii sa hodnota zvýši o 1, kým sa nebude rovnať hodnote zadanej používateľom.
- Faktoriál čísla zadaného používateľom bude konečnou hodnotou v premennej fakt.
Nižšie je uvedená implementácia vyššie uvedeného prístupu:
C++
// C++ program for factorial of a number> #include> using> namespace> std;> > // function to find factorial of given number> unsigned>int> factorial(unsigned>int> n)> {> >int> res = 1, i;> >for> (i = 2; i <= n; i++)> >res *= i;> >return> res;> }> > // Driver code> int> main()> {> >int> num = 5;> >cout <<>'Factorial of '> ><< num <<>' is '> ><< factorial(num) << endl;> >return> 0;> }> > // This code is contributed by Shivi_Aggarwal> |
>
>
C
#include> > // function to find factorial of given number> unsigned>int> factorial(unsigned>int> n)> {> >int> res = 1, i;> >for> (i = 2; i <= n; i++)> >res *= i;> >return> res;> }> > int> main()> {> >int> num = 5;> >printf>(> >'Factorial of %d is %d'>, num, factorial(num));> >return> 0;> }> |
>
>
Java
// Java program to find factorial of given number> class> Test {> > >// Method to find factorial of the given number> >static> int> factorial(>int> n)> >{> >int> res =>1>, i;> >for> (i =>2>; i <= n; i++)> >res *= i;> >return> res;> >}> > >// Driver method> >public> static> void> main(String[] args)> >{> >int> num =>5>;> >System.out.println(> >'Factorial of '> + num> >+>' is '> + factorial(>5>));> >}> }> |
>
>
Python3
# Python 3 program to find> # factorial of given number> > # Function to find factorial of given number> def> factorial(n):> > >res>=> 1> > >for> i>in> range>(>2>, n>+>1>):> >res>*>=> i> >return> res> > # Driver Code> num>=> 5>;> print>(>'Factorial of'>, num,>'is'>,> factorial(num))> > # This code is contributed by Smitha Dinesh Semwal> |
>
>
C#
// C# program to find> // factorial of given number> using> System;> > class> Test {> >// Method to find factorial> >// of given number> >static> int> factorial(>int> n)> >{> >int> res = 1, i;> > >for> (i = 2; i <= n; i++)> >res *= i;> >return> res;> >}> > >// Driver method> >public> static> void> Main()> >{> >int> num = 5;> >Console.WriteLine(> >'Factorial of '> + num> >+>' is '> + factorial(5));> >}> }> > // This code is contributed by vt_m> |
>
>
PHP
// function to find factorial // of given number function factorial( $n) { $res = 1; $i; for ($i = 2; $i <= $n; $i++) $res *= $i; return $res; } // Driver Code $num = 5; echo 'Factorial of ', $num, ' is ', factorial($num); // This code is contributed // by anuj_67. ?>> |
>
>
Javascript
> // JavaScript program to find factorial of given number> > >// Method to find factorial of the given number> >function> factorial(n)> >{> >var> res = 1, i;> >for> (i = 2; i <= n; i++)> >res *= i;> >return> res;> >}> > >// Driver method> > >var> num = 5;> >document.write(>'Factorial of '> + num +>' is '> + factorial(5));> > > // This code is contributed by shivanisinghss2110.> > > |
>
reťazec v poli c
>Výkon
Factorial of 5 is 120>
Časová zložitosť: O(n)
Pomocný priestor: O(1)
Prístup 2: Tento príklad používa cyklus while na implementáciu algoritmu a nájdenie faktoriálneho programu.
C
// C program for factorial of a number> #include> > // function to find factorial of given number> unsigned>int> factorial(unsigned>int> n)> {> >if>(n == 0)> >return> 1;> >int> i = n, fact = 1;> >while> (n / i != n) {> >fact = fact * i;> >i--;> >}> >return> fact;> }> > int> main()> {> >int> num = 5;> >printf>(>'Factorial of %d is %d'>, num, factorial(num));> >return> 0;> }> |
>
>
C++
// C++ program for factorial of a number> #include> using> namespace> std;> > // function to find factorial of given> // number using while loop> unsigned>int> factorial(unsigned>int> n)> {> >if>(n == 0)> >return> 1;> >int> i = n, fact = 1;> >while> (n / i != n) {> >fact = fact * i;> >i--;> >}> >return> fact;> }> > // Driver code> int> main()> {> >int> num = 5;> >cout <<>'Factorial of '> ><< num <<>' is '> ><< factorial(num) << endl;> >return> 0;> }> // This code is contributed by Shivi_Aggarwal> |
>
>
Java
// Java program to find factorial of given number> > class> Test {> > >// Method to find factorial of the given number> >static> int> factorial(>int> n)> >{> >if>(n ==>0>)> >return> 1>;> >int> i = n, fact =>1>;> >while> (n / i != n) {> >fact = fact * i;> >i--;> >}> >return> fact;> >}> > >// Driver method> >public> static> void> main(String[] args)> >{> >int> num =>5>;> >System.out.println(> >'Factorial of '> + num> >+>' is '> + factorial(>5>));> >}> }> |
>
>
Python3
# Python 3 program to find> # factorial of given number> > # Function to find factorial of given number> def> factorial(n):> >if>(n>=>=> 0>):> >return> 1> >i>=> n> >fact>=> 1> > >while>(n>/> i !>=> n):> >fact>=> fact>*> i> >i>->=> 1> > >return> fact> > # Driver Code> num>=> 5>;> print>(>'Factorial of'>, num,>'is'>,> factorial(num))> > # This code is contributed by Smitha Dinesh Semwal> |
>
nudný unikát
>
C#
// C# program to find> // factorial of given number> using> System;> > class> Test {> >// Method to find factorial> >// of given number> >static> int> factorial(>int> n)> >{> >if>(n == 0)> >return> 1;> >int> i = n, fact = 1;> >while> (n / i != n) {> >fact = fact * i;> >i--;> >}> >return> fact;> >}> > >// Driver method> >public> static> void> Main()> >{> >int> num = 5;> >Console.WriteLine(> >'Factorial of '> + num> >+>' is '> + factorial(5));> >}> }> |
>
>
Javascript
> >// JavaScript Program to implement> >// the above approach> >// function to find factorial of given> >// number using while loop> >function> factorial(n) {> >if> (n == 0)> >return> 1;> >let i = n, fact = 1;> >while> (Math.floor(n / i) != n) {> >fact = fact * i;> >i--;> >}> >return> fact;> >}> > >// Driver code> >let num = 5;> >document.write(>'Factorial of '> >+ num +>' is '> >+ factorial(num) +>' '>);> > // This code is contributed by Potta Lokesh> > >> |
>
>Výkon
Factorial of 5 is 120>
Časová zložitosť: O(N)
Pomocný priestor: O(1)
Prístup 3: A ternárny operátor možno chápať ako skratku pre vyhlásenie if... else. Poskytujú sa podmienky spolu s vyhláseniami, ktoré sa majú na ich základe vykonať. Tu je program pre faktoriál pomocou ternárneho operátora.
C++
// C++ program to find factorial of given number> #include> using> namespace> std;> > int> factorial(>int> n)> > >// single line to find factorial> >return> (n == 1> > // Driver Code> int> main()> {> >int> num = 5;> >cout <<>'Factorial of '> << num <<>' is '><< factorial(num);> >return> 0;> }> > // This code is contributed by shivanisinghss2110> |
>
>
C
// C++ program to find factorial of given number> #include> > int> factorial(>int> n)> n == 0) ? 1 : n * factorial(n - 1);> > > // Driver Code> int> main()> {> >int> num = 5;> >printf>(>'Factorial of %d is %d'>, num, factorial(num));> >return> 0;> }> > // This code is contributed by Rithika palaniswamy.> |
>
>
Java
// Java program to find factorial> // of given number> class> Factorial {> > >int> factorial(>int> n)> > n ==>0>) ?>1> : n * factorial(n ->1>);> >> > >// Driver Code> >public> static> void> main(String args[])> >{> >Factorial obj =>new> Factorial();> >int> num =>5>;> >System.out.println(> >'Factorial of '> + num> >+>' is '> + obj.factorial(num));> >}> }> > // This code is contributed by Anshika Goyal.> |
>
>
Python3
# Python 3 program to find> # factorial of given number> > def> factorial(n):> > ># single line to find factorial> >return> 1> if> (n>=>=> 1> or> n>=>=> 0>)>else> n>*> factorial(n>-> 1>)> > > # Driver Code> num>=> 5> print> (>'Factorial of'>, num,>'is'>,> >factorial(num))> > # This code is contributed> # by Smitha Dinesh Semwal.> |
>
>
C#
// C# program to find factorial> // of the given number> using> System;> > class> Factorial {> > >int> factorial(>int> n)> >> > >// Driver Code> >public> static> void> Main()> >{> >Factorial obj =>new> Factorial();> >int> num = 5;> > >Console.WriteLine(> >'Factorial of '> + num> >+>' is '> + obj.factorial(num));> >}> }> > // This code is contributed by vt_m.> |
>
>
PHP
// PHP program to find factorial // of given number function factorial( $n) $n == 0) ? 1: $n * factorial($n - 1); // Driver Code $num = 5; echo 'Factorial of ', $num, ' is ', factorial($num); // This code is contributed by anuj_67. ?>> |
>
>
Javascript
> > // JavaScript program to find factorial of given number> function> factorial(n)> > > // Driver Code> > >var> num = 5;> >document.write(>'Factorial of '> +num +>' is '> + factorial(num));> > // This code is contributed by shivanisinghss2110.> > > |
>
>Výkon
testovanie a typy softvéru
Factorial of 5 is 120>
Časová zložitosť: O(n)
Pomocný priestor: O(n)
Problémy pri písaní kódu faktoriálu
Keď sa hodnota n zmení o 1, hodnota faktoriálu sa zvýši o n. Takže premenná uchovávajúca hodnotu faktoriálu by mala mať veľkú veľkosť. Nasleduje hodnota n, ktorej faktoriál môže byť uložený v príslušnej veľkosti.
1. celé číslo –> n<=12
2. long long int –> n<=19
Z vyššie uvedených údajov môžeme vidieť, že je možné vypočítať veľmi malú hodnotu n kvôli rýchlejšiemu rastu faktoriálnej funkcie. Môžeme však nájsť mod hodnotu faktoriálu väčších hodnôt tak, že v každom kroku použijeme mod.
Vyššie uvedené riešenie spôsobuje pretečenie pri veľkých počtoch. Riešenie, ktoré funguje pre veľké čísla, nájdete v faktoriáli veľkého čísla.
Ak nájdete nejakú chybu vo vyššie uvedenom kóde/algoritme, napíšte komentáre alebo nájdite iné spôsoby riešenia rovnakého problému.