ACM 大数阶乘模板原版+进阶+高级+最终（C++）+java版

àì夳堔傛蜴生んèń 2024-02-19 19:23 9阅读 0赞

**目录**

一.C++版

1.原版

2.进阶

3.高级

4.最终

二.java版

--------------------

##  ##

所有测试数据均为10000！

## 一.C++版 ##

### 1.原版 ###

思想：

用一个数组去存每一次阶乘的结果，仔细想想就能想出来。

#include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<time.h>
    #include<cstring>
    using namespace std;
    #define max 40000
    int a[max];
    void factorial(int n)
    {
    	int i,j,add=0;   //add为进位 
    	a[0]=1;
    	for(i=1;i<=n;i++)    // 思想是把阶乘结果存到一个数组里 ，每一次对数组进行处理 
    	{
    		add=0;
    		for(j=0;j<max;j++)
    		{
    			a[j]=a[j]*i+add;
    			add=a[j]/10;
    			a[j]=a[j]%10;
    		}
    	}
    	for(i=max-1;i>=0;i--)   //c从后往前，找到第一个不为0的数组单元 
    	if(a[i])
    	break;
    	for(;i>=0;i--)       //开始输出，每一个数组单元此时仅一位数字 
    	printf("%d",a[i]);
    }
    int main()
    {
    	clock_t start,end;
    	start=clock();
    	memset(a,0,sizeof(a));
    	int n;
    	cin>>n;
    	factorial(n);
    	end=clock();
    	cout<<endl<<"大数阶乘原版耗时："<<(float)(end-start)*1000.0/CLOCKS_PER_SEC<<"ms"<<endl;
    	return 0;
    }

结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70][]

### 2.进阶 ###

for(j=0;j<max;j++)

在i循环里还有一个j循环，这个j循环每次都是从0到max（max为40000），即便数组单元没有数值，他也照样循环，浪费时间，其实，j每次循环的次数为上一次结果的位数，就OK了，即i！的位数（从0开始，所以是i！，而不是（i-1）！），

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 1][]

咱也不知道咋让转90度，先这样看吧。

**N!的位数=\[lg(1)+lg(2)+…..lg(N)\]+1(\[\]表示向上取整) 向上取整，再+1，更保险**

**然后，就声明一个double数组存相应的位数。**

**具体见代码**

#include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<time.h>
    #include<cstring>
    using namespace std;
    #define max 40000
    int a[max];
    double b[max]; 
    void factorial(int n)
    {
    	int i,j,add=0;
    	a[0]=1;
    	b[0]=0;
    	for(i=1;i<max;i++)      // 预处理每一位的位数 
    	{
    		b[i]=b[i-1]+log10(i);
    	}
    	for(i=1;i<=n;i++)
    	{
    		add=0;
    		for(j=0;j<=(int)(b[i-1]+1);j++)    //向上取整 
    		{
    			a[j]=a[j]*i+add;
    			add=a[j]/10;
    			a[j]=a[j]%10;
    		}
    	}
    	for(i=(int)(b[n]+1);i>=0;i--)   //h还有这个地方，也可以优化 
    	if(a[i])
    	break;
    	
    	for(;i>=0;i--) 
    	printf("%d",a[i]);
    }
    int main()
    {
    	clock_t start,end;
    	start=clock();
    	memset(a,0,sizeof(a));
    	int n;
    	cin>>n;
    	factorial(n);
    	end=clock();
    	cout<<endl<<"大数阶乘进阶版耗时："<<(float)(end-start)*1000.0/CLOCKS_PER_SEC<<"ms"<<endl;
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 2][]

### 3.高级 ###

我们知道：用来存放结果的数组是int型的，4个字节，能存21亿多，让一个数组单元存一位数，是不是有点太亏了，我们也不多存，就让他存5位数，那么原来存放每一次阶乘结果的位数的数组中的数值该怎么变？

每一单元从存放一位数到存放5位数，显然，存放结果位数的数组中的每一个数值变为原来的五分之一。

#include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<time.h>
    #include<cstring>
    using namespace std;
    #define max 40000
    int a[max];
    double b[max]; 
    void factorial(int n)
    {
    	int i,j,add=0;
    	a[0]=1;
    	b[0]=0;
    	for(i=1;i<max;i++)
    	{
    		b[i]=b[i-1]+log10(i);
    	}
    	for(i=1;i<=n;i++)
    	{
    		add=0;
    		int x=(int)(b[i]+1);
    		x=x/5;
    		for(j=0;j<=x;j++)    //
    		{
    			a[j]=a[j]*i+add;
    			add=a[j]/100000;
    			a[j]=a[j]%100000;
    		}
    	}
    	for(i=(int)(b[n]+1)/5;i>=0;i--)
    	if(a[i])
    	break;
    	printf("%d",a[i--]);
    	for(;i>=0;i--) 
    	printf("%05d",a[i]);
    	/*"%05d" 为什么会是他呢?
    		而不是"%d"？？？？？
    		因为如果结果为102000各位取余后res[0]=2000;
    		res[1]=1,输出的时候直接为12000,会出现错误，
    		这里你就明白了吧。*/
    }
    int main()
    {
    	clock_t start,end;
    	start=clock();
    	memset(a,0,sizeof(a));
    	int n;
    	cin>>n;
    	factorial(n);
    	end=clock();
    	cout<<endl<<"大数阶乘进阶版耗时："<<(float)(end-start)*1000.0/CLOCKS_PER_SEC<<"ms"<<endl;
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 3][]

### 4.最终 ###

用一个b数组存放每一次结果的位数，是不是有点浪费空间了，能不能用a数组本身来达到b数组的效果？

当然能啦！

当每次j循环结束，对进位进行判断，是否大于0，则把进位填充到相应的位置。

不懂的话，看代码

#include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<time.h>
    using namespace std;
    #define LL int 
    void facterial(LL n)
    {
    	int a[10000];
    	int i,j,l,c,m=0;
    	LL w;
    	a[0]=1;
    	for(i=1;i<=n;i++)
    	{
    		c=0;
    		for(j=0;j<=m;j++)
    		{
    			a[j]=a[j]*i+c;
    			c=a[j]/100000;
    			a[j]=a[j]%100000;
    		}
    		if(c>0)        //如果有进位 用m*4存放上一次结果的位数 
    		{
    			m++;
    			a[m]=c;
    		}
    	}
    	w=m*5+log10(a[m])+1;  // 计算最终结果的位数 
    	printf("%d",a[m]);
    	for(i=m-1;i>=0;i--)
    	{
    		printf("%05d",a[i]);
    		/*"%05d" 为什么会是他呢?
    		而不是"%d"？？？？？
    		因为如果结果为102000各位取余后res[0]=2000;
    		res[1]=1,输出的时候直接为12000,会出现错误，
    		这里你就明白了吧。*/
    	}
    	
    }
    int main()
    {
    	clock_t start,end;
    	start=clock();
    	LL n;
    	cin>>n;
    	facterial(n);
    	end=clock();
    	cout<<endl;
    	cout<<"最终版耗时："<<(float)(end-start)*1000.0/CLOCKS_PER_SEC<<"ms"<<endl;
    	return 0;
     }

## 二.java版 ##

用java解大数题简直开挂，记住java有BigDecimal类

package 大数;
    
    import java.math.BigDecimal;
    import java.util.Scanner;
    
    public class 大数阶乘 {
    	public static BigDecimal factorial(BigDecimal n)
    	{
    		long start=System.currentTimeMillis();
    		BigDecimal a=new BigDecimal(1);
    		BigDecimal res=new BigDecimal(1);
    		while(n.compareTo(a)>0)   //如果n>1
    		{
    			res=res.multiply(n);  //  res*n
    			n=n.subtract(a);   //  n=n-1;
    		}
    		
    		return res;
    	}
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		long start=System.currentTimeMillis();
    		Scanner in=new Scanner(System.in);
    		BigDecimal n=in.nextBigDecimal();
    		in.close();
    		System.out.println(n+"!=:"+factorial(n));
    		long end=System.currentTimeMillis();
    		System.out.println("当前程序运行了："+(end-start)+"ms");
    
    	}
    
    }

切记：BigDecimal类的运算只能和同类进行操作。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 4][]

开10000，不出结果，所以啊，还是自己老实的写吧，O(∩\_∩)O哈哈~

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 5][]

如果你有不懂的地方，请留言，乐意解答。

最后，

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 7][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/87ba36fc6c4a48efaa3dc6819a3717f7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/058c71fba95747c3822026f54ff20c29.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/79ef145081094aaba9e031e439fe97d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/8e60fcd6fb364762ab5ca5e0dd0b7d64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/50602485c08d4effacb8f217586cc0b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/70ad13db53c246fe95aa4f39991f1d95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/476ca23eda4d45bb9212cf45e686dc76.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/f39d364cc0b34fd598affa36f9fe39d3.png