基础练习 阶乘计算

问题描述 　　

输入一个正整数n，输出n!的值。其中n!=1*2*3*…*n。

输入格式 　　

输入包含一个正整数n，n<=1000。

输出格式 　　

输出n!的准确值。

 

样例输入

10

样例输出

3628800

解题过程

      很明显，我们无法直接用课本上的递归或循环的连乘。所以有涉及到了高精度计算方法。（就是将数放入数组中逐个计算，最后看具体情况来决定是加还是逆序输出）。一开始，习惯限制我的想象……我竟然还考虑“高精度加法”中的个位对个位的方法。后来我参考了别的大神的思路，才能茅塞顿开。这里的数组中的一个元素不是只能存储个位的，而是可以存储2位数、3位数等多位数。（学习到了）

     由于n<=1000,必然考虑1000!有多少位的问题。假设每项都为1000，那么1000个1000相乘后的位数为9位。那么如果你数组为a[1000],那么数组中的每一项至少存储6位数。如果为a[10000],那么每项至少4位数。

     这里附上10！的计算过程（字迹有点迷），以7！开始往后算

附上代码

#include<iostream>
using namespace std;
const int Maxn=10000;
int main()
{
	int a[Maxn]={1};//这里只有a[0]=1,a[1]~a[Maxn-1]随机 
	int len=1;	
	int r=0;	//进位 
	int n;
	cin>>n;	
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<len;j++)
		{
			a[j]=a[j]*i+r;
			r=a[j]/10000;	//这里用10000只是为了保留4位数 
			a[j]=a[j]%10000;//如果用1000，那么最高保留 3位数 
		}
		if(r)
		{
			a[len]=r;
			len++;
			r=0; 
		}
	}
	for(int i=len-1;i>=0;i--)
		cout<<a[i];
	cout<<endl;
	return 0;
}