大整数阶乘的算法思路

听说中科院软件所09年复试的笔试题就是这个，打算自己写写。

这里的大整数指大于500以上的整数，当然更大也可以。由于整数阶乘递增的很快，远大于指数式递增，对于小整数，比如20，30左右，可以直接使用比如递归的方式进行，这很基本。

但是当整数较大时，阶乘的结果很大，远非一个int或者long就能存的下的，比如1000的阶乘结果有上千位。

所以大整数阶乘设计的关键点就是存储大整数，当选择了存储大整数，那么整数的乘法运算也不能再依靠*了，所以还要重新设计大整数的乘法运算。

上面是我的设计思路。网上找过相关的文章，有高手以4行代码完成了该算法，确实佩服！当然这涉及了算法的优化，不管那么多了，这里要的就是以尽量清晰地思路快速设计该算法，这是使用了STL标准库的容器。

下面是我的算法代码，直接贴这里了，注意看相关的注释：

#include <iostream>
#include <vector>

using namespace std;

// 传入整数：int，和整数-1的阶乘结果，进行相乘的结果
// 结构依然存储到容器中
void Calc(int num,vector<int> &calcresult)
{
	vector<int> tempnum;
	vector<int> 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;

			// 保存当前位
			if((i+j)<rest.size())
			{
				// 临时结果中有对应位存在，则直接更新
				rest[i+j] += (res + carry) % 10;
			}
			else
			{
				// 没有对应位则需要添加
				rest.push_back((res+carry)%10);
			}
			// 有进位，则更新进位
			carry = (res + carry) / 10;
		}
		// 如果计算之后还有最高位的进位，那么则直接添加进去
		if(carry)
		{
			// 保存当前位
			if((i+j)<rest.size())
			{
				// 临时结果中有对应位存在，则直接更新
				rest[i+j] += carry;
			}
			else
			{
				// 没有对应位则需要添加
				rest.push_back(carry);
			}
		}
	}
	// 上述计算之后，会出现有些位的数字超过了10，那是因为在处理每一位运算结果之后
	// 相加时地位向高位可能存在进位，上面没有考虑，所以需要进行调整
	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;
			}
		}
	}
	// 将计算结果存储到原来的容器中
	calcresult.clear();
	for(i = 0;i < rest.size();++i)
	{
		calcresult.push_back(rest[i]);
	}
}
int main()
{
	int num = 0;
	vector<int> calcresult;
	// 将初值1赋进去
	calcresult.push_back(1);
	// 获取欲求阶乘的整数
	cout<<"输入欲求阶乘的整数："<<endl;
	cin>>num;

	for(int i = 0;i < num;++i)
	{
		Calc(i+1,calcresult);
	}
	// 输出计算结果
	cout<<num<<"的阶乘："<<endl;
	for(unsigned int i = calcresult.size();i > 0 ;--i)
	{
		cout<<calcresult[i-1];
	}
	cout<<endl;

	return 0;
}