当前位置:网站首页>高精度运算
高精度运算
2022-07-06 10:01:00 【Stellaris_L】
高精度加法
解析
实现高精度加法主要有2点:①怎么将数存下②怎么对数运算
一、怎么存下一个大整数?
答:存在数组当中,并从个位(低位)开始存。例如一个数123456789。
位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
存的数 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
(1)为什么要逆序存?
答:每次计算的时候,都有可能遇到进位的问题。如果在最大一位计算时出现了进位的情况,而我们又是使用正序存储,就需要移动数组在开头空出一个位置,这样会十分繁琐。所以直接使用逆序存储就可以十分方便的加上最后一位进位了。
而且这也符合我们人工计算的方向。(后面会解释人工计算)
(2)为什么使用动态数组(vector)
答:在动态数组中,可以使用STL自带的函数来很方便的获取数组长度,不用另外来求和存储,而且可以随机访问。
二、怎么对数组进行计算?
答:模拟人工加法,从两个数低位开始相加,当相加小于10时候直接表示为这一位的运算结果,相加的大于等于10的时候将大于10的部分作为这一位的运算结果并向前进一位。
模板
vector<int> add(string a,string b){
vector<int>A,B;//将字符串逆序存入动态数组。
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');//转化类型
for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
vector<int>C;
int t=0;//进位标识,初始进位0
for(int i=0;i<A.size()||i<B.size();i++){
if(i<A.size())t+=A[i];//当前位存在,加入t
if(i<B.size())t+=B[i];
C.push_back(t%10);//将非进位数加入数组。
t/=10;//当t大于10时商1,即为进位。
}
if(t)C.push_back(1);//判断最后是否进位
return C;
}
例题
791. 高精度加法 - AcWing题库
AC题解:
#include <iostream>
#include <vector>
using namespace std;
vector<int> add(string a,string b){
vector<int>A,B;//将字符串逆序存入动态数组。
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');//转化类型
for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
vector<int>C;
int t=0;//进位标识,初始进位0
for(int i=0;i<A.size()||i<B.size();i++){
if(i<A.size())t+=A[i];//当前位存在,加入t
if(i<B.size())t+=B[i];
C.push_back(t%10);//将非进位数加入数组。
t/=10;//当t大于10时商1,即为进位。
}
if(t)C.push_back(1);//判断最后是否进位
return C;
}
int main(){
string a,b;
cin>>a>>b;
auto sum=add(a,b);//auto可以自动判断返回值类型,可以偷懒。
for(int i=sum.size()-1;i>=0;i--)cout<<sum[i];
return 0;
}
高精度减法
解析
四种高精度算法的存储方式是相同的。
A 3 A_3 A3 | A 2 A_2 A2 | A 1 A_1 A1 | A 0 A_0 A0 | |
---|---|---|---|---|
— | B 2 B_2 B2 | B 1 B_1 B1 | B 0 B_0 B0 |
A i − B i − t A_i-B_i-t Ai−Bi−t有两种情况,
① A i − B i − t ≥ 0 A_i-B_i-t\ge0 Ai−Bi−t≥0有直接 A i − B i − t A_i-B_i-t Ai−Bi−t。
② A i − B i − t < 0 A_i-B_i-t<0 Ai−Bi−t<0有 A i − B i + 10 − t A_i-B_i+10-t Ai−Bi+10−t,同时要记录一个借位。
这时候可以发现一个问题,只有当保证 A ≥ B A\ge B A≥B时候才能以一个正确的顺序计算。所以我们还需要考虑当 A < B A<B A<B的情况,这种情况也很好处理只需要改成 − ( B − A ) -(B-A) −(B−A)就可以了。这里当然还有一点,就是 A A A和 B B B一定都是正数,若是出现负数的情况还需要一个判断在转化。
- 总结:判断 A A A和 B B B的大小关系, A ≥ B A\ge B A≥B的时候算 A − B A-B A−B; A < B A<B A<B的时候算 − ( B − A ) -(B-A) −(B−A)。
最后还需要去除前导0。
模板
bool cmp(vector<int> &A,vector<int> &B){
if(A.size()!=B.size())return A.size()>B.size();
for(int i=A.size()-1;i>=0;i--)
if(A[i]!=B[i])return A[i]>B[i];
return true;
}
vector<int> sub(vector<int> &A,vector<int> &B){
vector<int> C;
for(int i=0,t=0;i<A.size();i++){
t=A[i]-t;
if(i<B.size())t-=B[i];
C.push_back((t+10)%10);
if(t<0)t=1;
else t=0;
}
while(C.size()>1&&C.back()==0)C.pop_back();//去除前导0
return C;
}
vector<int> C;
if(cmp(A,B))C=sub(A,B);
else C=sub(B,A),cout<<'-';
例题
#include <iostream>
#include <vector>
using namespace std;
bool cmp(vector<int> &A,vector<int> &B){
if(A.size()!=B.size())return A.size()>B.size();
for(int i=A.size()-1;i>=0;i--)
if(A[i]!=B[i])
return A[i]>B[i];
return true;
}
vector<int> sub(vector<int> &A,vector<int> &B){
vector<int> C;
for(int i=0,t=0;i<A.size();i++){
t=A[i]-t;
if(i<B.size())t-=B[i];
C.push_back((t+10)%10);
if(t<0)t=1;
else t=0;
}
while(C.size()>1&&C.back()==0)C.pop_back();//去除前导0
return C;
}
int main(){
string a,b;
vector<int> A,B;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
vector<int> C;
if(cmp(A,B))C=sub(A,B);
else C=sub(B,A),cout<<'-';
for(int i=C.size()-1;i>=0;i--)cout<<C[i];
cout<<endl;
return 0;
}
高精度乘法
解析
这里的高精度乘法和前面的高进度加法和除法不同,不是两个高精度相运算。而是一个高精度和一个低精度的运算。这里的低精度是小于 m a x ( l o n g l o n g ) / 10 max(long\ long)/10 max(long long)/10的。
A 2 = 1 A_2=1 A2=1 | A 1 = 2 A_1=2 A1=2 | A 0 = 3 A_0=3 A0=3 | ||
---|---|---|---|---|
× × × | B = 12 B=12 B=12 | |||
进位 | t 3 t_3 t3 | t 2 t_2 t2 | t 1 t_1 t1 | t 0 t_0 t0 |
值 | C 3 C_3 C3 | C 2 C_2 C2 | C 1 C_1 C1 | C 0 C_0 C0 |
第一步:
C 0 = ( A 0 ∗ B + t 0 ) % 10 = 6 C_0=(A_0*B+t_0)\%10=6 C0=(A0∗B+t0)%10=6
t 1 = ( A 0 ∗ B + t 0 ) / 10 = 0 t_1=(A_0*B+t_0)/10=0 t1=(A0∗B+t0)/10=0
第二步:
C 1 = ( A 1 ∗ B + t 1 ) % 10 = 7 C_1=(A_1*B+t_1)\%10=7 C1=(A1∗B+t1)%10=7
t 2 = ( A 1 ∗ B + t 1 ) / 10 = 2 t_2=(A_1*B+t_1)/10=2 t2=(A1∗B+t1)/10=2
第三步:
C 2 = ( A 2 ∗ B + t 2 ) % 10 = 4 C_2=(A_2*B+t_2)\%10=4 C2=(A2∗B+t2)%10=4
t 3 = ( A 2 ∗ B + t 2 ) / 10 = 1 t_3=(A_2*B+t_2)/10=1 t3=(A2∗B+t2)/10=1
第四步:
C 3 = ( 0 ∗ B + t 3 ) % 10 = 1 C_3=(0*B+t_3)\%10=1 C3=(0∗B+t3)%10=1
- 最终答案 123 ∗ 12 = 1476 123*12=1476 123∗12=1476
模板
vector<int> mul(vector<int> &A,int b){
vector<int> C;
int t=0;
for (int i=0;i<A.size()||t;i++){
if(i<A.size())t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
while(C.size()>1&&C.back()==0)C.pop_back();//去除前导0
return C;
}
vector<int> A;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
例题
#include <iostream>
#include <vector>
using namespace std;
vector<int> mul(vector<int> &A,int b){
vector<int> C;
int t=0;
for (int i=0;i<A.size()||t;i++){
if(i<A.size())t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
while(C.size()>1&&C.back()==0)C.pop_back();//去除前导0
return C;
}
int main(){
string a;
int b;
cin>>a>>b;
vector<int> A;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
auto C=mul(A,b);
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
return 0;
}
高精度除法
解析
和高精度乘法一样,高精度除法也是高精度和低精度的运算。并且设定上不会产生小数,而是以余数的方式存在。
模板
vector<int> div(vector<int> &A,int b,int &r){
//r是引用传递
vector<int> C;//商
r=0;
for (int i=A.size()-1;i>=0;i--){
//从最高位开始算
r=r*10+A[i];
C.push_back(r/b);
r%=b;
}
reverse(C.begin(),C.end());
while(C.size()>1&&C.back()==0)C.pop_back();
return C;
}
例题
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> div(vector<int> &A,int b,int &r){
//r是引用传递
vector<int> C;//商
r=0;
for (int i=A.size()-1;i>=0;i--){
//从最高位开始算
r=r*10+A[i];
C.push_back(r/b);
r%=b;
}
reverse(C.begin(),C.end());
while(C.size()>1&&C.back()==0)C.pop_back();
return C;
}
int main(){
string a;
vector<int> A;
int B;
cin>>a>>B;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
int r;
auto C=div(A,B,r);
for(int i=C.size()-1;i>=0;i--)cout<<C[i];
cout<<endl<<r<<endl;
return 0;
}
边栏推荐
- Kivy tutorial: support Chinese in Kivy to build cross platform applications (tutorial includes source code)
- 一体化实时 HTAP 数据库 StoneDB,如何替换 MySQL 并实现近百倍性能提升
- Nodejs 开发者路线图 2022 零基础学习指南
- FlutterWeb浏览器刷新后无法回退的解决方案
- Pytest learning ----- pytest confitest of interface automation test Py file details
- Summary of Android interview questions of Dachang in 2022 (II) (including answers)
- The art of Engineering
- After entering Alibaba for the interview and returning with a salary of 35K, I summarized an interview question of Alibaba test engineer
- EasyCVR平台通过接口编辑通道出现报错“ID不能为空”,是什么原因?
- Xin'an Second Edition: Chapter 26 big data security demand analysis and security protection engineering learning notes
猜你喜欢
node の SQLite
JMeter interface test response data garbled
Pytest learning ----- detailed explanation of the request for interface automation test
重磅!蚂蚁开源可信隐私计算框架“隐语”,主流技术灵活组装、开发者友好分层设计...
C语言通过指针交换两个数
scratch疫情隔离和核酸检测模拟 电子学会图形化编程scratch等级考试三级真题和答案解析2022年6月
F200——搭载基于模型设计的国产开源飞控系统无人机
一体化实时 HTAP 数据库 StoneDB,如何替换 MySQL 并实现近百倍性能提升
The NTFS format converter (convert.exe) is missing from the current system
[translation] principle analysis of X Window Manager (I)
随机推荐
Getting started with pytest ----- test case pre post, firmware
Chrome prompts the solution of "your company management" (the startup page is bound to the company's official website and cannot be modified)
Spark calculation operator and some small details in liunx
远程代码执行渗透测试——B模块测试
The art of Engineering (3): do not rely on each other between functions of code robustness
重磅!蚂蚁开源可信隐私计算框架“隐语”,主流技术灵活组装、开发者友好分层设计...
RepPoints:可形变卷积的进阶
HMS Core 机器学习服务打造同传翻译新“声”态,AI让国际交流更顺畅
历史上的今天:Google 之母出生;同一天诞生的两位图灵奖先驱
偷窃他人漏洞报告变卖成副业,漏洞赏金平台出“内鬼”
中移动、蚂蚁、顺丰、兴盛优选技术专家,带你了解架构稳定性保障
《ASP.NET Core 6框架揭秘》样章发布[200页/5章]
Fleet tutorial 13 basic introduction to listview's most commonly used scroll controls (tutorial includes source code)
C# NanoFramework 点灯和按键 之 ESP32
【ASM】字节码操作 ClassWriter 类介绍与使用
The art of Engineering
Openharmony developer documentation open source project
【MySQL入门】第四话 · 和kiko一起探索MySQL中的运算符
Interview assault 63: how to remove duplication in MySQL?
Easy introduction to SQL (1): addition, deletion, modification and simple query