大整數(shù)階乘的算法思路
這里的大整數(shù)指大于500以上的整數(shù)，當(dāng)然更大也可以。由于整數(shù)階乘遞增的很快，遠大于指數(shù)式遞增，對于小整數(shù)，比如20，30左右，可以直接使用比如遞歸的方式進行，這很基本。
但是當(dāng)整數(shù)較大時，階乘的結(jié)果很大，遠非一個int或者long就能存的下的，比如1000的階乘結(jié)果有上千位。
所以大整數(shù)階乘設(shè)計的關(guān)鍵點就是存儲大整數(shù)，當(dāng)選擇了存儲大整數(shù)，那么整數(shù)的乘法運算也不能再依靠*了，所以還要重新設(shè)計大整數(shù)的懲罰運算。
上面是我的設(shè)計思路。網(wǎng)上找過相關(guān)的文章，有高手以4行代碼完成了該算法，確實佩服!當(dāng)然這涉及了算法的優(yōu)化，不管那么多了，這里要的就是以盡量清晰地思路快速設(shè)計該算法，這是使用了STL標(biāo)準(zhǔn)庫的容器。
下面是我的算法代碼，直接貼這里了，注意看相關(guān)的注釋：
#include
#include
using namespace std;
// 傳入整數(shù)：int，和整數(shù)-1的階乘結(jié)果，進行相乘的結(jié)果
// 結(jié)構(gòu)依然存儲到容器中
void Calc(int num,vector &calcresult)
{
vector tempnum;
vector rest;
// 將傳入的int拆分之后保存到容器中
do
{
tempnum.push_back(num % 10);
num = num / 10;
} while (num);
// 將分拆之后的num進行乘法計算
unsigned int i = 0,j = 0;
for(i = 0;i < tempnum.size();++i)
{
int carry = 0;// 存儲每位計算時來自低位的進位
for(j = 0;j < calcresult.size();++j)
{
int bit1 = 0,bit2 = 0,res = 0;
bit1 = calcresult[j];
bit2 = tempnum[i];
res = bit1 * bit2;
// 保存當(dāng)前位
if((i+j)
{
// 臨時結(jié)果中有對應(yīng)位存在，則直接更新
rest[i+j] += (res + carry) % 10;
}
else
{
// 沒有對應(yīng)位則需要添加
rest.push_back((res+carry)%10);
}
// 有進位，則更新進位
carry = (res + carry) / 10;
}
// 如果計算之后還有位的進位，那么則直接添加進去
if(carry)
{
// 保存當(dāng)前位
if((i+j)
{
// 臨時結(jié)果中有對應(yīng)位存在，則直接更新
rest[i+j] += carry;
}
else
{
// 沒有對應(yīng)位則需要添加
rest.push_back(carry);
}
}
}
// 上述計算之后，會出現(xiàn)有些位的數(shù)字超過了10，那是因為在處理每一位運算結(jié)果之后
// 相加時地位向高位可能存在進位，上面沒有考慮，所以需要進行調(diào)整
for(i = 0;i < rest.size();++i)
{
if(rest[i] > 9)
{
if((i+1) != rest.size())
{
// 高位存在，則直接更新高位
rest[i+1] += rest[i] / 10;
rest[i] = rest[i] % 10;
}
else
{
// 高位不存在，則需要插入
rest.push_back(rest[i] / 10);
rest[i] = rest[i] % 10;
}
}
}
// 將計算結(jié)果存儲到原來的容器中
calcresult.clear();
for(i = 0;i < rest.size();++i)
{
calcresult.push_back(rest[i]);
}
}
int main()
{
int num = 0;
vector calcresult;
// 將初值1賦進去
calcresult.push_back(1);
// 獲取欲求階乘的整數(shù)
cout<<"輸入欲求階乘的整數(shù)："<
cin>>num;
for(int i = 0;i < num;++i)
{
Calc(i+1,calcresult);
}
// 輸出計算結(jié)果
cout<
for(unsigned int i = calcresult.size();i > 0 ;--i)
{
cout<
}
cout<
return 0;
}