高精度之高精度除法（高精除以高精）

本文主要是介绍高精度之高精度除法（高精除以高精），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

好像NOIP并不会用到，但是作为强迫症的我还是坚持学了。高精度除以高精度我所知道的有两个思路：

手动模拟法

还是手动模拟除法过程，但是注意在截取了被除数的正确片段之后应该试商，即枚举k从1到9看当k等于多少才合适，但是如果每次循环都试一边的话时间复杂度必定会很高，优化的方法就是在开始时就把k乘以除数的值记录下来，程序执行时只要二分比较确定K值就行了。

但是这种方法实现起来太过麻烦，比较大小时可能会用到高精度减法，刚开始初始化的时候又用到高精度乘法，所以被我自动忽略。下面着重介绍第二种方法。

高精度减法模拟法

第二种方法是运用高精度减法，截取完被除数之后用余数减除数，直到值为负数，这样确定出了这意味的商应该是多少，然后再取被除数的下一位。为了免去一些麻烦，可以使被除数被截取的区间长度比除数大1，最后得出来的商如果大于9就朝上一位进位。具体代码实现如下：
读的过程中建议自己造一组数据自行模拟手动的减法过程

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector> 
#include<iterator>
#include<cstdio>
using namespace std;
string a,b,d="0",bb="0";
int dif,dns=0,r,all=0;
int lena,lenb,qq=0;//qq记录小数点是否已经输出 
vector<int>c;
void change(string x,string y)//这里的减法和我写的独立的减法程序一样，不再赘述
{c.clear();dif=abs(x.length()-y.length());int len=max(x.length(),y.length());for(int i=len-1;i>=0;i--){int a=x[i]-'0'+dns,b=y[i-dif]-'0';if(len-i > y.length()) {b=0;}int p=a-b;dns=0; if (p < 0) {p+=10;dns=-1;}c.push_back(p);}
}
void handle()
{int num=0;while(a.length() > b.length() || (b.length() == a.length() && a >= b)){//只是将除法的过程改为了减法，而这一步就是确定商多少num++;//每减一次商累加一change(a,b);int con=1;a="0";for(int i=c.size()-1;i>=0;i--)//把余数重新转化为string {if(c[i]==0&&con){continue;}con=0;if(a == "0") a=char(c[i]+48);//0的阿斯科玛是48else a=a+char(c[i]+48);}//为了不再更改之前写的高精度减法的基础，这里只能将余数转换成string的形式//之前其实没用char(c[i]+48)的形式但是出现了各种错误，最后才发现这样可以}cout<<num;//输出得到的商的当前位，当然如果希望得到结果的话也可以将它存起来if(a == "0" ) exit(0);//对于小于的情况，如果余数等于0了一定是已经除尽int con=1;while(a.length() < b.length() || (b.length() == a.length() && a < b)){//余数后面补零，使余数大于除数if(con--) a=a+char(48);//如果只补一次，自然结束了else //但是如果补了两个0的话，一定会得到一个商是0，这时应该输出{cout<<"0";a=a+char(48);}}
}
int main()
{cin>>a>>b;if(b=="0"){cout<<"-1";return 0;}lena=a.length();lenb=b.length();if(a == b){cout<<"1";return 0;}if(lena < lenb || (lena == lenb && a < b))//如果被除数小于除数，先输出“0.”，再将被除数加一{cout<<"0.";a+="0";while(a.length() < b.length() || (b.length() == a.length() && a < b))//有可能出现加一后被除数仍然小于除数，这时应该继续加{a+="0";cout<<"0";//为了模拟手动除法，每次给被除数加末尾数字的时候都应该输出0}while(all <= 100)//all用来控制输出的位数，这里是输出的小数点后的位数{handle();//其实这里的handle改自高精度减法的main函数all++;}}else//被除数大于除数和小于除数的情况差别很大，所以分开写{r=lenb-1;//记录a中已经读到的位置//还是模拟除法，每次得到商的一位后都应该从被除数上降下一位到余数，而r就是记录从那里降//之前大于的情况在因为被除数已经没有位可以降，所以是直接降0，而这里显然不可以for(int i=0;i<lenb;i++)//将所选区间转化为string形式 {if(d == "0") d=a[i];else d+=a[i];}while(d.length() < b.length() || (d.length() == b.length() && d < b)) {d+=a[++r];}//还是考虑到可能所选区间不够大while(all <= 100){int num=0;while(d.length()>lenb||(d.length()==lenb && d>=b )){num++;change(d,b);//减法过程int con=1;d=bb;for(int i=c.size()-1;i>=0;i--){if(c[i]==0&&con)continue;con=0;if(d == "0") d=char(c[i]+48);else d=d+char(c[i]+48);}
//              cout<<d<<endl;}cout<<num;if(r+1 == lena && d == "0") break;if(r+1 == lena ){if(!qq){cout<<".";qq=1;}d=d+char(48);}else d=d+a[++r];all++;}}return 0;
}