hdu 1042 N!(大数)
发布时间:2020-12-14 02:55:11 所属栏目:大数据 来源:网络整理
导读:题意:求n!(0 ≤ N ≤ 10000) 思路:大数,用数组存储 1.首先要考虑数据N!的位数,因为最大是10000!,可以计算一下大概是5+9000*4+900*3+90*2+10*1=38865位, (此处没看懂,怎么求的) 可以开一个40000的int数组存放,然后用常规的方法去计算 2.但是需
题意:求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,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,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; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |