求大数阶乘的算法

介绍一种非常规方法
服务器君一共花费了516.788 ms进行了4次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

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

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

unsigned long factorial( int n )
{
	if( n == 0 )
		return 1;
	unsigned long result = 1;
	for( int i = 1; i < n + 1; ++i )
	{
		result *= i;
	}
	return result;
}

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类型的整数也无法保存计算结果。那么,这时候,我们应该怎么办呢? 现在,我们就要介绍一种计算方法,该方法的主要思路如下:

  1. 开辟一个大小为10000或更大的整形数组;
  2. 数组的每一个元素只保存计算结果中的一位数字,数组索引最小的元素对应计算结果的最小位,依次类推;
  3. 在计算中,将1-n中的每一个数字都与数组中的每一个数相乘,将与某元素的乘积仍保存在该元素中;
  4. 在1-n中的每个数字与所有元素做完乘积之后,依次每一个元素中的数字是否超过10(或者radix),若超过,则向前进位;

按照上面所描述的算法,我们在这里利用C++语言进行了实现:

#include <iostream>
#include <sstream>

#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,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/271

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《人月神话》 弗雷德里克·布鲁克斯 (作者), 汪颖 (译者)

《人月神话》原文:The Mythical Man-Month: The Essays on Software Engineering, 2nd ed.在软件领域,很少能有像《人月神话》一样具有深远影响力并且畅销不衰的著作。Brooks博士为人们管理复杂项目提供了最具洞察力的见解。既有很多发人深省的观点,又有大量软件工程的实践。本书内容来自Brooks博士在IBM公司System/360家族和OS/360中的项目管理经验。该书英文原版一经面世,即引起业内人士的强烈反响,后又译为德、法、日、俄中等多种语言,全球销量数百万册。确立了其在行业内的经典地位。

更多计算机宝库...