高精度算法

淩亂°似流年 2022-07-15 19:17 178阅读 0赞

***大整数的四则运算***

我们都知道不管是什么类型的整数都是有限制的，那么对于大整数的四则运算我们是否就没有办法了呢？答案是否定的，这里将介绍大整数的四则运算。我们可以先用字符数组存储大整数，然后像小学学算数一样，按照小学的算数法则对大整数进行加减乘除。这里只介绍大整数乘以一位数的算法和大整数除以一位数的算法。

1.加法运算

代码如下：

#include<stdio.h>
 #include<string.h>
 #define MAX 200
 void inv(char s[],int len) //将整数逆置，使s[0]是低位
 {
 	int i,j;
 	for(i=0,j=len-1;i<j;i++,j--)
 	{
 		char s1;
 		s1=s[i];
 		s[i]=s[j];
 		s[j]=s1;
 	}
 }
 int main()
 {
 	char s1[MAX+2],s2[MAX+2]; //定义两个字符数组，用于存放大整数
 	scanf("%s%s",s1,s2);
 	int len1,len2;
 	len1=strlen(s1);
 	len2=strlen(s2);
 	if(len1>len2)
 	{
 		char s[MAX+2];
 		strcpy(s,s1);
 		strcpy(s1,s2);
 		strcpy(s2,s);
 		len1=strlen(s1);
 		len2=strlen(s2);
 	}
 	inv(s1,len1);
 	inv(s2,len2);
 	int i;
 	for(i=0;i<len1;i++)
 	{
 		s2[i]+=s1[i]-'0'; //对齐后对大整数的各位相加，即ASCII值相加
 	}
 	for(i=0;i<len2;i++)
 	{
 		if(s2[i]>'9') //若该位ASCII值大于'9'，说明有进位 
 		{
 			s2[i]-=10;
 			s2[i+1]++;
 			if(i==len2-1) 
 			{
 				s2[len2]='1';
 				s2[len2+1]='\0';
 				len2++;
 			}	
 		}
 	}
 	inv(s2,len2); //逆置回来
 	printf("%s",s2);
 	return 0;
 }

2.减法运算

代码如下：

#include<stdio.h>
 #include<string.h>
 #define MAX 200
 void inv(char s[],int len) //整数逆置
 {
 	int i,j;
 	for(i=0,j=len-1;i<j;i++,j--)
 	{
 		char c;
 		c=s[i];
 		s[i]=s[j];
 		s[j]=c;
 	}
 }
 int main()
 {
 	char s1[MAX+1],s2[MAX+1];
 	scanf("%s%s",s1,s2);
 	int len1,len2;
 	len1=strlen(s1);
 	len2=strlen(s2);
 	if(len1==len2) //判断整数位数是否相等 
 	{
 		if(strcmp(s1,s2)<0) //比较整数大小
 		{
 			char s[MAX+1];
 			strcpy(s,s1);
 			strcpy(s1,s2);
 			strcpy(s2,s);
 		}
 	}
 	if(len1<len2) //若不相等，则位数大的整数大，交换的意义在于始终保证s[1]大，即让它成为减数
 	{
 	 	char s[MAX+1];
 	 strcpy(s,s1);
 		strcpy(s1,s2);
 		strcpy(s2,s);
 	}
 	len1=strlen(s1);
 	len2=strlen(s2);
 	inv(s1,len1);
 	inv(s2,len2);
 	int i;
 	for(i=0;i<len2;i++)
 	{
 		if(s1[i]>s2[i]) //若减数该位较大，直接相减。否则应借位再减 
 		{
 			s1[i]=s1[i]-s2[i]+'0';
 		}
 		else 
 		{
 			s1[i]=s1[i]+10-s2[i]+'0';
 			s1[i+1]--;
 		}
 	}
 	for(i=len2;i<len1;i++) //判断减数该位是否小于0，若小于0，应向高位借位
 	{
 		if(s1[i]<'0')
 		{
 			s1[i]+=10;
 			s1[i+1]--;
 		}
 	}
 	inv(s1,len1); //逆置回来
 	if(s1[0]=='0') //若高位为0，舍去
 	{
 		for(i=1;i<len1;i++)
 		{
 			printf("%c",s1[i]);
 		}
 	}
 	else
 	 printf("%s",s1);
 	return 0;
 }

3.乘法运算

代码如下：

#include<stdio.h>
 #include<string.h>
 #define MAX 200
 void inv(char s[],int len)
 {
 	int i,j;
 	for(i=0,j=len-1;i<j;i++,j--)
 	{
 		char c;
 		c=s[i];
 		s[i]=s[j];
 		s[j]=c;
 	}
 }
 int main()
 {
 	char s[MAX+2];
 	int i,a,len;
 	scanf("%s %d",s,&a);
 	len=strlen(s);
 	inv(s,len);
 	for(i=0;i<len;i++)
 	{
 		
 		s[i]=s[i]-'0'; 
 		s[i]=a*s[i];
 		if(i>0&&s[i-1]>9)
 		{
 			s[i]=s[i]+s[i-1]/10;
 			s[i-1]=s[i-1]%10+'0';
 			if(i==len-1&&s[i]>9)
 			{
 				s[i]=s[i]-10+'0';
 				s[len]='1';
 				s[len+1]='\0';
 			}
 		}
 		if(i==len-1&&s[i]<=9) s[i]=s[i]+'0';
 		if(i>0&&s[i-1]<=9) 
 		{
 			s[i-1]=s[i-1]+'0'; 
 		}
 	}
 	inv(s,strlen(s));
 	printf("%s",s);
 	return 0;
  }

4.除法运算

代码如下：

#include<stdio.h>
 #include<string.h>
 #define MAX 200
 int main()
 {
 	char s[MAX+2],ans[MAX+2];
 	int a,i,len;
 	scanf("%s%d",s,&a);
 	len=strlen(s);
 	int k=0;
 	for(i=0;i<len;i++)
 	{
 		s[i]+=k*10-'0';
 	 ans[i]=s[i]/a+'0';
 	 k=s[i]%a;	
 	}
 	int m; 
 	for(i=0;i<len;i++)
 	{
 		if(ans[i]!='0') 
 		{
 			m=i;
 			break;
 		}
 	}
 	for(i=m;i<len;i++)
 	{
 		printf("%c",ans[i]);
 	}
 	return 0;
 }

如有不足之处，请指正！谢谢！