数据结构与算法再探（二）高精度计算

基本知识点：

相关操作：

高精度计算也被称作大整数计算，内置类型给的数据范围总会有超出范围的计算，一般处理高精度计算，使用数字数组来表示高精度数字。每一个字符表示数字的一个十进制位，高精度数值计算实际上是一种特别的字符串处理。

转字符数组：

既然使用数字数组就会涉及到数字串转为数字数组，数字位如何存储？转换时是将数字最高位在字符串首（下标小的位置），而后从低位到高位保存各位数字（存储反转的字符串）这么做的原因在于，数字的长度可能发生变化，这样存储的化所有的个位都在下标 [0]，所有的十位都在下标 [1]……）；同时，加、减、乘的运算一般都从个位开始进行就不会受到影响。

结果输出：

计算之前将字符数组所有元素初始化为0，因为结果是反转存储，输出的时候需要从高位输出，涉及到如果不希望输出前导零的化，需要从最高位开始向下寻找第一个非零位，然后从此处开始输出。输出的终止条件是i>=1而不是i>=0是因为当整个数字等于0时仍希望输出一个字符0。

四则运算实例：

高精度的四则运算重点在于梳理清楚如何处理每一位和进位的规则。

高精度加：

从最低位开始，将两个加数对应位置上的数码相加，并判断是否达到进位 。如果达到，那么处理进位：将更高一位的结果上增加 ，当前位的结果减少 。

高精度减法：

高精度减法，也就是竖式减法，从个位起逐位相减，遇到负的情况则向上一位借 。如果不确定被减数和减数哪个更大，可以先比较一下两个数，如果被减数更小，则先输出负号，再进行更大数字减更小数字的减法运算。

 高精度乘法：

高精度除法：

竖式除法实际上可以看作一个逐次减法的过程。

#include <iostream>
using namespace std;
#define N 102 //高精度位数//数字串转字符数组
int toNum(const string &str, int nums[])
{   int len = str.length();for (int i = 0; i < len; ++i){nums[i] = (str[len - i - 1] - '0');}return len;
}
void add(int pa[],int sizeA,int pb[],int sizeB, int resultC[]) //高精加
{int t = 0; // 进位for (int i = 0; i < sizeA||i<sizeB; ++i){resultC[i] = pa[i] + pb[i] + t;t = resultC[i] / 10;resultC[i] %= 10;}
}
void sub(int pa[], int maxAB,int pb[], int resultC[])//高精度减默认pa>pb
{int  t = 0;//进位for(int i = 0; i <maxAB; ++i){resultC[i] = pa[i] - t - pb[i];t = 0;if(resultC[i] < 0){t = 1;resultC[i] += 10;}}
}
//高精度乘法
void mul(int pa[],int lenA, int pb[],int lenB, int mul[])//高精度乘法
{int i;for(i = 0; i <lenA; ++i){int t = 0;for(int j = 0; j <lenB; ++j){mul[i+j] += pa[i]*pb[j] + t;t = mul[i+j] / 10;mul[i+j] %= 10;}mul[i+lenB] += t;}
}
bool cmp(int a[],int b[],int x,int lenB){//被除数从最高位到第x位，是否大于等于除数if(a[x+lenB]>0) {//如果被除数比除数多一位，返回truereturn true;}for(int i=lenB-1;i>=0;i--){//逐位比较if (a[x+i]<b[i]){//除数大return false;}else if (a[x+i]>b[i]){//被除数大return true;}}return true;
}
void divide(int a[], int b[], int lenA,int lenB,int c[],int d[])//r:商 x:余数 
{int LA,LB;for (LA=lenA; LA >0; --LA)if (a[LA-1] != 0) break;for (LB = lenB; LB >0; --LB)if (b[LB-1] != 0) break;if (LB == 0) {cout<<"除数不可以为0";return;}  // 除数不能为零// d 是被除数的剩余部分，算法结束后自然成为余数for (int i = 0; i < LA; ++i) d[i] = a[i];for(int i=LA-LB;i>=0;--i){while(cmp(d,b,i,LB)){//够减c[i]++;//商加1for(int j=0;j<LB;++j){//逐位相减if (d[i+j]>=b[j]){//够减d[i+j]-=b[j];//直接减}else{//不够减d[i+j+1]--;//借位d[i+j]+=10-b[j];//加10再减}}}} 
}
void show(int tmp[]){
int i;for (i = N - 1; i >= 1; --i)if (tmp[i] != 0)break;for (; i >= 0; --i)cout << tmp[i];cout<<endl;
}
int main()
{int a[N]={}, b[N]={}, c[N]={},rmul[2*N]={},d[N]={};string s = "2000";string s1 = "100";int lenA=toNum(s,a);int lenB=toNum(s1,b);// add(a,lenA,b,lenB,c);// cout<<"-add-result ";// show(c);// cout<<"-mul-result ";// mul(a, lenA,b,lenB, rmul);// show(rmul);// cout<<"-sub-result ";// int i;// if(lenA>lenB||(lenA==lenB&&s>=s1)){//     sub(a,lenA,b,c);//     show(c);// }else{//     sub(b,lenB,a,c);//b>a输出-//     cout<<"-";//     show(c);// }divide(a,b,lenA,lenB,c,d);cout<<"-divide-quotient ";show(c);cout<<"-divide-remainder ";show(d);return 0;
}