算法刷题笔记 高精度除法（C++实现）

题目描述

• 给定两个非负整数（不含前导0）A，B，请你计算 A/B 的商和余数。

输入格式

• 共两行，第一行包含整数A，第二行包含整数B。

输出格式

• 共两行，第一行输出所求的商，第二行输出所求余数。

数据范围

• 1 ≤ A的长度 ≤ 100000。
• 1 ≤ B ≤ 10000。
• B一定不为 0

求解思路

本题的求解思路仍然是通过编程模拟除法的竖式计算，但是和加减乘法又不一样的地方。由于除法竖式计算中，是从被除数的最高位开始，因此，存放被除数的数组应该用小端存放高位，大端存放低位。最后，和之前的 高精度减法 和 高精度乘法 两道算法题类似，最后的结果需要去除前导零。

实现代码

#include <iostream>
#include <vector>
using namespace std;vector<int> div(const vector<int>& a, const int& b)
{vector<int> result;int jinwei(0);for(int i(0); i < a.size(); ++i){int beichushu = a[i] + 10 * jinwei;result.push_back(beichushu / b);jinwei = beichushu % b;}result.push_back(jinwei);return result;
}int main(void)
{//变量定义部分string a;int b;vector<int> a_vector;//变量输入部分cin >> a >> b;for(int i(0); i < a.length(); ++i) a_vector.push_back(a[i] - '0');//除法运算并去除前导零部分vector<int> result = div(a_vector, b);while(result[0] == 0 && result.size() > 2) result.erase(result.begin());//变量输出部分for(int i(0); i < result.size() - 1; ++i) cout << result[i];cout << endl << result[result.size() - 1];return 0;
}

注意事项：

• 本题中要求同时输出商和余数，但是C++中只能一次返回一个变量，所以本题中将返回向量的最后一个元素设置为余数。实际使用过程中，可以为div函数传入一个新的整数引用类型的参数r，这样，在div函数中修改r，则主函数中的r的值也会随之变化，从而解决了一次只能返回一个值的问题。