2.2算法的概念及描述 (精品课件),算法导论2.2-2
Yyds干货库存
写在前面：本系列文章旨在复习算法刷题常用的基本算法和数据结构，用详细的图例进行讲解，总结相应的代码模板，结合实例，达到最佳的学习效果。本专栏面向零基础算法，但有一定C基础知识的学习者。如果C基础不扎实，请参考：10分钟快速复习C语法，进行语法复习。
本文已收录于算法基础系列专栏：算法基础课程免费订阅，持续更新。
高精度加法适用于C，java，python。不存在这个问题，因为java有一个很大的整数类，python自带的，默认数字是无限的。
分类：
一个数量级10^6A-B数量级10^6A *一个数量级A 10 6，a 10000 a/一个数量级A 10 6，a10000。大整数的存储其实就是把长数字的每一位都存储在数组里，而且是逆序存储。
逆向存储的原因：
在一个数组中，如果是顺序存储的，那么在生成进位时，在数组a[0]的头之前添加元素是非常不方便的，后面的元素需要依次后移。但如果是逆序存储，可以直接加进位。
计算过程让我们先来看看我们是如何做普通加法的：
接下来，我们对其进行抽象。
对于其中一个，我们列出以下公式：
示例：高精度加法给定两个正整数(不包括前导零)，计算它们的和。
输入格式
有两行，每行包含一个整数。
输出格式
总共一行，包括要求的总数。
数据范围
1整数长度100000
12
23
输出样本：
35
模板#包含iostream
#包含矢量
使用命名空间std
//函数是计算数组表示的整数A和数组表示的整数B
向量整数加法(向量整数A，向量整数B)
{
if (A.size() B.size())返回add(B，A)；
向量整数
int t=0；//进位
for(int I=0；I a . size()；我)
{
t=A[I]；
if(I B . size())t=B[I]；
c . push _ back(t % 10)；
t/=10；
}
//最后看看最高位有没有1。如果是1，就按进去。
if(t)c . push _ back(t)；
返回C；
}
int main()
{
字符串a，b；
向量int A，B；
CIN a b；
for(int I=a . size()-1；I I-)a . push _ back(a[I]--0 )；
for(int I=b . size()-1；I I-)b . push _ back(b[I]--0 )；
auto C=add(A，B)；
for(int I=c . size()-1；I I-)cout C[I]；
cout endl
返回0；
}
模板描述
这个模板被递归调用。
向量整数加法(向量整数A，向量整数B)
{
if (A.size() B.size())返回add(B，A)；
向量整数
int t=0；//进位
for(int I=0；I a . size()；我)
{
t=A[I]；
if(I B . size())t=B[I]；
c . push _ back(t % 10)；
t/=10；
}
//最后看看最高位有没有1。如果是1，就按进去。
if(t)c . push _ back(t)；
返回C；
}
这个模板也可以用另一种方式编写。
向量整数加法(向量整数A，向量整数B)
{
向量整数
int t=0；//进位
for(int I=0；I a . size() I b . size()；我)
{
if(I A . size())t=A[I]；
if(I B . size())t=B[I]；
c . push _ back(t % 10)；
t/=10；
}
//最后看看最高位有没有1。如果是1，就按进去。
if(t)c . push _ back(t)；
返回C；
}
高精度减法整数的存储同上。
这里的计算过程以下面的公式为例
再把它抽象出来，形成一个形式。
由此，我们可以列出下面的公式
先判断A和B的关系，如果A大于B，正常加减，否则计算差的负数。
然后分别判断每一位的大小，计算是否需要进位。
例：高精度减法给定两个正整数(不含前导零)，计算它们的差，计算结果可能是负数。
输入格式
有两行，每行包含一个整数。
输出格式
总共一行，包括所需的差异。
数据范围
1整数长度 10 5
输入样本：
32
11
输出样本：
21
模板#包含iostream
#包含矢量
使用命名空间std
//判断是否有A B
布尔cmp(向量整型A，向量整型B)
{
//首先判断两个数的比特大小。
if (A.size()！=B.size())返回a . size()b . size()；
for(int I=a . size()-1；我我-)
如果(A[i]！=B[i])
return A[I]B[I]；
返回true
}
向量int sub(向量int A，向量int B)
{
向量整数
for (int i=0，t=0；I a . size()；我)
{
t=A[I]-t；
//首先判断下面的B[i]是否存在。
if(I B . size())t-=B[I]；
//这里是(t 10)% 10。如果t是0-9，就会抵消掉。如果t小于0，则相当于10次借款。
c . push _ back((t 10)% 10)；
//t小于0，表示借用，所以标记为1。
if(t 0)t=1；
否则t=0；
}
//删除前导0
while(c . size()1 c . back()==0)c . pop _ back()；
返回C；
}
int main()
{
字符串a，b；
向量int A，B；
CIN a b；
for(int I=a . size()-1；I I-)a . push _ back(a[I]--0 )；
for(int I=b . size()-1；I I-)b . push _ back(b[I]--0 )；
向量整数
if (cmp(A，B)) C=sub(A，B)；
else C=sub(B，A)，cout -；
for(int I=c . size()-1；I I-)cout C[I]；
cout endl
返回0；
}
高精度乘法存储同上。
这里列出了计算公式的通式。
与常见的计算类似，每个位分别考虑当前数的进位和余数。
当前位：C_0=(A_0 * B_1 B_0 t) \% 10
进位：t=(A_0 * B_1 B_0)/10
注意：这里把B看成一个整体，和一般乘法不一样。b这样便于计算和存储(存成int就行了)。
例：高精度减法给定两个正整数(不含前导零)，计算它们的差，计算结果可能是负数。
输入格式
有两行，每行包含一个整数。
输出格式
总共一行，包括所需的差异。
数据范围
1整数长度 10 5
输入样本：
32
11
输出样本：
21
模板#包含iostream
#包含矢量
使用命名空间std
向量整数乘法(向量整数A，整数b)
{
向量整数
//进位
int t=0；
for(int I=0；I a . size() t；我)
{
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()；
返回C；
}
int main()
{
字符串a；
int b；
CIN a b；
向量整数
for(int I=a . size()-1；I I-)a . push _ back(a[I]--0 )；
auto C=mul(A，b)；
for(int I=c . size()-1；i i - ) printf(%d ，C[I])；
返回0；
}
高精度除法的计算过程高精度除法的一般公式如下：
模拟求解除法的过程，高精度除法算法可以设计如下：
起始余数r是0。
r=r * 10a _ 3C _ 3=(r * 10a _ 3)/b；R=r \% b例：高精度除法给定两个非负整数(不含前导0) A，B，请计算A/B的商和余数。
输入格式
有两行。第一行包含整数A，第二行包含整数b。
输出格式
有两行，第一行输出商，第二行输出余数。
数据范围
1A 100001 B 10000b的长度不能为0。
输入样本：
七
2
输出样本：
三
一个
模板# include bits/stdc . h
使用命名空间std
向量整数除法(向量整数A，整数b，整数r)
{
向量整数
r=0；
//其中r是余数
for(int I=a . size()-1；我我-)
{
//将下一位数字加到余数*10上，输出标准数字为r/b，然后继续取余数r。
r=r * 10 A[I]；
c .推回(r/b)；
r %=b；
}
//因为除法存储是按从高到低的顺序，但一般输出是按从低到高的逆序，所以这里反过来。
reverse(C.begin()、c . end())；
while(c . size()1 c . back()==0)c . pop _ back()；
返回C；
}
int main()
{
字符串a；
int b；
CIN a b；
向量整数
for(int I=a . size()-1；I I-)a . push _ back(a[I]--0 )；
int r；
auto C=div(A，b，r)；
for(int I=c . size()-1；i i - )printf(%d ，C[I])；
cout endl r endl
返回0；
}
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。