高精度算法小结

高精度算法:

所谓的高精度算法实则就是计算的数值超过的计算机所能接受的最大值,无法正确的计算.这个时候就需要我们利用其他方法来模拟计算机计算的过程.
在这里,我们可以估计计算的位数,定义一个足够储存的数组来储存我们计算的数值,手动的模拟计算机计算的过程,就像我们小学学习加减乘除那样计算,就是一个模拟的过程.不过有一点需要注意的是我们要手动的去除数字最开始多余的0.
一般的模拟我们都是用一个一维数组来按逆序储存每一位的数字,当然也可以每个数组元素储存多位,一个数组的元素储存多位的好处就是会提高计算的效率,减少循环的次数,不过就是可能会比储存一位的方法难一点.

模拟过程:

       数据的接收和存贮：当输入的数很长时，可采用字符串方式输入，这样可输入数字很长的数，利用字符串函数和操作运算，将每一位数取出，存入数组中。另一种方法是直接用循环加数组方法输入数据。
    void init(int a[])                                //传入一个数组
    {
            string s; 
           cin>>s;                                      //读入字符串s 
           a[0]=s.length();                         //用a[0]计算字符串s的位数 
           for(i=1;i<=a[0];i++)
              a[i]=s[a[0]-i]-'0';                 //将数串s转换为数组a，并倒序存储 
    }另一种方法是直接用循环加数组方法输入数据。
    (2) 高精度数位数的确定
       位数的确定：接收时往往是用字符串的，所以它的位数就等于字符串的长度。
(3) 进位,借位处理
       加法进位：c[i]=a[i]+b[i];
                         if (c[i]>=10) { c[i]%=10; ++c[i+1]; }
　　减法借位：if (a[i]<b[i]) { --a[i+1]; a[i]+=10; }
                         c[i]=a[i]-b[i];
　　乘法进位：c[i+j-1]= a[i]*b[j] + x + c[i+j-1];
                         x = c[i+j-1]/10;
                         c[i+j-1] %= 10;
(4) 商和余数的求法
     商和余数处理：视被除数和除数的位数情况进行处理.