网站建设公司的工资,wordpress登录小工具,全国最缺工的100个职业排行,易推广#x1f466;个人主页#xff1a;Weraphael ✍#x1f3fb;作者简介#xff1a;目前是C语言 算法学习者 ✈️专栏#xff1a;【C/C】算法 #x1f40b; 希望大家多多支持#xff0c;咱一起进步#xff01;#x1f601; 如果文章对你有帮助的话 欢迎 评论#x1f4ac… 个人主页Weraphael ✍作者简介目前是C语言 算法学习者 ✈️专栏【C/C】算法 希望大家多多支持咱一起进步 如果文章对你有帮助的话 欢迎 评论 点赞 收藏 加关注 前言 往期我们学习了高精度加法、高精度减法 和 高精度乘法本站就是高精度算法最后一站了闲言少叙开快车 目录前言一、算法由来二、算法基本思想三、算法思路四、代码模板一、算法由来 前提两个数都是正整数。当被除数的位数非常长时再同时除以上位数较短的b。最后结果大到unsigned long long都存不了这就要用到高精度除法。 二、算法基本思想 高精度算法同样也是计算机模拟人类竖式计算并将其转化计算机语言的过程。 现在来回忆一下小学除法我们是如何列竖式来解决的 三、算法思路
首先我们用数组存高精度数字被除数。为了方便读入采用字符串读入。为什么要采用字符串读入呢原因是数据位数过长。其次将其转化成数字存进vectorint数组中。存进数组的时候一定要倒着存入。然后就是两数相除的过程了初始化余数t 0两数相除t t * 10 A[i] t临时用来存储每一次余数的结果。对于答案只需要t / b即是商为了保留上一步的余数t只需要将t t % b再次重复以上操作直到被除数全部都遍历完为止在除法运算中计算顺序是从高位向低位开始运算因此A的前导0是在vector的前面而不是尾部详情见算法基本思想因此为了方便去除前导0我们将A翻转这样0就位于数组尾部可以使用pop函数删除前导0最后再逆序输出结果就是答案输出t就是余数
四、代码模板
#include iostream
#include vector
#include algorithmusing namespace std;vectorint div(vectorint A, int b, int t)
{vectorint C;//存储答案t 0;//初始化余数为0//除法从高位开始算起for (int i A.size() - 1; i 0; i -- ){//上一次的余数乘10再加上当前位上的数就是被除数t t * 10 A[i];//商的计算C.push_back(t / b);//保留下一次的余数t % b;}//翻转是为了方便取出前导0reverse(C.begin(), C.end());//去除前导0while (C.size() 1 C.back() 0) {C.pop_back();}//返回答案return C;
}int main()
{string a;//字符串读入被除数int b; //除数int t; //余数vectorint A; //读入cin a b;//倒序存入A中for (int i a.size() - 1; i 0; i -- ) {A.push_back(a[i] - 0);}vectorint C div(A, b, t);//输出商for (int i C.size() - 1; i 0; i -- ) {printf(%d,C[i]); }//输出余数printf(\n%d\n,t);return 0;
}
