C++信奥之径,锻炼思维,扎实算法——模拟与高精度算法(4)
liuian 2025-01-14 15:21 79 浏览
【模版题】高精度减法
题目描述
算法解析
1、与上期的高精度加法类似,本题的数字由于最多到达10086位,C++中能存储数据位数最多的_int128类型(在后续的编程技巧中会介绍这一个特殊的大存储类型)也存储不下这个数字,所以需要使用高精度减法来计算结果。
2、同样需要先解决存储两个减数的问题,用字符串string或字符数组char[]来存储。
3、高精度减法的算法原理也是小学数学的减法竖式计算,过程为:(1)数位对齐;(2)从个位开始减,不够就借位;(3)存储结果,计算最终答案的位数,以便去掉前导0。
接下来用程序设计语言描述整个过程。
01
数位对齐
这部分代码与高精度加法一致,可以参考前一篇文章(点击跳转查看)。
同时,在初始化的时候,需要判断a和b的大小,我们只做a>b的减法。如果a-b<0,那么根据减法的规则,a-b = -(b-a),需要交换a和b,并输出负号。
02
从个位开始减,不够就借位
每一位a[i]-b[i]后,需要判断减下来的结果,如果>=0就正常相减,如果<0,说明a[i]需要向高位借1才能与b[i]相减,此时需要c[i+1]--来实现向高位借一,同时要注意高位的减法答案因为借位要-1,而-1也会反馈在高位的减法中。
因此,可以每次将借位的情况传递到c[i+1]上去,如果c[i+1]==0,就表示没有借位,如果c[i+1]==-1,表明前一位减法有借位。因此当前位的减法应该要类似于下面的代码:
c[i] = a[i] - b[i] + c[i]; //+c[i]的目的是加上之前是否有的借位
if(c[i] < 0){
c[i+1]--; //先借位
c[i]+=10; //再算出真正结果
}03
存储结果,计算最终答案的位数,以便去掉前导0
在初始化数据时,我们会大致判断答案数组c的大小肯定不大于max(lena,lenb),即a和b字符串中较大的那个。
但是,如果a和b的长度一致,那么相减得到的结果c可能会位数很少,例如10001-10000=1,但是c数组中储存的答案为00001,这时候就需要去掉前导0来保证答案为数学数字。
使用while循环,当c数组的首位是0时,lenc--,从而获取到正确的答案数组c的长度。具体代码为:
while(c[lenc-1]==0 && lenc>0) //lenc>0是以防最终答案是0的情况
lenc--;【参考代码】
#include<bits/stdc++.h>
using namespace std;
int a[10001],b[10001],c[10002],lena,lenb,lenc;
int main(){
string l1,l2;
cin>>l1>>l2;
lena=l1.length();lenb=l2.length();
//判断a和b的大小
if(lena<lenb || (lena==lenb && l1<l2)){
swap(l1,l2);
cout<<"-";
}
//处理数字
lena=l1.length();
lenb=l2.length();
for(int i=0;i<lena;i++)
a[lena-i]=l1[i]-'0';
for(int i=0;i<lenb;i++)
b[lenb-i]=l2[i]-'0';
lenc=max(lena,lenb);
//模拟竖式相减
for(int i=1;i<=lenc;i++){
c[i]=a[i]+c[i]-b[i];
if(c[i]<0){
c[i+1]--;
c[i]+=10;
}
}
//处理答案的前导0
while(c[lenc-1]==0 && lenc>0)
lenc--;
//如果0都被处理掉了,那么答案就是0
if(lenc==0){
cout<<0;
}
else{
for(int i=lenc;i>0;i--)
cout<<c[i];
}
return 0;
}代码中的C++知识解读
swap()函数
在C++的std标准库中,我们常用swap()函数来进行两个变量或元素的交换,其中函数模版为:
swap()函数
在C++的std标准库中,我们常用swap()函数来进行两个变量或元素的交换,其中函数模版为:
void swap(T &a,T &b){
T c(a);
a = b;
b = c;
}代码中的T为类型,根据实际需要可以使用相应的类型。swap()函数支持相同数据类型的变量值相互交换,例如:
int a,b;
float x,y;
string s1,s2;
//赋值后
swap(a,b);
swap(x,y);
swap(s1,s2);特别地,在string字符串和vector可变数组的函数中,也有自带成员函数swap():
string s1,s2;
s1.swap(s2);
vector<int> a1,a2;
a1.swap(a2);从而实现两个字符串、两个数组内容的交换,并且vector数组在经过容器交换后,还能实现内存空间的收缩,从而节约内存。
运行结果
- 上一篇:C++遍历vector元素的四种方式
- 下一篇:向量(vector)的使用实例
相关推荐
- 万能app破解器(万能app软件破解器)
-
1、以现有的技术手段,是没有办法破解WPA的加密方式(现在基本上全部WIFI的加密方式),WPA的加密方式安全性很高,根本就破不了。2、即使破解密码,人家也有可能设置了MAC地址过滤,还是上不去。3、...
- 笔记本电脑自带摄像头怎么开启
-
要使用笔记本电脑自带的摄像头,请按照以下步骤操作:1.打开你的电脑,进入桌面。2.定位摄像头,通常在笔记本电脑的上部或者展开的屏幕的中央位置。3.双击摄像头图标,或者在键盘上按下对应的快捷键,以...
- 怎么知道wifi密码(手机连接上wifi怎么知道wifi密码)
-
关于这个问题,如果您想查看已经连接过的无线网络密码,请按照以下步骤操作:对于Windows10:1.点击任务栏中的WiFi图标,选择“网络和Internet设置”2.在“网络和Internet设...
- 电脑如何调出任务管理器(电脑如何调出任务管理器快捷键)
-
在Windows操作系统中,可以通过以下方法调出任务管理器:使用快捷键:按下“Ctrl+Shift+Esc”快捷键组合,即可快速打开任务管理器。使用组合键:按下“Ctrl+Alt+...
- win732位怎么还原系统(win732位gho)
-
系统安装失败,在以前的系统没有备份的情况下,是不能恢复的。只要诺顿开始运行,,不管进度条在什么位置,原系统都被格式化。如果有备份文件,那么方法是:1、打开系统备份还原软件:2、点击浏览,找到备份文件,...
- 电脑装什么杀毒软件(电脑装什么杀毒软件最安全)
-
好用的电脑杀毒软件,目前比较知名的有360杀软,腾讯电脑管家,金山毒霸,瑞星等杀毒软件,至于哪一个更好用,就看你自己的习惯了,我个人觉得360比较让人放心一些,这些年也一直用着360,比较安全有保证,...
- u盘uefi是什么意思(u盘用uefi模式启动)
-
u盘启动盘是指在U盘里安装PE版的操作系统后,把系统设置成从U盘启动,然后电脑开机就从U盘开始重装系统。UEFI,全称“统一的可扩展固件接口”,是一种详细描述类型接口的标准。这种接口用于操作系统自动...
- 天猫积分兑换根本抢不到(2021天猫积分兑换根本抢不到)
-
因为天猫积分的东西是有限的,但是很多人想要它们。如果你想抢到它,你最好注意启动秒杀的时间,在你启动倒计时时做好准备,并立即点击交换验证码,然后点击确认。一般最慢的时间是十秒内甚至四五秒内下单,五分钟内...
- win10任务管理器未响应(win10任务管理器没反应)
-
未响应这种情况应该是:1、说明程序是正在运行,但由于是系统运行内存不足,或者病毒、垃圾等造成的系统卡顿了。2、可以尝试重启系统、杀毒、清理垃圾即可。解决方法一:双击“此电脑”我的电脑的时候,出现资源管...
-
- 新电脑装win7进不了系统(新电脑安装win7系统启动不了)
-
解决方法:1、开机按F8,选择“最好一次正确配置”尝试修复。2、开机按F8,选择“安全模式”尝试修复。3、如果方法1,2不能修复,通过系统还原或者重新安装系统修复。二、如果软件无法修复,仍然无法启动,那么就是硬件故障原因造成的。比如硬盘、主...
-
2025-12-25 21:55 liuian
-
- 台式键盘锁住了打不了字怎么解锁
-
1.找到在键盘上靠左侧的位置,有一个fn的键,按住fn键。2.然后找到键盘最上面f8的键,把fn和f8一起按住,即可完成操作。3.然后此时看到键盘已经解除锁定,就可以可以正常输入了,这样就完成了键盘的解锁操作。...
-
2025-12-25 21:05 liuian
- 怎么超频显卡(显卡怎么超频使用)
-
显卡超频犯法如下:1、首先是显卡体质的检测,如果不知道显卡的体质,盲目加电压或者频率很容易导致超频的失败,检测显卡体质需要用到软件超频和拷机软件。2、接下来是BIOS准备阶段,用户可以选择从现有显卡提...
- 自动关机怎么设置win10指令(win10设置自动关机代码)
-
1最简单的方法是通过系统自带的计划任务来设置自动开关机。2打开‘任务计划程序’,选择‘创建基本任务’,按照提示完成设置,可以选择定时执行或在特定条件下执行。3另外也可以通过第三方软件来实现自动开...
- 一周热门
- 最近发表
- 标签列表
-
- python判断字典是否为空 (50)
- crontab每周一执行 (48)
- aes和des区别 (43)
- bash脚本和shell脚本的区别 (35)
- canvas库 (33)
- dataframe筛选满足条件的行 (35)
- gitlab日志 (33)
- lua xpcall (36)
- blob转json (33)
- python判断是否在列表中 (34)
- python html转pdf (36)
- 安装指定版本npm (37)
- idea搜索jar包内容 (33)
- css鼠标悬停出现隐藏的文字 (34)
- linux nacos启动命令 (33)
- gitlab 日志 (36)
- adb pull (37)
- python判断元素在不在列表里 (34)
- python 字典删除元素 (34)
- vscode切换git分支 (35)
- python bytes转16进制 (35)
- grep前后几行 (34)
- hashmap转list (35)
- c++ 字符串查找 (35)
- mysql刷新权限 (34)
