基础算法题——高精度加、减、乘、除

Dear 丶 2023-07-16 12:57 10阅读 0赞

前言  
本文仅对正整数进行运算，若扩大到负数只要提前判断最终结果是否为负，然后将负数转换为正数计算。当最终结果为负时，只需在答案前加负号即可。

### 高精度加法 ###

> **a+b=c**  
> 由于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输出即可。

#include<bits/stdc++.h>
    #include<cstring>
    using namespace std;
    string A, B, C;
    
    void js(string A, string B)//计算 
    { 
    	int len, i, a=0, b=0, d=0;
    	
    	A=A.substr(A.find_first_not_of('0'));//返回第一个不是0的字符地址 
    	B=B.substr(B.find_first_not_of('0'));//若出现02+03也可以计算 
    	
    	reverse(A.begin(), A.end());//翻转
    	reverse(B.begin(), B.end());
    	
    	A.length()>B.length()?len=A.length():len=B.length();//长度 
    	
    	string C(len+10, '0');	//初始化 (必须)：C字符串并没被赋值，值为随机 
    	
    	for(i=0; i<=len; i++)
    	{ 
    		a=0, b=0;
    		if(i<A.length())a=A[i]-'0';
    		if(i<B.length())b=B[i]-'0';
    		C[i]=(a+b+d)%10+'0';
    		d=(a+b+d)/10;
    	}
    
    	reverse(C.begin(), C.end());
    	cout<<C;
    }
    
    int main()
    { 
    	cin>>A>>B;
    	js(A, B);
    	return 0;
    }

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

### 高精度减法 ###

> **a-b=c**  
> 由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，一般使用数组来处理。定义一个数组A，**A\[0\]用于存储a的个位，A\[1\]用于存储a的十位，依此类推**。同样可以用一个数组B来存储b。  
> 计算a - b = c 的时候，判断a与b的大小，用大的减去小的。在这里我们假设a>b固定。首先从低位相减，**如果a\[0\]要借位，则把a\[1\]自减1，a\[0\]-b\[0\]+10作为个位数存入C\[0\]，即C\[0\]等于A\[0\]-B\[0\]+10**。然后计算A\[1\]与B\[1\]相减，依此类推，即可求出C的所有位。最后将C输出即可。

#include<bits/stdc++.h>
    using namespace std;
    
    int main()
    { 
    	string a, b;
    	int judge=0;
    	cin>>a>>b;
    	if(a<b)
    	{ 
    		string s = a;
    		a = b;
    		b = s;
    		judge=1;
    	}
    	else if(a==b)
    	{ 
    		cout<<"0";
    		return 0;
    	}
    	//a - b = c
    	string c(a.length()+2, '0');
    	reverse(a.begin(), a.end());
    	reverse(b.begin(), b.end());
    	for(int i=0; i<a.length(); i++)
    	{ 
    		int intb = 0;
    		if(i<b.length())
    		  	intb = b[i] - '0';
    		c[i] = a[i] - intb;
    		if(c[i] < '0')
    		{ 
    			c[i]+=10;
    			a[i+1]--;
    		}
    	}
    	reverse(c.begin(), c.end());
    	c = c.substr(c.find_first_not_of('0'));
    	if(judge==1)
    		cout<<"-";
    	cout<<c;
    	
    	return 0;
    }

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

### 高精度乘法 ###

> **a \* b = c**  
> 由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，一般使用数组来处理。定义一个数组A，**A\[0\]用于存储a的个位，A\[1\]用于存储a的十位，依此类推**。同样可以用一个数组B来存储b。  
> 计算c = a \* b的时候，首先将数组A与B\[0\]相乘，得到AB\[0\]。接着依次将A与B\[1\]相乘得到AB\[1\]…由两数相乘可以得到AB\[0\]~AB\[N\]（假设B\[N\]为b的最高位）。计算AB\[0\] \* 100\+AB\[1\] \* 10 1 \+ … + AB\[N\]\*10N得到C数组，通过高精度加法可以完成，最后将C输出即可。

#include<bits/stdc++.h>
    using namespace std;
    
    string add(string a, string b)//功能实现， 输入为计算式，输出计算式 
    { 
    	if(a=="0") return a;	//特殊情况 
    	if(b=="0") return b;
    	
    	int c, d=0;
    	a.length()>b.length()?c=a.length():c=b.length();
    	string s(c+10,'0');
    	for(int i=0; i<=c; i++)
    	{ 
    		int inta=0, intb=0;
    		if(i<a.length()) inta=a[i]-'0';
    		if(i<b.length()) intb=b[i]-'0';
    		s[i]=(inta+intb+d)%10+'0';
    		d=(inta+intb+d)/10;
    	}
    	reverse(s.begin(), s.end());
    	s=s.substr(s.find_first_not_of('0'));
    	reverse(s.begin(), s.end());
    	return s;
    }
    
    string sch(string s2,char s1ch)
    { 
    	if(s2=="0"||s1ch=='0')	//判断特殊情况 
    		return "0";
    	
    	string s;
    	int d=0;
    	for(int i=0; i<=s2.length(); i++)
    	{ 
    		int ints2=0, ints1ch=s1ch-'0';
    		if(i<s2.length()) ints2=s2[i]-'0';//确定数值 
    		//计算与进位 
    		int temp=(ints1ch*ints2+d)%10;
    		d=(ints1ch*ints2+d)/10;	 
    
    		//相加 
    		string a(1, temp+'0'); 
    		s+=a; 
    	}
    	return s;
    }
    
    int main()
    { 
    	int s1_0, s2_0;
    	string s1,s2;
    	cin>>s1>>s2;
    	if(s1=="0"||s2=="0")
    	{ 
    		cout<<"0";
    		return 0;
    	} 
    	string ss;
    	reverse(s1.begin(), s1.end());
    	reverse(s2.begin(), s2.end());
    	
    	for(s1_0=0; s1[s1_0]=='0'; s1_0++);	//统计0的数量 
    	for(s2_0=0; s2[s2_0]=='0'; s2_0++);
    	s1=s1.substr(s1.find_first_not_of('0'));
    	s2=s2.substr(s2.find_first_not_of('0'));
    	
    	for(int k=0; k<s1.length(); k++)
    	{ 
    		string s=sch(s2, s1[k]);	//字符串 * 字符 
    		
    		reverse(s.begin(), s.end());
    		for(int j=0; j<k; j++)		//进多少位
    			s+='0';
    		reverse(s.begin(), s.end());
    		
    		ss=add(ss, s);				//加上字符串 * 字符进位后的值 
    	}
    	reverse(ss.begin(),ss.end());
    	cout<<ss;
    	
    	for(int t=1; t<=s1_0+s2_0; t++)
    	cout<<"0";
    	return 0;
    }

### 高精度除法 ###

> **a / b = c**  
> 由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，一般使用数组来处理。定义一个数组A，**A\[0\]用于存储a的个位，A\[1\]用于存储a的十位，依此类推**。同样可以用一个数组B来存储b。

> 让我们通过例子来了解实现过程：  
> First：1/3=0.33…33  
> ![例1][1]  
> Second:1/4=0.25  
> ![例2][2]

希望能够将自己的一些学习经验分享给有需要的人。  
我是小郑，一个坚持不懈的小白。

[1]: /images/20230528/0bede8679a41437db944d065ef0e7c03.png
[2]: /images/20230528/5e29c7dc6f1b45b89a3898ac77dfe3f4.png