C++基础算法教程——高精度算法
2022/1/8 22:10:12
本文主要是介绍C++基础算法教程——高精度算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
欢迎来到沾花把玖的C++算法课堂!
高精度算法
利用计算机进行数值计算,有时会遇到这样的问题:有些计算要求精度高,希望计算的数的位数可达几十位甚至几百位,虽然计算机的计算精度也算较高了,但因受到硬件的限制,往往达不到实际问题所要求的精度。我们可以利用程序设计的方法去实现这样的高精度计算。
高精度计算中需要处理好以下几个问题:
1.数据的接受方法和存贮方法
当输入的数很长时,可采用字符串的方式读入,这样可以输入位数很长的数,利用字符串函数和操作运算,将每一位数取出,存入数组中。
void init(int a[]){ //传入一个数组 string s; cin>>s; //读入字符串s int len=s.length(); //用len计算字符串s的位数 for(int i=1;i<len;i++) a[i]=s[len-1]-'0'; //将字符串s转换为数组a,并倒序存储 }
另一种方法是直接用循环加数组的方法输入数据。
2.高精度位数的确定
接收时往往是用字符串的,所以它的位数就等于字符串的长度。
3.进位、借位的处理
加法进位:
c[i]=a[i]+b[i]; if(c[i]>=10){ c[i]%=10; c[i+1]++; }
减法借位:
if(a[i]<b[i]){ a[i+1]--; a[i]+=10; } c[i]=a[i]-b[i];
乘法进位:
c[i+j-1]=a[i]*b[i]+x+c[i+j-1]; x=c[i+j-1]/10; c[i+j-1]%=10;
4.商和余数的求法
视被除数和除数的位数情况进行处理。
例题1:
【题目描述】
求两个不超过200位的非负整数的和。
【输入】
有两行,每行是一个不超过200位的非负整数。
【输出】
一行,即相加后的结果。
【样例输入】
22222222222222222222
33333333333333333333
【样例输出】
55555555555555555555
以下是代码:
#include<bits/stdc++.h> using namespace std; string s1,s2; int a[10010],b[10010],c[10010]; int main(){ cin>>s1>>s2; a[0]=s1.length(); for(int i=1;i<=a[0];i++)a[i]=s1[a[0]-i]-'0'; b[0]=s2.length(); for(int i=1;i<=b[0];i++)b[i]=s2[b[0]-i]-'0'; c[0]=max(a[0],b[0]); for(int i=1;i<=c[0];i++){ c[i]+=a[i]+b[i]; c[i+1]=c[i]/10; c[i]%=10; } if(c[c[0]+1]!=0)c[0]++; for(int i=c[0];i>=1;i--)cout<<c[i]; cout<<endl; return 0; }
例题2:
【题目描述】
求两个大的正整数相减的差。
【输入】
共2行,第1行是被减数a,第2行是减数b(a > b)。每个大整数不超过200位,不会有多余的前导零。
【输出】
一行,即所求的差。
【样例输入】
9999999999999999999999999999999999999
9999999999999
【样例输出】
9999999999999999999999990000000000000
以下是代码:
#include<bits/stdc++.h> using namespace std; string s1,s2; int a[10010],b[10010],c[10010]; int main(){ cin>>s1>>s2; a[0]=s1.length(); for(int i=1;i<=a[0];i++)a[i]=s1[a[0]-i]-'0'; b[0]=s2.length(); for(int i=1;i<=b[0];i++)b[i]=s2[b[0]-i]-'0'; c[0]=a[0]; for(int i=1;i<=c[0];i++){ if(a[i]<b[i]){ a[i+1]--; a[i]+=10; } c[i]=a[i]-b[i]; } while(c[0]>1&&c[c[0]]==0)c[0]--; for(int i=c[0];i>=1;i--)cout<<c[i]; cout<<endl; return 0; }
本文内容为小编自己汇总,内容可能会有错误或疏漏,感谢大家的提议!
记得点赞和关注哦~
这篇关于C++基础算法教程——高精度算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升