算法笔记——高精度算法(附源码)

简介: 📖作者介绍:22级树莓人(计算机专业),热爱编程<目前在c++阶段,因为最近参加新星计划算法赛道(白佬),所以加快了脚步,果然急迫感会增加动力>——目标Windows,MySQL,Qt,数据结构与算法,Linux,多线程,会持续分享学习成果和小项目的📖作者主页:热爱编程的小K📖专栏链接:算法笔记🎉欢迎各位→点赞👏 + 收藏💞 + 留言🔔​💬总结:希望你看完之后,能对你有所帮助,不足请指正!共同学习交流 🐾————————————————版权声明:本文为CSDN博主「热爱编程的小K」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。

文章目录

一、高精度算法的应用场景

二、高精度加法

1、思路

2、算法

3、模板展示

4、习题练习

1、题目:Acwing 791. 高精度加法

输入格式

输出格式

数据范围

输入样例:

输出样例:

2、代码展示

三、高精度减法

1、思路

2、算法

3、模板展示

4、习题练习

1、题目 Acwing 792. 高精度减法

输入格式

输出格式

数据范围

输入样例:

输出样例:

2、代码展示

四、高精度乘法

1、题目 Acwing 793. 高精度乘法

输入格式

输出格式

数据范围

输入样例:

输出样例:

2、代码展示

五、高精度除法

1、模拟与算法

2、题目 Acwing 794. 高精度除法

输入格式

输出格式

数据范围

输入样例:

输出样例:

3、代码展示

一、高精度算法的应用场景

利用计算机进行数值计算,有时会遇到这样的问题:有些计算要求精度高,希望计算的数的位数可达几十位甚至几百位,虽然计算机的计算精度也算较高了,但因受到硬件的限制,往往达不到实际问题所要求的精度。我们可以利用程序设计的方法去实现这样的高精度计算。这里不包括java和Python选手哈,当输入很大的时候scanf比cin效率更高

二、高精度加法

1、思路

我们先手动模拟一下加法

3b6a7d64c7ea44b082ba3e736bd4b1cf.png

先个位相加:6+6=12,所以个位的结果得2,向十位进1

再十位相加:6+9+1(进位)=16,所以十位的结果得6,向百位进1

最后再百位相加:5+1(进位)=6,所以百位的结果得6,进位为0

2、算法

第一步:需要把两个大整数倒序过来储存到一个数组中,因为我们都知道加法是从低位开始加的

第二步:判断较长的数字,放在前面,因为循环条件需要

第三步:开始计算A[i]+B[i]+t这里t表示进位,前面的和表示为sum,则当前的位的结果表示为sum%10,进位更新t/=10

循环结束后:判断t为不为0,如果不为0,需要把t存到和数组中(这种情况就是和比最长加数还要长的情况)

3、模板展示

vector<int> add(vector<int> &A, vector<int> &B)

{

   if (A.size() < B.size()) return add(B, A);

   //为了方便计算,让A中保存较长的数字, B中保存较短的数字

   vector<int> C;//保存结果的数组

   int t = 0;//进位,开始时是0

   for (int i = 0; i < A.size(); i ++ )//依次计算每一位

   {

       t += A[i];//加上 A 的第 i 位上的数字

       if (i < B.size()) t += B[i];//加上 B 的第 i 位上的数字

       C.push_back(t % 10); //C 中放入结果

       t /= 10;//t 更新成进位

   }

   if (t) C.push_back(t);//最后如果进位上有数,放进结果数组

   return C;//返回结果

}

4、习题练习

1、题目:Acwing 791. 高精度加法

给定两个正整数(不含前导 0),计算它们的和。

输入格式

共两行,每行包含一个整数。

输出格式

共一行,包含所求的和。

数据范围

1≤整数长度≤100000

输入样例:

1  2

2  3

输出样例:

1  35

2、代码展示

#include<iostream>

#include<string>

#include<vector>

using namespace std;

vector<int> add(vector<int>&A,vector<int>&B)

{

   vector<int> C;

   if(A.size()<B.size()) return add(B,A);//大的放前面,判断

   int t=0;//进位

   for(int i=0;i<A.size();i++)

   {

       t+=A[i];

       if(i<B.size()) t+=B[i];

       C.push_back(t%10);

       t/=10;

   }

   if(t) C.push_back(t);

   return C;

 

}

int main()

{

   string a,b;

   vector<int> A,B;

   cin>>a>>b;

   //倒序存放

   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');

   auto C=add(A,B);

   for(int i=C.size()-1;i>=0;i--) cout<<C[i];

   cout<<endl;

   return 0;

}

✨三、高精度减法

1、思路

一样的我们先模拟一下减法竖式

96feab9b34fc45368c5cb9cb5ffab78a.png

和高精度加法差不多,值得注意的是

减法的借位处理

相减为负数的处理

前导0的处理

2、算法

对于两个减数的处理t = A[i] - B[i] - t; 可以拆为 t = A[i] - t如果B[i]合法,再t -= B[i] 这么两步来做,这里的t表示借位

两数对应位置相减后放入的应为(t+10)%10,解释:t>0时,对应位的结果就为t,t<0时,对应结果为t-10,借位

相减为负数的处理:加一个判断大小的函数,大的当减数,小的当被减数,为负的情况最后再输出的时候再先输出一个负号

3、模板展示

vector<int> sub(vector<int>&A,vector<int>&B)

{

   vector<int> C;

   int t=0;

   for(int i=0;i<A.size();i++)

   {

       t=A[i]-t;

       if(i<B.size()) t-=B[i];

       C.push_back((t+10)%10);

       //借位处理

       if(t<0) t=1;  

       else t=0;

   }

   //前导0处理

   while(C.size()>1&&C.back()==0) C.pop_back();

   return C;

}

 4、习题练习

1、题目 Acwing 792. 高精度减法

给定两个正整数(不含前导 00),计算它们的差,计算结果可能为负数。

输入格式

共两行,每行包含一个整数。

输出格式

共一行,包含所求的差。

数据范围

1≤整数长度≤10的5次方

输入样例:

1  32

2  11

输出样例:

1  21

2、代码展示

#include <iostream>

#include <vector>

using namespace std;

bool cmp(vector <int> &A,vector <int> &B)

{  

   // 判断是否A > B

   if(A.size() != B.size()) return A.size() > B.size();  

   // 如果A、B长度不相同,长度长的那个数大

   for(int i = A.size() - 1;i >= 0;i --)

   {  

// 否则就要从最高位开始看(因为执行这个函数前,A和B数组都已经倒序,所以这里要从后往前看)

       if(A[i] != B[i]) return A[i] > B[i];

       // 如果A的当前位和B的当前位不相等,当前位大的更大

   }

   return true; // 如果A、B数组都相等,这里可以直接返回true,当然也可以直接输出0

}

vector <int> sub(vector <int> &A,vector <int> &B)

{  // A - B

   int t = 0;                // 每一位上相减得到的数

   vector <int> C;           // 最后的答案

// 遍历一遍,和高精度加法不一样的是,只要遍历完A就行了,因为这里A肯定比B长

   for(int i = 0;i < A.size();i ++)

   {  

       t = A[i] - t;// t要等于A的当前位减掉自己,因为上一位有可能出现借位的情况

 if(i < B.size()) t -= B[i];  // 如果没有遍历完B,那么t减掉B的当前位

  C.push_back((t + 10) % 10);  

     

       // 更新C数组

       // 这里如果没有借位,(t + 10) % 10就刚好等于t

       // 如果这里有借位,(t + 10) % 10就会借一个10下来

     

       if(t < 0) t = 1;  

// 如果t < 0,说明不够减,需要借位,把t赋值为1,就是在下一次执行中,A的当前位会减掉t

       else t = 0;      // 否则够减,赋值为0,不用借位

   }

   while(C.size() > 1 && C.back() == 0) C.pop_back(); // 删除前导0

   return C; // 返回答案

}

int main(){

   string a,b;    // 两个数,因为很大,所以用string来存

   cin>>a>>b;   // 读入

   vector <int> A,B;   // 两个数,因为减法是从最低位开始减,我们可以把两个数倒过来

   for(int i = a.size() - 1;i >= 0;i --) A.push_back(a[i] - '0');

   // 把a数组到过来存入A,记得a是string类型的数组,要减去'0'让它变成数字

   for(int i = b.size() - 1;i >= 0;i --) B.push_back(b[i] - '0');  

   // 把b数组倒过来存入B

   if(cmp(A,B))

   {  

       // 如果A > B

       auto C = sub(A,B); // 那么可以直接相减

       for(int i = C.size() - 1;i >= 0;i --) printf("%d",C[i]);  

       // 最后因为C是倒着的,需要反向输出

   }

   else

   {   // 否则A < B,需要计算-(B - A)

       auto C = sub(B,A); // 计算B - A

       printf("-"); // 给前面加上一个负号

       for(int i = C.size() - 1;i >= 0;i --) printf("%d",C[i]); // 反向输出C数组

   }

   return 0;

}

四、高精度乘法

高精度乘法就没什么好说的,直接上习题,代码有讲解

1、题目 Acwing 793. 高精度乘法

给定两个非负整数(不含前导 0)A和 B,请你计算 A×B 的值。

输入格式

共两行,第一行包含整数 A,第二行包含整数 B。

输出格式

共一行,包含 A×B 的值。

数据范围

1≤A的长度≤100000

0≤B≤100000

输入样例:

1  2

2  3

输出样例:

1  6

2、代码展示

#include<iostream>

#include<string>

#include<vector>

using namespace std;

vector<int> mul(vector<int>&A,int b)

{

   vector<int> C;

   int t=0;//进位

   //A的长度一定比b长,而且这里加了`||t`

   for(int i=0;i<A.size()||t;i++)

   {

       if(i<A.size()) t+=A[i]*b;

       C.push_back(t%10);

       t/=10;

   }

   //去除前导0

   while(C.size()>1&&C.back()==0) C.pop_back();

   return C;

}

int main()

{

   string a;

   int b;

   cin>>a>>b;

   vector<int> A;

   //倒序

   for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');

   auto C=mul(A,b);

   for(int i=C.size()-1;i>=0;i--) cout<<C[i];

   return 0;

}

五、高精度除法

1、模拟与算法

我们先模拟一下

ace579f770d8422c961d309306b957a9.png需要注意的就两点一个:余数r传入函数的时候一定要传入引用,因为要修改并返回r的值

第二个:上一位的余数乘以10,再加上当前位上的数就是余数

2、题目 Acwing 794. 高精度除法

给定两个非负整数(不含前导 00) A,B,请你计算 A/B的商和余数

输入格式

共两行,第一行包含整数 A,第二行包含整数 B。

输出格式

共两行,第一行输出所求的商,第二行输出所求余数。

数据范围

1≤A的长度≤100000

1≤B≤10000

B不一定不为 0

输入样例:

1  7

2  2

输出样例:

1  3

2  1

3、代码展示

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

vector <int> div(vector <int> &A,int b,int &r)

{  

   // 取r的地址符,是为了更改r的值,方便后面输出余数

   vector <int> C; // 答案

   r = 0; // 余数

   for(int i = A.size() - 1;i >= 0;i --)

   {  

       // 从最高位开始处理

       r = r * 10 + A[i]; // 上一次的余数乘10,再加上当前位上的数,就是被除数

       C.push_back(r / b); // 往C里压入这个被除数除b

       r %= b; // 计算余数

   }

   reverse(C.begin(),C.end());  

   // 因为除法运算中从高位开始计算,而前导0都在顶部而不是底部,所以要翻转过来

   while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去除前导0

   return C; // 返回答案

}

int main()

{

   string a;

   int b;

   cin>>a>>b;

   vector <int> A;

   for(int i = a.size() - 1;i >= 0;i --) A.push_back(a[i] - '0'); // 倒序

   int r;

   auto C = div(A,b,r); // 答案

   for(int i = C.size() - 1;i >= 0;i --) cout<<C[i];

   cout<<endl<<r<<endl;

   return 0;

}

版权声明:本文为CSDN博主「热爱编程的小K」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。

原文链接:https://blog.csdn.net/qq_72157449/article/details/129967115

相关文章
|
28天前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
59 1
|
28天前
|
算法 索引
❤️算法笔记❤️-(每日一刷-141、环形链表)
❤️算法笔记❤️-(每日一刷-141、环形链表)
44 0
|
28天前
|
算法
【❤️算法笔记❤️】-(每日一刷-876、单链表的中点)
【❤️算法笔记❤️】-(每日一刷-876、单链表的中点)
41 0
|
2天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
24 8
|
2天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
20 7
|
27天前
|
算法 API 计算机视觉
人脸识别笔记(一):通过yuface调包(参数量54K更快更小更准的算法) 来实现人脸识别
本文介绍了YuNet系列人脸检测算法的优化和使用,包括YuNet-s和YuNet-n,以及通过yuface库和onnx在不同场景下实现人脸检测的方法。
30 1
|
27天前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
50 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
28天前
|
算法
❤️算法笔记❤️-(每日一刷-160、相交链表)
❤️算法笔记❤️-(每日一刷-160、相交链表)
16 1
|
27天前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
12 0
|
28天前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
29 0