一、算法描述
高精度除法和乘法讨论的一样,都是一个大整数和一个小整数之间的运算。
算法思路
-
根据小学除法一样,我们还是模拟这个过程。
-
注意这里遍历\(A\)数组的时候要按照我们读数字的顺序,也就是从数组尾部到头部遍历。
-
每一位的计算过程应该是,上一轮的余数\(r\)乘\(10\)之后加上当前位数上的数
A[i]
,即r = r * 10 + A[i]
。 -
然后计算当前位数上的答案并加入答案数组,
C.push_back(r / b)
,然后计算余数进行下一轮的计算,r = r % b
。 -
假如答案是\(0084\),那么我们将答案加入数组的顺序也是\(0、0、8、4\),为了方便处理前导\(0\)以及统一输出,我们需要将答案逆序一下。
-
最后的结果需要将余数带出来,所以参数用一个引用表示余数。
经过优化之后代码如下:
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
for (int i = A.size() - 1; i >= 0; --i)
{
r = r * 10 + A[i];
C.push_back(r / b);
r = r % b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
二、题目描述
给定两个非负整数(不含前导 \(0\))\(A,B\),请你计算 \(A/B\) 的商和余数。
输入格式
共两行,第一行包含整数 \(A\),第二行包含整数 \(B\)。
输出格式
共两行,第一行输出所求的商,第二行输出所求余数。文章来源:https://www.toymoban.com/news/detail-711046.html
数据范围
\(1≤A的长度≤100000,\)
\(1≤B≤10000,\)
\(B\) 一定不为 \(0\)文章来源地址https://www.toymoban.com/news/detail-711046.html
输入样例:
7
2
输出样例:
3
1
三、题目来源
四、源代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100010;
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
for (int i = A.size() - 1; i >= 0; --i)
{
r = r * 10 + A[i];
C.push_back(r / b);
r = r % b;
}
reverse(C.begin(), C.end());
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');
int r = 0;
vector<int> C = div(A, b, r);
for (int i = C.size() - 1; i >= 0; --i) cout << C[i];
cout << endl << r << endl;
return 0;
}
到了这里,关于高精度除法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!