计算π

三月 31, 2018 904

计算 π 可不是件容易事

前情提要

偶然在WA谷上看到一道题

tlUNK.png

不得不说很玄学

抱着好奇的心态我点开了题解

发现了一个打表的。。。。

于是心血来潮去搜了一下如何计算π

于是就有了这篇文章

题目描述

Handwer STD 要你计算一下圆周率，要求最少为4000位（从小数部分第一位开始算起）

输入描述&样例

无输入

输出描述&样例

输出 π ，要求保留至少4000位小数。

样例：

1
3141592653589793......

其他

时限为5000ms

解题

解题思路

我们需要找到一个合适、可靠且快速的圆周率计算公式

我选择了基于级数的快速收敛公式

这是一个很快、精度也很高的算法

公式为：

tlkra.png

（懒得写LaTeX码了

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

long long n = 16366;
long long d[16366 + 2];

int main() {
	ios::sync_with_stdio(false);
	double cost;
	long long  i = 0;
	while (n - i) d[++i] = 2000;
	for (;n;n -= 14) {
		long long p;
		for (p = 0,i = n;i;i--) {
			p = p * i + d[i] * 10000;
			d[i] = p % (2 * i - 1);
			p /= 2 * i - 1;
		}
		printf("%.4d",d[0] + p / 10000);
		d[0] = p % 10000;
	}
	return 0;
}