hdu 1042 N!（大数）

题意：求n！（0 ≤ N ≤ 10000）

思路：大数，用数组存储

1.首先要考虑数据N!的位数，因为最大是10000！，可以计算一下大概是5+9000*4+900*3+90*2+10*1=38865位，（此处没看懂，怎么求的）

可以开一个40000的int数组存放，然后用常规的方法去计算

2.但是需要改进一下，咱们知道int数组一个只存1位太浪费了，不如让它的空间发挥到极限，数组一个元素存一个不超过10^5的数，

为什么是10^5呢？见代码中的注释，改进后就一个元素存5位，这样开的数组就可以小5倍了，只需要8000就可以了

代码1：

#include<cstdio>

#include<cstring>

const int N=40000;

int main(){

	int ans[N];

	int n,i,j,co,sum;

	while(~scanf("%d",&n)){

		memset(ans,0,sizeof(ans));

		ans[0]=1;

		for(i=2;i<=n;i++){

			for(j=0,co=0;j<N;j++){//求阶乘

				sum=ans[j]*i+co;//

				ans[j]=sum%10;

				co=sum/10;

			}

		}

		for(i=N-1;ans[i]==0;i--);

		printf("%d",ans[i]);

		for(i--;i>=0;i--) printf("%d",ans[i]);

		printf("\n");

	}

	return 0;

}

代码2：

#include<cstdio>

#include<cstring>

const int N=8000;

int main(){

	int ans[N];

	int n,i,j,co,sum;

	while(~scanf("%d",&n)){

		memset(ans,0,sizeof(ans));

		ans[0]=1;

		for(i=2;i<=n;i++){

			for(j=0,co=0;j<N;j++){//求阶乘

				sum=ans[j]*i+co;//这里的sum决定了10^5，因为ans[j]<10^5，i<10^4，co<10^5,那么sum不会超出int范围；如果用10^6，则sum可能溢出。

				ans[j]=sum%100000;

				co=sum/100000;

			}

		}

		for(i=N-1;ans[i]==0;i--);

		printf("%d",ans[i]);

		for(i--;i>=0;i--) printf("%05d",ans[i]);

		printf("\n");

	}

	return 0;

}

巴特西

hdu 1042 N!（大数）

最新文章

热门文章