欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 文化 > NO.57十六届蓝桥杯备战|基础算法-高精度|加减乘除|模拟竖式计算(C++)

NO.57十六届蓝桥杯备战|基础算法-高精度|加减乘除|模拟竖式计算(C++)

2025/4/1 2:53:27 来源:https://blog.csdn.net/CoderZzz6310/article/details/146506875  浏览:    关键词:NO.57十六届蓝桥杯备战|基础算法-高精度|加减乘除|模拟竖式计算(C++)

当数据的值特别⼤,各种类型都存不下的时候,此时就要⽤⾼精度算法来计算加减乘除:

  • 先⽤字符串读⼊这个数,然后⽤数组逆序存储该数的每⼀位;
  • 利⽤数组,模拟加减乘除运算的过程。
    ⾼精度算法本质上还是模拟算法,⽤代码模拟⼩学列竖式计算加减乘除的过程
P1601 A+B Problem(高精) - 洛谷

模拟⼩学「列竖式」计算「两数相加」的过程
![[Pasted image 20250325135304.png]]

  1. ⽤字符串读⼊数据;
  2. 将字符串的每⼀位拆分,逆序放在数组中;
  3. 模拟列竖式计算的过程:
    a. 对应位累加;
    b. 处理进位;
    c. 处理余数。
  4. 处理结果的位数。
#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int a[N], b[N], c[N];
int la, lb, lc;void add(int c[], int a[], int b[])
{for (int i = 0; i < lc; i++){c[i] += a[i] + b[i];c[i + 1] += c[i] / 10;c[i] %= 10;}if (c[lc]) lc++;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);string x, y; cin >> x >> y;//拆分每一位逆序放在数组中la = x.size(); lb = y.size(); lc = max(la, lb);for (int i = 0; i < la; i++) a[la - 1 - i] = x[i] - '0';for (int i = 0; i < lb; i++) b[lb - 1 - i] = y[i] - '0';//模拟加法add(c, a, b);//输出结果for (int i = lc - 1; i >= 0; i--) cout << c[i];return 0;
}
P2142 高精度减法 - 洛谷
  1. ⽤字符串读⼊数据;
  2. 判断两个数的⼤⼩,让较⼤的数在前。注意字典序vs数的⼤⼩:
    a. 位数相等:按字典序⽐较;
    b. 位数不等:按照字符串的⻓度⽐较。
  3. 将字符串的每⼀位拆分,逆序放在数组中;
  4. 模拟列竖式计算的过程:
    a. 对应位求差;
    b. 处理借位;
  5. 处理前导零。
#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int a[N], b[N], c[N];
int la, lb, lc;bool cmp(string& x, string& y)
{if (x.size() != y.size()) return x.size() < y.size();return x < y;
}void sub(int c[], int a[], int b[])
{for (int i = 0; i < lc; i++){c[i] += a[i] - b[i]; //对应位相减处理借位if (c[i] < 0){c[i + 1] -= 1;c[i] += 10;}}//处理前导0while (lc > 1 && c[lc - 1] == 0) lc--;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);string x, y; cin >> x >> y;//比大小if(cmp(x, y)){swap(x, y);cout << "-";}//拆分,逆序la = x.size(); lb = y.size(); lc = max(la, lb);for (int i = 0; i < la; i++) a[la - i - 1] = x[i] - '0';for (int i = 0; i < lb; i++) b[lb - i - 1] = y[i] - '0';//模拟减法sub(c, a, b);//输出for (int i = lc - 1; i >= 0; i--) cout << c[i];return 0;
}
P1303 A*B Problem - 洛谷

⽆进位相乘再相加:

  • 还是「列竖式」,但是每⼀位相乘的时候不考虑进位,直接把乘的结果放在对应位上;
  • 等到所有对应位置「乘完」并且「累加完」之后,「统⼀处理进位」
  1. ⽤字符串读⼊数据;
  2. 将字符串的每⼀位拆分,逆序放在数组中;
  3. 模拟⽆进位相乘再相加的过程:
    a. 对应位求乘积;
    b. 乘完之后处理进位;
    c. 处理余数;
  4. 处理前导零
#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int a[N], b[N], c[N];
int la, lb, lc;void mul(int c[], int a[], int b[])
{//无进位相乘,相加for (int i = 0; i < la; i++){for (int j = 0; j < lb; j++){c[i + j] += a[i] * b[j];        }}//处理进位for (int i = 0; i < lc; i++){c[i + 1] += c[i] / 10;c[i] %= 10;}//处理前导0while (lc > 1 && c[lc - 1] == 0) lc--;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);string x, y; cin >> x >> y;//拆分,逆序la = x.size(); lb = y.size(); lc = la + lb;for (int i = 0; i < la; i++) a[la - 1 - i] = x[i] - '0';for (int i = 0; i < lb; i++) b[lb - 1 - i] = y[i] - '0';//模拟乘法mul(c, a, b);//输出for (int i = lc - 1; i >= 0; i--) cout << c[i];return 0;
}
P1480 A/B Problem - 洛谷

![[Pasted image 20250325161925.png]]

定义⼀个指针i 从「⾼位」遍历被除数,⼀个变量t 标记当前「被除的数」,记除数是b ;

  • 更新⼀个当前被除的数t = t × 10 + a[i];
  • t/b 表⽰这⼀位的商,t%b 表⽰这⼀位的余数;
  • ⽤t 记录这⼀次的余数,遍历到下⼀位的时候重复上⾯的过程
    被除数遍历完毕之后,t ⾥⾯存的就是余数,但是商可能存在前导0 ,注意清空
#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
typedef long long LL;
int a[N], b, c[N];
int la, lc;void sub(int c[], int a[], int b)
{LL t = 0; //标记余数for (int i = la - 1; i >= 0; i--){//计算被除数t = t * 10 + a[i];c[i] = t / b;t %= b;}//处理前导0while (lc > 1 && c[lc - 1] == 0) lc--;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);string x; cin >> x >> b;la = x.size();for (int i = 0; i < la; i++) a[la - 1 - i] = x[i] - '0';//模拟除法lc = la;sub(c, a, b);//输出for (int i = lc - 1; i >= 0; i--) cout << c[i];return 0;
}

热搜词