柚子快報(bào)激活碼778899分享:算法 階乘 (C++)
柚子快報(bào)激活碼778899分享:算法 階乘 (C++)
階乘(factorial)
又稱為階乘函數(shù),是數(shù)學(xué)中的一個(gè)重要概念。它表示一個(gè)正整數(shù)n與小于或等于它的所有正整數(shù)的乘積,通常以符號(hào)“n!”表示。在數(shù)學(xué)領(lǐng)域中,階乘是一個(gè)廣泛應(yīng)用的概念,常常出現(xiàn)在排列組合、概率統(tǒng)計(jì)、數(shù)論等諸多領(lǐng)域中。
目錄
階乘(factorial)
1. 階乘的定義
2. 階乘的性質(zhì)和應(yīng)用
3. 階乘的計(jì)算方法
(1) 用遞歸方式計(jì)算階乘:
(2) 用循環(huán)方式計(jì)算階乘:
(3) 用高精度算法計(jì)算階乘:
4. [拓展] 雙階乘的概念
5. 結(jié)束語(yǔ)
1. 階乘的定義
一個(gè)正整數(shù)的階乘(factorial)是所有小于及等于該數(shù)的正整數(shù)的積,并且0的階乘為1。自然數(shù)n的階乘寫(xiě)作 n! 。
1808年,基斯頓·卡曼 引進(jìn)這個(gè)表示法,即 n! = 1×2×3×...×(n-1)×n 。
階乘的定義非常簡(jiǎn)單,即n的階乘 (n!) 等于小于或等于n的所有正整數(shù)的乘積。
2. 階乘的性質(zhì)和應(yīng)用
階乘具有以下幾個(gè)性質(zhì):
????????(1):0的階乘為1(0! = 1)。
????????(2):負(fù)整數(shù)以及分?jǐn)?shù)沒(méi)有階乘的定義。
????????(3):階乘增長(zhǎng)非???,隨著n的增大,n!的值急劇增加。
階乘在排列組合、概率統(tǒng)計(jì)、數(shù)論等領(lǐng)域有廣泛的應(yīng)用。
在排列組合中,階乘用于計(jì)算有序的元素排列的方式數(shù)量。
例如,從n個(gè)元素中選取m個(gè)元素進(jìn)行排列,可表示為? n!/(n-m)!? ,即從n個(gè)元素中任選m個(gè)元素進(jìn)行排列的不同方式數(shù)量。
從n個(gè)元素中選取m個(gè)元素進(jìn)行組合,可表示為? n!/(n-m)!/m!? ,即將其進(jìn)行排列的結(jié)果除以m的階乘,表示n個(gè)元素中任選m個(gè)元素進(jìn)行組合的不同方式數(shù)量。
在概率統(tǒng)計(jì)中,階乘用于計(jì)算排列組合方式的概率。例如,在一副撲克牌中,從中抽取5張牌的順序不同的可能性就可以表示為5!。
在數(shù)論中,階乘與素?cái)?shù)、除法取模運(yùn)算等概念有密切關(guān)聯(lián)。例如,通過(guò)階乘可以證明除法取模定理:對(duì)于任意的正整數(shù)n和素?cái)?shù)p,n!模p的結(jié)果等于0。
3. 階乘的計(jì)算方法
計(jì)算階乘的方法可以通過(guò)遞歸或循環(huán)來(lái)實(shí)現(xiàn)。遞歸是一種將大問(wèn)題分解為小問(wèn)題的方法,通過(guò)反復(fù)調(diào)用自身來(lái)解決問(wèn)題。用遞歸計(jì)算階乘的公式為:? ? 0! = 1 ,? n!?= n×(n-1)!? ?。
(1) 用遞歸方式計(jì)算階乘:
#include
using namespace std;
int fact(int n){
if(n==0) return 1;
return n * fact(n-1);
}
int main(){
int n;
scanf("%lld",&n);
printf("%d",fact(n));
return 0;
}
另一種常見(jiàn)的計(jì)算階乘的方法是使用循環(huán),從1到n逐步累乘得到階乘的結(jié)果。
(2) 用循環(huán)方式計(jì)算階乘:
#include
using namespace std;
int main(){
int n,s=1;
scanf("%lld",&n);
for(int i=1;i<=n;i++){
s*=i;
}
printf("%d",s);
return 0;
}
?但是,由于階乘的增長(zhǎng)特別快,13的階乘(?6227020800 ) 就會(huì)超出 C++ 中int的數(shù)據(jù)范圍(2147483647),?而21的階乘(?51090942171709440000 ) 就會(huì)超出 C++ 中l(wèi)ong long的數(shù)據(jù)范圍(9223372036854775807), 具體數(shù)值可以看這篇博客?[階乘表 1-100階乘] , 所以,使用普通的數(shù)據(jù)類型無(wú)法計(jì)算較大數(shù)的階乘。
這里就需要用到高精度算法(High Accuracy Algorithm)了。
(3) 用高精度算法計(jì)算階乘:
#include
using namespace std;
const int N=10000;
int a[N];
int main(){
a[1]=1;
int c=1,t=0,xxx,n;
scanf("%d",&n);
if(n<2){
printf("%d",1);
return 0;
}
for(int i=2;i<=n;i++){
for(int j=1;j<=c;j++){
xxx=a[j]*i+t;
a[j]=xxx%10;
t=xxx/10;
}while(t){
c++;
a[c]=t%10;
t/=10;
}
}
for(int i=c;i>0;i--)
printf("%d",a[i]);
return 0;
}
4. [拓展] 雙階乘的概念
雙階乘(即二次階乘)是在階乘的基礎(chǔ)上的一個(gè)擴(kuò)展概念。雙階乘表示對(duì)小于等于正整數(shù)n的所有奇數(shù)進(jìn)行乘積。通常用符號(hào)“ n!! ”表示。
雙階乘的計(jì)算方法與階乘類似,但考慮的元素不同,雙階乘只考慮奇數(shù)。通過(guò)遞歸或循環(huán),將n的階乘的奇數(shù)部分相乘得到雙階乘的結(jié)果。
雙階乘有其特殊的應(yīng)用場(chǎng)景。例如,在組合數(shù)學(xué)中,雙階乘被用于計(jì)算排列組合的可能性。特別地,雙階乘在計(jì)算卡特蘭數(shù)(Catalan number)時(shí)起到重要作用,卡特蘭數(shù)表示在特定條件下有效的排列組合的數(shù)量。
5. 結(jié)束語(yǔ)
階乘是數(shù)學(xué)中一個(gè)常用的概念,其定義是將一個(gè)正整數(shù)與小于或等于它的所有正整數(shù)相乘。階乘的計(jì)算可以通過(guò)遞歸或循環(huán)來(lái)實(shí)現(xiàn)。階乘具有多種性質(zhì)和應(yīng)用,常用于排列組合、概率統(tǒng)計(jì)和數(shù)論中。雙階乘是對(duì)小于等于正整數(shù)n的所有奇數(shù)進(jìn)行乘積,其計(jì)算方法和階乘類似。雙階乘在計(jì)算卡特蘭數(shù)等應(yīng)用中有特殊的作用。
今天的內(nèi)容就到這里,創(chuàng)作不易,請(qǐng)大家多多支持博主!? [?點(diǎn)贊+收藏+關(guān)注 ]
柚子快報(bào)激活碼778899分享:算法 階乘 (C++)
參考閱讀
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理,出于傳遞更多信息之目的,不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明,如有侵權(quán),聯(lián)系刪除。