php专区

在很多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 < dgts; i++ )
	{
		result[i] += carry_value;
		carry_value = ( result[i] < RADIX ) ? 0 : ( result[i] / RADIX );
		result[i] -= carry_value * RADIX;
	}

	//处理最后一位：
	//若需进位，则循环进位，直到不需进位为止
	result[i] += carry_value;
	while( result[i] >= RADIX && i < MAXDIGIT )
	{
		carry_value = result[i] / RADIX;
		result[i] -= carry_value * RADIX;
		result[++i] = carry_value;
		++dgts;
	}
	
	if( 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 < n+1; ++i )
		{
			for( int j = 0; j <= digits; ++j )
			{
	           	result[j] *= i;
			}
			if( !carry( result, digits ) )
           		break;
		}
	
		return digits >= MAXDIGIT ? -1 : digits;
	}
	
	void print( s_int result[], const int &digits )
	{
		if( digits < 10 )
			for( int i = digits; i >= 0; i-- )
				cout << result[i];
		else
		{
			cout << result[digits] <<".";
			for( int i = digits -1; i >= 0; i-- )
				cout << result[i];
			cout << "E" << digits;
		}
		cout << endl;
	}
	
	int main(void)
	{
		s_int result[MAXDIGIT];
		int n;
		int digits;
	
		cout << "Input the value of n: ";
		cin >> n;
	 
		if( n < 0 )
		{
			cout << "Error: A positive integer is need!" << endl;
			return 0;
		}
	
		if( (digits = factorial(n, result)) == -1 )
		{
			cout << "Error: Overflow!" << endl;
			return 0;
		}
		else
		{
			print(result, digits);
			return 0;
		}
	}
												
本文地址：http://www.nowamagic.net/librarys/veda/detail/271，欢迎访问原出处。