简单数论（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;
}
