题解 P1727 【计算π】

0AND1STORY · 2019-06-07 10:26:46 · 题解

正如楼上大佬所说，确实有很多人无节操的打表，但是本蒟蒻懒得打表，于是便决定写一篇题解来介绍一下这道题的正解（这怕是这道题最短的代码了）

算法

和楼上大佬一样，我也采用了如下公式：

其中，n!=1\times 2\times 3\times ...\times n，n!!=1\times 3\times 5\times ...\times n(n\text{为奇数})

然后我们对公式进行展开和调整：

π/2 = 1 + 1!/3!! + 2!/5!! + 3!/7!! + ... + k!/(2×k+1)!! = 1 + 1/3 + (1×2)/(3×5) + (1×2×3)/(3×5×7) + ... + (1×2×...×k)/(3×5×...×(2k+1)) = 1 + 1/3 + (1/3)×(2/5) + (1/3)×(2/5)×(3/7) + ... + (1/3)×(2/5)×...×(k/(2k+1)) = (1/3)×(2/5)×...×(k/(2k+1)) + ... + (1/3)×(2/5)×(3/7) + (1/3)×(2/5) + 1/3 + 1 = (k/(2k+1))×...×(2/5)×(1/3) + ... + (3/7)×(2/5)×(1/3) + (2/5)×(1/3) + 1/3 + 1 = (((((k/(2k+1)+1)×((k-1)/(2(k-1)+1)+1)×...)×3/7+1)×2/5+1)×1/3+1)/1 = (((((1/(2k+1)×k+1)/(2(k-1)+1)×(k-1)+1)/...)/7×3+1)/5×2+1)/3×1+1)/1

然后我们就可以发现，只需要循环做除法、乘法、加1，直到除数为1为止

但是我们发现一个问题，题目要求求到\pi的10000位，所以我们只能用大整数除法来解决

所以代码如下

代码

#include <cstdio>
using namespace std;

int a=10000,b,c=70000,d,e,f[70001],g,n=-1,len;
char str[100005]="141";

int main() {
    scanf("%d",&len);
    for(;b-c;) f[b++]=a/5;
    for(;d=0,(g=c*2)&&n<=len;c-=14,~n&&sprintf(str+n, "%.4d",e+d/a),n+=4,e=d%a)
        for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);
    printf("3.");
    for(register int i=0;i<len;i++) {
        if (!(i%10)) printf(" ");
        if (!(i%50)) printf("\n");
        printf("%c", str[i]);
    }
    return 0;
}

算上空行不到20行，这真的是这道题最♂短♂的代码了orz！