高精度算法详解(加减乘除+高精度案例)

大家好，欢迎来到IT知识分享网。

什么是高精度算法?

        高精度通常指的是在计算机中对超过基本数据类型表示范围的大整数或者小数进行精确计算的能力。在计算机中，通常使用固定长度的数据类型（比如int、long、float、double等）来表示数字，这些数据类型的表示范围是有限的，超出这个范围的数字就无法被准确表示和计算，这就需要使用高精度计算。

        精度计算经常用于需要对非常大或者非常精确的数字进行计算的场景，比如在密码学中的大素数运算、金融领域的精确计算、科学计算中的精确浮点数运算等。为了实现高精度计算，通常需要设计特定的数据结构和算法来表示和计算这些超出固定数据类型范围的数字.

        算法应用范围: 高精度计算广泛应用于算法设计中，包括动态规划、数论、组合数学、几何算法等领域。许多经典算法问题，如大整数乘法、大整数除法、高精度加减法等都需要高精度计算来解决。

在所有代码中,我都加上了详细的注释,如果有算法设计思路看不懂的同学,可以结合着代码一起学习,如果还有不会的地方,可以直接在评论区问我哦

最后,一定要看代码哦,代码才是最重要的

高精度加法

算法设计思路:

• 从低位到高位，逐位将对应位的数字相加，并考虑前一位的进位。
• 将相加的结果与进位相加，得到当前位的最终结果，并更新下一位的进位。
• 将得到的最终结果记录下来，并继续进行上述步骤，直到所有位都被处理完毕。

 高精度加法的设计思路主要包括以下几个关键步骤：

1. 输入处理 – 将输入的两个高精度数以字符串的形式接收。

2.将字符串拆解为一个个数字存到int数组中

3. 逐位相加 – 从低位（字符串的末尾）开始，逐位将两个数的对应位数字相加，并加上前一位的进位。 – 计算当前位的和，并计算进位。

4. 处理进位 – 如果当前位的和大于等于 10 ，则需要向高位进位。

5. 结果处理 – 去除结果前面可能存在的多余的 0 。 

以下是高精度加法的算法实现:

/* Author:XYu12301 */ #include<bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' int main() { string s1,s2; // 用于存储输入的两个字符串，例如 "123" 和 "1456" int a[505]={0},b[505]={0},c[505]={0}; // 三个整数数组，用于存储转换后的数字 cin>>s1>>s2; // 输入两个字符串 int la = s1.length(),lb = s2.length(); // 获取两个字符串的长度 // 将字符串 s1 转换为逆序存储在数组 a 中 for(int i=0;i<la;i++) { a[la-i-1]=s1[i]-'0'; // 实现数字的逆序存储，如 "123" 存储为 321 } // 将字符串 s2 转换为逆序存储在数组 b 中 for(int i=0;i<lb;i++) { b[lb-i-1]=s2[i]-'0'; // 实现数字的逆序存储，如 "1456" 存储为 6541 } int l =max(la,lb); // 确定结果数组的最大长度 // 进行逐位相加，并处理进位 for(int i=0;i<l;i++) { c[i] += a[i] + b[i]; // 当前位相加 c[i+1] = c[i]/10; // 计算进位 c[i] %= 10; // 保留当前位的值 } // 去除结果前面的前导 0 while(c[l]==0&&l>0)l--; /*去除前置 0 可以简化数字的表示，减少不必要的位数。 在高精度加法中，通常会涉及到对两个数字进行逐位相加的操作，如果其中一个数字有大量的前置 0，会导致计算过程变得复杂和冗长。*/ // 输出结果 for(int i=l;i>=0;i--) { cout<<c[i]; // 逆序输出相加的结果 } return 0; }

 下面是luogu一道经典的高精度加法的案例,看懂的小伙伴可以自己尝试一下哦

 P1601 A+B Problem（高精)

高精度减法

高精度减法的设计思路和加法的非常相似

1. 对齐操作：首先要对两个数字进行对齐，确保两个数字的位数相同。如果两个数字位数不同，需要在较短的数字前面补0，使它们的位数相等，这样才能进行逐位相减。
2. 逐位相减：从最低位开始，逐位相减。从最低位开始，将第一个数字的对应位数减去第二个数字的对应位数，并记录结果。如果减法的结果为负数，需要向高位借位。
3. 处理借位：如果某一位的减法结果为负数，需要向高位借位。借位的处理需要考虑进位和借位相互影响的情况，确保高位的减法结果正确。
4. 去除前导零：在得到减法结果后，需要去除结果中的前导零，使结果更加规范和紧凑

关键步骤

1. 首先要判断两数的大小,用数字大的减数字小的

2.将减数与被减数逆序用int数组接收

3.逐位相减,处理进位

4.去除前置0

以下是高精度减法的C++代码

/* Author:XYu12301 */ #include<bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' // 比较两个字符串表示的数字大小的函数 bool pd(string s1,string s2) { int l1 = s1.length(),l2=s2.length(); // 如果长度不同，长度长的数字大 if(l1!=l2) return l1>l2; // 如果长度相同，逐位比较 for(int i=0;i<(l1>l2?l1:l2);i++) { if(s1[i]!=s2[i])return s1[i]>s2[i]; } return 1; } int main() { string s1,s2,s3; // 用于存储输入的三个字符串 int a[10090]={0},b[10090]={0},c[10090]={0}; bool flag = true; // 标记是否为正数 cin>>s1>>s2; // 如果 s1 小于 s2，进行交换 if(!pd(s1,s2)) { flag = false; s3=s1; s1=s2; s2=s3; } int la = s1.length(),lb = s2.length(); // 将 s1 转换为逆序存储在数组 a 中 for(int i=0;i<la;i++) { a[la-i-1]=s1[i]-'0'; } // 将 s2 转换为逆序存储在数组 b 中 for(int i=0;i<lb;i++) { b[lb-i-1]=s2[i]-'0'; } int l =max(la,lb); // 逐位相减，处理借位 for(int i=0;i<l;i++) { if(a[i]<b[i]) { a[i+1]--; a[i]+=10; } c[i] = a[i]-b[i]; } // 去除结果前面的前导 0 while(c[l]==0&&l>0)l--; // 如果是负数，输出负号 if(!flag)cout<<"-"; // 输出结果 for(int i=l;i>=0;i--) { cout<<c[i]; } return 0; }

下面是luogu一道经典的高精度减法的案例,看懂的小伙伴可以自己尝试一下哦 

P2142 高精度减法

高精度乘法

1. 逐位相乘：从被乘数的最低位开始，逐位与乘数相乘，得到部分乘积。需要记录每一步的部分乘积，并考虑进位的情况。
2. 部分乘积相加：得到部分乘积后，需要将所有的部分乘积相加，得到最终的乘积结果。在相加的过程中，需要考虑进位的情况。
3. 处理进位：在逐位相乘和部分乘积相加的过程中，需要考虑进位的情况。确保进位的正确处理，不会遗漏或错误处理进位情况。
4. 处理小数部分：如果需要进行高精度乘法，可能会涉及到小数部分的处理。在进行乘法操作后，需要继续处理小数部分，直到达到指定的精度要求。

 关键步骤:

1.将乘数用字符串接收,并拆分放入int数组中

2.模拟乘法步骤,找到算法的关键

• 这里的关键是找到两数相乘时的规律:c[i+j] += a[i] * b[j]

3.处理进位

4.删除前导零

/* Author:XYu12301 */ #include<bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' int main() { string s1,s2; // 用于存储输入的两个字符串，例如 "123" 和 "1456" int a[505]={0},b[505]={0},c[505]={0}; // 三个整数数组，用于存储转换后的数字和计算结果 cin>>s1>>s2; // 输入两个字符串 int la = s1.length(),lb = s2.length(); // 获取两个字符串的长度 // 将字符串 s1 转换为逆序存储在数组 a 中 for(int i=0;i<la;i++) { a[la-i-1]=s1[i]-'0'; // 实现数字的逆序存储，如 "123" 存储为 321 } // 将字符串 s2 转换为逆序存储在数组 b 中 for(int i=0;i<lb;i++) { b[lb-i-1]=s2[i]-'0'; // 实现数字的逆序存储，如 "1456" 存储为 6541 } int l = la + lb; // 结果数组的最大长度 // 进行高精度乘法运算 for(int i=0;i<la;i++) // 遍历第一个数的每一位 { for(int j=0;j<lb;j++) // 遍历第二个数的每一位 { c[i+j]+=a[i]*b[j]; // 对应位相乘并累加 c[i+j+1]+=c[i+j]/10; // 处理进位 c[i+j]%=10; // 保留当前位的值 } } // 去除结果前面的前导 0 while(c[l]==0&&l>0)l--; // 输出结果 for(int i=l;i>=0;i--) { cout<<c[i]; // 逆序输出乘法结果 } return 0; }

下面是luogu一道经典的高精度乘法的案例,看懂的小伙伴可以自己尝试一下哦  

P1919 【模板】高精度乘法 | A*B Problem 升级版

高精度除法

高精度除法(高精度/低精度) 

高精度除法分为两种情况:一种时高精度除低精度,另一种是高精度除高精度,我们先来介绍比较简单的高精度除低精度

高精度除低精度算法的实现可以模拟竖式除法的过程，具体步骤如下：

1. 输入处理：将高精度的被除数以字符串形式接收，并将其各位数字转换为整数存储在数组中。同时，获取低精度的除数。
2. 初始化相关变量：设置一个变量用于存储余数，并初始化为0。
3. 逐位计算：从被除数的最高位开始，依次进行以下操作:

•  将余数乘以10，并加上当前位的数字，得到当前被除数部分。
• 用当前被除数部分除以除数，得到商的当前位，并存储在结果数组中。
• 将当前被除数部分除以除数后的余数更新为新的余数。

1. 去除前导零：在得到的结果数组中，可能存在前导零，需要通过循环去除这些前导零。
2. 输出结果：输出去除前导零后的商。

/* Author:XYu12301 */ #include<iostream> #include<cstring> using namespace std; #define ll long long char s[5000]; ll b,c[5000],x,a[5000],la,lc; int main(){ cin>>s>>b; // 读入被除数字符串 s 和除数 b la = strlen(s); // 获取被除数字符串的长度 for(int i = 1; i <= la; i++){ a[i] = s[i-1]-'0'; // 将字符串形式的被除数一位一位转换为数字并存入 a 数组 } for(int i = 1; i <= la; i++){ // 计算当前位的商，并更新余数 c[i] = (x*10 + a[i])/b; x = (x*10 + a[i])%b; } lc = 1; while(c[lc]==0 && lc<la)lc++; // 找到结果中第一个非零位的位置，删除前导 0 for(int i = lc; i <= la; i++)cout<<c[i]; // 输出计算得到的商 return 0; }

下面是luogu一道经典的高精度除法的案例,看懂的小伙伴可以自己尝试一下哦   

 P1480 A/B Problem

高精度除法(高精度除高精度)

高精度除高精度的算法可以通过模拟竖式除法的过程来实现，一般步骤如下：

1. 输入：将两个高精度数以字符串形式读入。
2. 初始化：将字符串形式的数转换为整数数组进行存储，并确定被除数和除数的位数。
3. 试除与减法模拟：从被除数的高位开始，逐位与除数进行比较和计算。通过使用高精度减法来模拟试商的过程。每次用被除数的一部分减去一个适当倍数的除数，减的次数即为商的相应位的值。
   • 将除数移动和被除数对齐，位数不够时补0。
   • 利用被除数减去除数，一直减到被除数小于除数，减的次数就是“试商”的结果。
   • 重复上述步骤，一直到被除数和除数的位数相等为止。
4. 处理商和余数：记录每次试商的结果，得到商的各位数字。同时，计算减法操作后的剩余部分作为新的被除数，继续进行下一位的试除。
5. 去除前导零：得到的商可能包含前导零，需要将其去除。
6. 输出结果：输出商和最终的余数。

高精度除高精度的过程十分复杂,我将讲解放在代码注释中,每一行都有详细的注释

/* Author:XYu12301 */ #include <iostream> #include <string> using namespace std; // 比较两个高精度数组 a 和 b 的大小 // len 表示数组的有效长度 int compare(int* a, int* b, int len) { // 从数组的最高位开始比较 for (int i = len - 1; i >= 0; i--) { // 如果当前位 a 大于 b，返回 1 if (a[i] > b[i]) return 1; // 如果当前位 a 小于 b，返回 -1 if (a[i] < b[i]) return -1; } // 如果所有位都相等，返回 0 return 0; } // 复制数组 b 到数组 p 中，从位置 m 开始 void copyArr(int* p, int* q, int m) { // 遍历数组 b 的每一位 for (int i = 1; i <= q[0]; i++) { // 将 b 的当前位复制到 p 的指定位置 p[i + m - 1] = q[i]; } // 更新 p 的有效长度 p[0] = q[0] + m - 1; } // 高精度减法 void sub(int* a, int* b) { // 比较两个数组的大小 int flag = compare(a, b); // 如果两个数相等 if (flag == 0) { // 设置结果数组的有效长度为 1，值为 0 a[0] = 1; a[1] = 0; return; } // 如果 a 大于 b if (flag == 1) { // 从最高位开始处理 for (int i = 1; i <= a[0]; i++) { // 如果当前位 a 小于 b，需要借位 if (a[i] < b[i]) { a[i] += 10; a[i + 1]--; } // 计算相减的结果 a[i] -= b[i]; } // 去除结果前面的无效 0 while (a[a[0]] == 0 && a[0] > 1) a[0]--; } } // 高精度除以高精度 void div(int* a, int* b, int* c) { // 初始化结果数组 c 的值为 0 memset(c, 0, sizeof(int) * (a[0] + 1)); // 计算结果数组 c 的有效长度 c[0] = a[0] - b[0] + 1; int tmp[205]; // 从结果数组 c 的最高位开始计算 for (int i = c[0]; i >= 1; i--) { // 初始化临时数组 tmp 为 0 memset(tmp, 0, sizeof(int) * (b[0] + 1)); // 将除数 b 复制到临时数组 tmp 的指定位置，准备与被除数的一部分进行比较 copyArr(tmp, b, i); // 当被除数 a 大于等于临时数组 tmp 时 while (compare(a, tmp) >= 0) { // 结果数组 c 的当前位加 1 c[i]++; // 被除数 a 减去临时数组 tmp sub(a, tmp); } } // 去除结果数组 c 前面的无效 0 while (c[c[0]] == 0 && c[0] > 1) c[0]--; } int main() { string a_s, b_s; int a[205] = {0}, b[205] = {0}, c[205] = {0}; cin >> a_s >> b_s; int len_a = a_s.length(); int len_b = b_s.length(); // 将输入的字符串形式的被除数转换为整数数组 a for (int i = 0; i < len_a; i++) a[len_a - 1 - i] = a_s[i] - '0'; // 将输入的字符串形式的除数转换为整数数组 b for (int i = 0; i < len_b; i++) b[len_b - 1 - i] = b_s[i] - '0'; div(a, b, c); // 输出商 for (int i = c[0]; i >= 1; i--) cout << c[i]; cout << endl; // 如果有余数 if (a[0] > 1 || a[1] > 0) { cout << "余"; // 输出余数 for (int i = a[0]; i >= 1; i--) cout << a[i]; } return 0; }

下面是一道经典的高精度除法的案例,看懂的小伙伴可以自己尝试一下哦    

 A/B problem除法(高精度)

为了加强对高精度的理解,这里我也准备了几个经典的高精度的题目

P1255 数楼梯

P1009 阶乘之和

P1249 最大乘积

P1581 A+B Problem（升级版）

D-小红的 gcd_牛客周赛 Round 51

最后制作不易,给个点赞ba