大数问题

逃离我推掉我的手 2022-11-19 01:09 78阅读 0赞

# 大数问题 #

##### 基础练习 阶乘计算 #####

时间限制：1.0s 内存限制：512.0MB

##### 问题描述 #####

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

##### 算法描述 #####

n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A\[0\]表示a的个位，A\[1\]表示a的十位，依次类推。  
　　将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。  
　　首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。

##### 输入格式 #####

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

##### 输出格式 #####

输出n!的准确值。

##### 样例输入 #####

##### 样例输出 #####

3628800

##### 思路 #####

弄一个数组然后一位位存值，每位依次乘，然后求进位

##### 代码 #####

#include <stdio.h> 
    int a[10000]; 
    int main()
    { 
    	int x,len=0,c=0;
    	scanf("%d",&x);
    	a[0]=1;
    	for(int i=2;i<=x;i++)
    	{ 
    		for(int j=0;j<=len;j++)
    		{ 
    			int demp=a[j]*i+c;//当前位乘完后的值
    			c=demp/10;//进位
    			a[j]=demp%10;//余下的值
    			if(j==len&&c!=0)//最高位进位然后长度加一
    			{ 
    				len++;
    			}
    		}
    	}
    	for(int i=len;i>=0;i--)//逆序输出
    	{ 
    		printf("%d",a[i]);
    	}
        return 0;
    }

##### 基础练习 高精度加法 #####

时间限制：1.0s 内存限制：512.0MB

##### 问题描述 #####

输入两个整数a和b，输出这两个整数的和。a和b都不超过100位。

##### 算法描述 #####

由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，一般使用数组来处理。  
　　定义一个数组A，A\[0\]用于存储a的个位，A\[1\]用于存储a的十位，依此类推。同样可以用一个数组B来存储b。  
　　计算c = a + b的时候，首先将A\[0\]与B\[0\]相加，如果有进位产生，则把进位（即和的十位数）存入r，把和的个位数存入C\[0\]，即C\[0\]等于(A\[0\]+B\[0\])%10。然后计算A\[1\]与B\[1\]相加，这时还应将低位进上来的值r也加起来，即C\[1\]应该是A\[1\]、B\[1\]和r三个数的和．如果又有进位产生，则仍可将新的进位存入到r中，和的个位存到C\[1\]中。依此类推，即可求出C的所有位。  
　　最后将C输出即可。

##### 输入格式 #####

输入包括两行，第一行为一个非负整数a，第二行为一个非负整数b。两个整数都不超过100位，两数的最高位都不是0。

##### 输出格式 #####

输出一行，表示a + b的值。

##### 样例输入 #####

20100122201001221234567890  
2010012220100122

##### 样例输出 #####

20100122203011233454668012

##### 思路： #####

利用数组来实现

特别注意31行的代码，要注意：  
输入  
218923438177986189160786402426  
835438596590886553207420956312  
此时若没有该行则输出：  
054362034768872742368207358738  
遗漏了最高位的1

#include <stdio.h> 
    #include <string.h>
    
    char a[105]={ 0},b[105]={ 0};
    int c[105]={ 0};
    int main()
    { 
    	int len1=0,len2=0,max;  
    	scanf("%s%s",a,b);
    	len1=strlen(a);
    	len2=strlen(b);
    // printf("%d %d",len1,len2);
    	if(len1>=len2)
    	max=len1;
    	else max=len2;
    	for(int i=0;i<max;i++)
    	{ 
    		if(i<len1)
    		{ 
    			c[i] += a[len1-i-1]-'0';//char转int
    		}
    		if(i<len2)
    		{ 
    			c[i] += b[len2-i-1]-'0'; 
    		}
    		if(c[i]>9)
    		{ 
    			c[i+1]=c[i]/10;
    			c[i]=c[i]%10;
    			if(i==max-1&&c[i+1])//判断当前最高位是否有值 若有值就增加长度
    			max++;
    		}
    	}
    	for(int i=max-1;i>=0;i--)
    	{ 
    		printf("%d",c[i]);
    	}
    	return 0;
    }

##### 大数减法 #####

#include <stdio.h>
    #include <string.h>
    char a[1000],b[1000];
    int c[100]={ 0};
    
    int main()
    { 
    	int len_a=0,len_b=0,max,flag=1;//flag 用来表面相同位数下值的大小，以及输出的正负性
    	scanf("%s%s",a,b);
    	len_a=strlen(a);
    	len_b=strlen(b);
    	if(len_a>len_b)
    	max=len_a;
    	else if(len_a<len_b)
    	{ 
    	max=len_b;
    	flag=-1;
    	}
    	else
    	{ 
    		flag=strcmp(a,b);
    		max=len_a;	
    	}
    	
    	if(flag>0)
    	{ 
    		for(int i=0;i<max;i++)
    		{ 
    			if(i<len_a)
    			{ 
    				c[i]+=a[len_a-i-1]-'0';
    			}
    			if(i<len_b)
    			{ 
    				c[i]-=b[len_b-i-1]-'0';
    			}
    			if(c[i]<0)
    			{ 
    				c[i]+=10;
    				a[len_a-i-2]--;
    			}
    		}
    	}else
    	{ 
    		for(int i=0;i<max;i++)
    		{ 
    			if(i<len_a)
    			{ 
    				c[i]-=a[len_a-i-1]-'0';
    			}
    			if(i<len_b)
    			{ 
    				c[i]+=b[len_b-i-1]-'0';
    			}
    			if(c[i]<0)
    			{ 
    				c[i]+=10;
    				b[len_b-i-2]--;
    			}
    		}
    	}
    	if(flag<0)
    	flag=-1;
    	else flag=1;
    	while(c[max-1]==0)
    	{ 
    		max--;
    	}
    	c[max-1]*=flag;
    	for(int i=max-1;i>=0;i--)
    	{ 
    		printf("%d",c[i]);
    	}
    	return 0;
    }