【算法基础】高精度加法
2023-04-18 16:05:54 时间
👦个人主页:@Weraphael
✍🏻作者简介:目前是C语言学习者
✈️专栏:【C/C++】算法
🐋 希望大家多多支持,咱一起进步!😁
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注😍
一、算法由来
a + b 自然是个很简单的问题,但若
a
和b
都能达到106位的话,连unsigned long long
都存不了,这就要用到高精度加法。
二、算法原理
就是用计算机来模拟人类列竖式加法
现在我们来回忆一下小学的加法是如何计算的
三、算法描述
- 首先,我们用数组存这两组数。为了方便读入,采用字符串读入。为什么要采用字符串读入呢?因为数据位数过长。
- 接着,将其转化成数字存进
vector<int>
数组中。存进数组的时候一定要倒着存入,为什么呢?因为后面计算中会涉及进位,如果最高位有进位的话,想把数据存入数组的低位,就需要把整个数组向后移,造成时间复杂度的增加,而想要把数据存入数组的高位是非常简单的。 - 然后,开始设进位一开始为
t = 0
,对于答案的每一位,只需将(Ai+ Bi+ t) %10就能得到,进位的更新只要每次循环结束后将总的结果÷10
即可。(还有一些细节在模板中) - 最后计算完之后,再把数组倒置输出即是答案
四、代码模板
【c++】
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e6 + 10;
vector<int> add(vector<int> &A,vector<int> &B)
{
vector<int> C; //C数组存储答案
int t = 0;//t表示进位
for(int i = 0;i < A.size() || i < B.size();i++)
{
if (i < A.size()) t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;//把t的个位数去掉只剩下十位数,即只剩下这个位置的进位
}
if(t)
{
C.push_back(t); //如果最后t≠0,说明还有进位,要在最高位补进位
}
return C;//返回C数组
}
int main()
{
string a,b;//数值太长,用字符串读
vector<int> A,B;//用vector来存储
//读入
cin >> a >> b;
//数组倒置
//减‘0’是因为假设a字符串存储的是‘1’,而这个1是字符1,asc码是49
//相减就是数字1
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 = add(A,B);
//输出,由于返回的数组C的答案是倒置的,要再把它反过来
for (int i = C.size() - 1;i >= 0;i --) printf("%d",C[i]);
return 0;
}
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击