算法之详解高精度加法【算法笔记】

(我已经把CSDN当作笔记本了~…,这里语言会浅显一点不想搞得很高级的样子)
高精度是各类信息竞赛中的必会类型,高精度一般就是整数位太长,小数位太大,程序很难直接运算或表达。
直接进入正题,不磨蹭,将问题分析一点点解决。
Q1:
为什么需要高精度
c语言现有的类型无法存储,上图,看一眼即可
算法之详解高精度加法【算法笔记】
Q2:如何实现加法,通过什么实现
小学我们学过,加减乘除,对于每一位,满十进1,不满十直接相加即可。对于高精度的加法,采用的也是这个原理,我们可以通过数组来存储每一位,用数组来模拟加法,这样可以实现很大位的加法运算,下图就是原理。

算法之详解高精度加法【算法笔记】
我们可以通过三个数组来实现,第一二个存储加数,第三个存储结果。

理论实现,开始实践

首先我们要解决难点:
Q3:如何存储数组-------将每一位数组倒序存储到数组内,为什么倒序/
A3:还是看上图,个位和个位是对齐的,方便计算,假如我们第一位放最大位数,那么假如两个数最大个数不同,加法算式就会出现下面情况
1234 ·············· ---- 1234 ················· --------4321(倒序)
45···················---- 0045 ··················--------54
这样加不对········这样也可以·····················虽然这样我们看着不方便,但是程序方便

Q4:如何录入
A4:如果真的是单纯的录入数字,而采取录入到数组的话,录入的时候会遇到个问题,每位存储一个数字意味着每输入一位数字,就要按空格或者换行,否则用scanf会导致多个数字粘连起来。所以使用字符数组很方便,然后让字符数组每一位减去’0’即可。

核心代码:

//我们数组第一位不存储数,所以从i=1开始
for(itn i=1;i<=max(a,b)+1;i++)
{
		* 注意这里的加号 ,不能少,是用来计算进位的*
		c[i]  + =a[i]+b[i];//先直接加,假如这一位不需要进位,c[i]<,反之大于
		c[i+1]=c[i]/10;//现在存储的是下一位的进位,会被保存到下一位,下一位计算的时候自动被加上
		c[i]=c[i]%10;//这个很浅显易懂,假如c[i]=15,1到下一位,5留下
}

全部代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
	char s1[505],s2[505];
	int a[505]={0},b[505]={0},c[505]={0};//注意这里要赋值为0,不然可能出错
	int la,lb,lc;
	scanf("%s",s1);
	scanf("%s",s2);
	la=strlen(s1);
	lb=strlen(s2);
	for(int i=0;i<la;i++)//在这里,数组第0位被跳过了
		a[la-i]=s1[i]-'0';
	for(int i=0;i<lb;i++)
		b[lb-i]=s2[i]-'0';
	
	lc=max(la,lb)+1;
	for(int i=1;i<=lc;i++)
	{
		c[i]+=a[i]+b[i];
		c[i+1]=c[i]/10;
		c[i]=c[i]%10;
	}
	if(c[lc]==0 && lc>0)lc--;
	for(int i=lc;i>0;i--)
		printf("%d",c[i]);
	return 0;
}

这么辛苦点个

上一篇:原创-性能测试篇-2D性能测试脚本


下一篇:lc 233 数位上的1