求大数阶乘的算法

在很多C/C++的书上，都给出了两种阶乘的计算方法，一种为利用递归进行计算；一种利用阶乘的定义进行计算。下面给出这两种算法的C程序源代码。

1. 利用阶乘的定义进行计算：

unsigned long factorial( int n )
{
	if( n == 0 )
		return 1;
	unsigned long result = 1;
	for( int i = 1; i 
	
	
2. 利用递归进行计算：
	
unsigned long factorial( unsigned long n )
{
	unsigned long result = 0;
	if( n == 0 )
		return 1;
	else
		result = n*factorial( n-1 );
	return result;
}

	
	
但是，由于阶乘的结果随着n的增大将急剧增加。最终导致即使是unsigned long类型的整数也无法保存计算结果。那么，这时候，我们应该怎么办呢？
现在，我们就要介绍一种计算方法，该方法的主要思路如下：

	

		
		
开辟一个大小为10000或更大的整形数组；
		
		
数组的每一个元素只保存计算结果中的一位数字，数组索引最小的元素对应计算结果的最小位，依次类推；
		
		
在计算中，将1-n中的每一个数字都与数组中的每一个数相乘，将与某元素的乘积仍保存在该元素中；
		
		
在1-n中的每个数字与所有元素做完乘积之后，依次每一个元素中的数字是否超过10（或者radix），若超过，则向前进位；
		
	
	
	
按照上面所描述的算法，我们在这里利用C++语言进行了实现：
	
#include 
#include 

#define s_int short int
#define MAXDIGIT 50000
#define RADIX 10
 
using std::cout;
using std::endl;
using std::cin;

//实现进位
bool carry( s_int result[], int &dgts )
{
	int i;
	s_int carry_value = 0;
	for( i = 0; i = RADIX && i = MAXDIGIT )
	return false;
	
	return true;
}

	// The function return the total digits of the result.
	//
	int factorial( int n, s_int result[] )
	{
		memset(result, 0, sizeof(s_int)*MAXDIGIT);
		int digits = 0;
		result[0] = 1;
	
		// 0! = 1
		if( n == 0 ) return 1;
	
		for( int i = 2; i = MAXDIGIT ? -1 : digits;
	}
	
	void print( s_int result[], const int &digits )
	{
		if( digits <10 )
			for( int i = digits; i >= 0; i-- )
				cout <= 0; i-- )
				cout <> n;
	 
		if( n <0 )
		{
			cout <<"Error: A positive integer is need!" <												
本文地址：http://www.nowamagic.net/librarys/veda/detail/271，欢迎访问原出处。