题目

这个是Noj的一道实验题目，题目描述如下：

限制使用双向链表作存储结构，请根据用户输入的一个整数（该整数表示精确到小数点后的位数，可能要求精确到小数点后500位），高精度计算PI值。可以利用反三角函数幂级展开式来进行计算。

input:输入的一个正整数n

output:输出PI的值，精确到小数点后n位，最后输出一个回车。

分析

这道题是一道大数操作题目，虽然存储类型为双向链表，但是重点在大数计算上。目前自己对于这种类型的题不是很擅长，没有想出较好的方法，因此学习的Shawn-Xue的博客的一种方法。
核心部分代码如下，实现建立了一个存储精度为小数点后500位的PI的双向链表，

for(int i = 1; i < 500; i ++)
{
    //R(n) = R(n-1)*i/(2*i+1)

    //乘法
    ret = 0;
    for(rit1 = rn.rbegin(); rit1 != rn.rend(); ++rit1)
    {
        temp = *rit1*i+ret;
        *rit1 = temp%10;
        ret = temp/10;
    }

    //除法
    ret = 0;
    for(it = rn.begin(); it != rn.end(); ++it)
    {
        temp = (*it+ret*10);
        *it = temp/(2*i+1);
        ret = temp%(2*i+1);
    }

    //加法,计算sum
    ret = 0;
    for(rit1 = sum.rbegin(), rit2 = rn.rbegin(); rit1 != sum.rend()&& rit2!=rn.rend(); ++rit1, ++rit2)
    {
        temp = *rit1 + *rit2+ret;
        *rit1 = temp%10;
        ret = temp/10;
    }
}

一开始的时候，没有太看懂实现的思路，所以打印出了前10次计算的中间结果，打印结果如下：

loop: 1
after mul,rn =  0000000002
after div,rn = 0666666666
after add,sum = 6666666662
loop: 2
after mul,rn =  2333333331
after div,rn = 0266666666
after add,sum = 2333333392
loop: 3
after mul,rn =  8999999970
after div,rn = 0114285714
after add,sum = 6409167403
loop: 4
after mul,rn =  6582417540
after div,rn = 0050793650
after add,sum = 6962148903
loop: 5
after mul,rn =  0528693520
after div,rn = 0023088022
after add,sum = 8170051213
loop: 6
after mul,rn =  2318258310
after div,rn = 0010656010
after add,sum = 8276512313
loop: 7
after mul,rn =  0702954700
after div,rn = 0004972804
after add,sum = 2359217313
loop: 8
after mul,rn =  2342879300
after div,rn = 0002340143
after add,sum = 5769649313
loop: 9
after mul,rn =  7821601200
after div,rn = 0001108488
after add,sum = 3618750413
loop: 10
after mul,rn =  0884801100
after div,rn = 0000527851
after add,sum = 4106011413

这样一来，具体的实现过程就一目了然了。算法中PI的计算公式如下：

$\pi = 2 * \sum_0^n \frac{n!}{(2n+1)!!}$

代码中定义了两个链表，为rn和sum,其中rn用于计算每次的相加项,sum用于将每项进行累加，且两个链表每个节点仅存储一位数。代码中的”500”为迭代相加的次数，最终的结果进行了500项的加法运算。每一项的加法运算由三步实现,分别为乘法，除法，加法。乘法实现rn中存储的数乘n，除法实现rn中存储的数除以(2n+1),加法为将新计算出来的rn加入sum中。经过500次循环得到一个500位精度的结果，并进行部分输出。
乘法的运算方法与手动计算乘法的步骤相同，从最低位开始进行乘法，用ret记录进位；除法也与手动计算除法的方法一样，从最高项开始进行除运算，用ret进行余数退位补到下一位上。sum的加法就比较简单，不再赘述了。从输出结果可以看出，对于rn的乘法是逆序遍历rn实现的,对于rn的除法是顺序遍历的，符合刚刚说的计算方法的顺序。

解决

对于原代码实现了一次重构，结果如下：

#include <iostream>
#include <list>

using namespace std;

list<int> epoch;
list<int> sum;

void creatPI(int num)
{
  int len = num;
  int temp = 0;
  int ret = 0;
  list<int>::reverse_iterator reverseIt1,reverseIt2;
  list<int>::iterator it;

  epoch.push_back(2);
  sum.push_back(2);
  for(int i =1;i<len;i++)
  {
    epoch.push_back(0);
    sum.push_back(0);
  }

  for (int j = 1;j<100000;j++)
  {
     ret = 0;
     for (reverseIt1 = epoch.rbegin(); reverseIt1!=epoch.rend();reverseIt1++)
     {
       temp = *reverseIt1 * j + ret;
       *reverseIt1 = temp%10;
       ret = temp/10;
     }
     ret = 0;
     for (it = epoch.begin(); it!=epoch.end(); it++)
     {
       temp = *it + ret*10;
       *it = temp/(2*j+1);
       ret = temp%(2*j+1);
     }
     ret = 0;
     for (reverseIt1 = sum.rbegin(),reverseIt2 = epoch.rbegin();
          reverseIt1 != sum.rend()  && reverseIt2 != epoch.rend();
          reverseIt1++,reverseIt2++)
     {
       temp = *reverseIt1 + *reverseIt2 + ret;
       *reverseIt1 = temp%10;
       ret = temp/10;
     }
   }
}


int main()
{
    int needLen = 0;
    cin >> needLen;
    list<int>::iterator loop;

    creatPI(550);

    loop = sum.begin();
    cout << 3 << "." ;
    loop++;
    for (int i =0;i<needLen;i++)
    {
      cout << *loop;
      loop++;
    }
    cout << endl;

    return 0;
}

需要注意的是，一开始提交代码之后提示输出错误，再检查格式正确后，想到原因可能是由于迭代次数过少而PI的精度不够，因此输出错误。所以将迭代计算的次数由500提升到100000，就正常AC了。

小结

对于大数操作类型的题目应该从每次进位退位的角度进行考虑，思考如何一位一位的计算出结果并存储到数组或者链表中。
PS:发现博主是我滴学长╰(￣▽￣)╭