题目描述

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

测试说明

**输入说明：**输入的一个正整数n。 输出说明：输出PI的值，精确到小数点后n位，最后输出一个回车。
平台会对你编写的代码进行测试：

**测试输入：**5

**预期输出：**3.14159

解答

以下是数组实现的方法：
显然使用数组，时间复杂度更低。

#include <stdio.h>
int r[2800 + 1];
int i, k;
int b, d;
int c = 0;
int ans[3000];
int j = 0;

int main() {
	int n;scanf("%d",&n);n++;
    for (i = 0; i < 2800; i++)
		r[i] = 2000;
    r[i] = 0;
    for (k = 2800; k > 0; k -= 14) {
	d = 0;
	i = k;
	for (;;) {
	    d += r[i] * 10000;
	    b = 2 * i - 1;
	    r[i] = d % b;
	    d /= b;
	    i--;
	    if (i == 0) break;
	    d *= i;
	}
	int tmp = c + d / 10000;
	ans[j+3] = tmp % 10;
	ans[j+2] = (tmp / 10) % 10;
	ans[j+1] = (tmp / 100) % 10;
	ans[j+0] = tmp / 1000;
	j+=4;
	c = d % 10000;
    }
    for(int i = 0;i<n;i++){
    	if(i==1&&n>1)printf(".");
    	printf("%d",ans[i]);
	}

    return 0;
}

k次循环实际上实在迭代：

2(1+13(1+25(1+…(1+27992⋅2799+1(1+0))…)))2\left(1+\frac{1}{3}\left(1+\frac{2}{5}\left(1+\ldots\left(1+\frac{2799}{2 \cdot 2799+1}(1+0)\right) \ldots\right)\right)\right)