[ACM_ZJUT_1382]计算N!（数组模拟超大数运算）

杰拉斯 | 时间：2012-04-11, Wed | 12,992 views
编程算法　

计算N!

Time Limit:1000MS Memory Limit:32768K

Description

yaojian最近学了一个新的运算法则——阶乘，但他很懒，不想一步一步计算，所以他想让你来帮他编一个程序，能马上得到N的阶乘。

Input

输入包含若干行数据，每行都有一个整数N(0<=N<=200)。

Output

与输入相对应每行输出N的阶乘。

Sample Input

2
4

Sample Output

 
2
24

Source

ZJUT1382

这道题看起来很简单，但其实存在一个很大的问题：200的阶乘是很恐怖的375位数：

78865786736479050355236321393218506229513597768717326329474253324435944996340334
29203042840119846239041772121389196388302576427902426371050619266249528299311134
62857270763317237396988943922445621451664240254033291864131227428294853277524242
40757390324032125740557956866022603190417032406235170085879617892222278962370389
7374720000000000000000000000000000000000000000000000000

根本完全无法用任何基础类型来储存，因此可以使用数组模拟超大数运算。下面是代码，因为N!比较简单，就不作注释，只为超大数运算部分添加注释。

#include<iostream>
using namespace std;
int main(){
	int n;
	int a[201][101] = {0};
	a[0][1] = 1;
	for(int i = 1; i <= 200; ++i){
		int tmp = 0;	//用于储存进位
		for(int j = 1; j < 100; ++j){
			a[i][j] = a[i - 1][j] * i + tmp;	//先做乘法，再加上进位
			tmp = a[i][j] / 10000;	//超过四位的部分保存出来，用于进位
			a[i][j] %= 10000;	//每一位数组只保留四位数字
		}
	}
	while(scanf("%d", &n) != EOF){
		int k = 100;
		while(!a[n][k--]);	//排除前面为空的数组
		printf("%d", a[n][k + 1]);	//输出结果的前四位
		for(; k > 0; --k){
			printf("%04d", a[n][k]);	//输出其余的所有四位数字，若数字小于四位，则前面用0填充
		}
		printf("\n");
	}
	return 0;
}

因为很多人问，所以把数组储存超大数的理论结构做成一个表格，关于数组储存超大数及超大数的运算我之后再写一篇博客来介绍一下。

a	5	4	3	2	1
a[i]	0	12	34	5678	910
输出		12	0034	5678	0910

如需转载请注明出处：杰拉斯的博客

杰拉斯的博客