【算法学习之路】4.简单数论（4）

简单数论（4） 前言三.高精度1.什么是高精度2.解决办法 精度乘除法一.精度乘法1.数据的存储2.步骤3.例题：高精度乘法 二.精度除法1.例子2.步骤3.例题：高精度除法

前言

我会将一些常用的算法以及对应的题单给写完，形成一套完整的算法体系，以及大量的各个难度的题目，目前算法也写了几篇，滑动窗口的题单正在更新，其他的也会陆陆续续的更新，希望大家点赞收藏我会尽快更新的！！！

三.高精度 1.什么是高精度

对运算的精度要求非常高，用已知的数据类型无法精确表示的数值，现有的数据类型存不下，无法计算

2.解决办法

1.一般是用数组模拟大数的运算 2.开一个比较大的整数数组或字符串 3.数组或字符串的元素代表大数的某一位 4.通过数组或字符串元素的运算模拟大数的运算 5.最后将代表大数的数组或字符串输出

精度乘除法 一.精度乘法 1.数据的存储

1.将数据存在数组中，并且0存个位数（数组a,b）； 2.结果：将结果单独放入一个数组，每个单独的位置放置对应的结果，判断每个结果>是否还有进位（c）； 注意:c[i+j] = a[i] * b[j]

2.步骤

1.用字符串读入，再倒着将其存在数组里 2.用两层for循环遍历这两个数组让他们相乘 3.将其存入到另一个数组中（长度位a+b） 4.用for循环遍历处理进位 5.去掉前导零

3.例题：高精度乘法

洛谷P1303 A*B Problem 题解：

#include <iostream> #include <string> using namespace std; void init(int* a) {//初始化 string s; cin >> s; a[0] = s.size();//数组的0位置存元素个数 for (int i = 1; i <= a[0]; i++) { a[i] = s[a[0] - i] - '0';//将字符串倒着存在数组中 } } //每次的除数 void numcpy(int* a, int* b, int n) {//n为后面有几个零 a[0] = b[0] + n;//有多少位 for (int i = 1; i <= n; i++) {//将前面初始化为零 a[i] = 0; } for (int i = n + 1; i <= a[0]; i++) {//将值赋给 a[i] = b[i - n]; } } bool check(int* a, int* t) {//检查哪个大 if (t[0] > a[0]) { return false; } else if (t[0] < a[0]) { return true; } else { for (int i = a[0]; i > 0; i--) { if (t[i] > a[i]) { return false; } else if (t[i] < a[i]) { return true; } } return true; } } void sub(int* t, int* a) {//两数相减 for (int i = 1; i <= a[0]; i++) { a[i] -= t[i]; if (a[i] < 0) { a[i] += 10; a[i + 1]--; } } int l = a[0];//位数 while (a[l] == 0 && l >= 1) {//去除前导零 a[0]--; l--; } } int main() { int a[100005], b[100005];//除数和被除数 int ans[100005] = { 0 };//答案 init(a); init(b); ans[0] = a[0] - b[0] + 1;//答案最多有多少位数 if (ans[0] <= 0) {//如果除数小于被除数 cout << '0' << endl; return 0; } for (int i = ans[0]; i > 0;i--) { int t[100005] = { 0 };//存每次的被除数 numcpy(t, b, i - 1); while (check(a, t)) { sub(t, a); ans[i]++; } } for (int i = ans[0]; i > 0; i--) {//去掉前导零 if (i == ans[0] && ans[i] == 0) { continue; } cout << ans[i]; } return 0; } 二.精度除法

本质为减法

1.例子

如： 531518 / 123 = 4321 ‘’‘’‘’ 35; 为： 531518 / 123000 = 4 ‘’‘’‘’ 39518 39518 / 12300 = 3 ‘’‘’‘’ 2618 2618 /1230 = 2 ‘’‘’‘’ 158 158 / 123 = 1 ‘’‘’‘’ 35 n位数除m位商位数最多为n - m + 1

2.步骤

1.利用字符串读入被除数和除数 2.把字符串倒着放入到数组中（把数组0的位置空出来，记录总共有多少位） 3.进行循环求商的每一位（如果a<b则商的结果为零） 注意：余数在被除数数组中

3.例题：高精度除法

洛谷P2005 A/B Problem II

#include <iostream> #include <string> using namespace std; void init(int* a) {//初始化 string s; cin >> s; a[0] = s.size();//数组的0位置存元素个数 for (int i = 1; i <= a[0]; i++) { a[i] = s[a[0] - i] - '0';//将字符串倒着存在数组中 } } //每次的除数 void numcpy(int* a, int* b, int n) {//n为后面有几个零 a[0] = b[0] + n;//有多少位 for (int i = 1; i <= n; i++) {//将前面初始化为零 a[i] = 0; } for (int i = n + 1; i <= a[0]; i++) {//将值赋给 a[i] = b[i - n]; } } bool check(int* a, int* t) {//检查哪个大 if (t[0] > a[0]) { return false; } else if (t[0] < a[0]) { return true; } else { for (int i = a[0]; i > 0; i--) { if (t[i] > a[i]) { return false; } else if (t[i] < a[i]) { return true; } } return true; } } void sub(int* t, int* a) {//两数相减 for (int i = 1; i <= a[0]; i++) { a[i] -= t[i]; if (a[i] < 0) { a[i] += 10; a[i + 1]--; } } int l = a[0];//位数 while (a[l] == 0 && l >= 1) {//去除前导零 a[0]--; l--; } } int main() { int a[100005], b[100005];//除数和被除数 int ans[100005] = { 0 };//答案 init(a); init(b); ans[0] = a[0] - b[0] + 1;//答案最多有多少位数 if (ans[0] <= 0) {//如果除数小于被除数 cout << '0' << endl; return 0; } for (int i = ans[0]; i > 0;i--) { int t[100005] = { 0 };//存每次的被除数 numcpy(t, b, i - 1); while (check(a, t)) { sub(t,a); ans[i]++; } } for (int i = ans[0]; i > 0; i--) {//去掉前导零 if (i == ans[0] && ans[i] == 0) { continue; } cout << ans[i]; } return 0; }