求圈算法

‘壹’ π的计算方法有哪些

中国古算书《周髀算经》（约公元前2世纪）的中有“径一而周三”的记载，意即取

(1)求圈算法扩展阅读：

圆周率是指平面上圆的周长与直径之比 （ratio of the circumference of a circle to the diameter） 。用符号π（读音：pài）表示。中国古代有圆率、周率、周等名称。（在一般计算时π=3.14）

圆周率的历史：

古希腊欧几里得《几何原本》（约公元前3世纪初）中提到圆周率是常数，中国古算书《周髀算经》（ 约公元前2世纪）中有“径一而周三”的记载，也认为圆周率是常数。

历史上曾采用过圆周率的多种近似值，早期大都是通过实验而得到的结果，如古埃及纸草书（约公元前1700）中取π=（4/3）^4≈3.1604 。

第一个用科学方法寻求圆周率数值的人是阿基米德，他在《圆的度量》（公元前3世纪）中用圆内接和外切正多边形的周长确定圆周长的上下界，从正六边形开始，逐次加倍计算到正96边形，得到(3+(10/71))

把圆周率的数值算得这么精确，实际意义并不大。现代科技领域使用的圆周率值，有十几位已经足够了。如果以39位精度的圆周率值，来计算宇宙的大小，误差还不到一个原子的体积。

以前的人计算圆周率，是要探究圆周率是否循环小数。自从1761年兰伯特证明了圆周率是无理数，1882年林德曼证明了圆周率是超越数后，圆周率的神秘面纱就被揭开了。

π在许多数学领域都有非常重要的作用。

‘贰’ 有N个人围成一环形圈，第一个人从1开始报数，报道M的人出列，直到最后一个同学，请写出算法。

经典的约瑟夫环问题
设n个人围成一圈，标号为0..n-1，从第一个人开始依次从1到k循环报数，当报到k的
时候此人出圈。设J(n,
k,
i)表示第i个出圈的人的标号。
定理一:
J(n,
k,
1)
=
(k-1)
MOD
n,
(n>=1,
k>=1)
…………
(1)
证明：由定义直接得证。
定理二：
J(n+1,
k,
i+1)
=
(k
+
J(n,
k,
i))
MOD
(n+1),
(n>=1,
k>=1,
1<=i<=n)
………
…
(2)
证明：
设g
=
J(n,
k,
i)，因此如果有n个人，从0开始报号，第隐世i个出圈的标号为g。现在考
虑J(n+1,
k,
i+1)，灶清肢因为J(n+1,
k,
1)
=
(k-1)
MOD
(n+1)，即第一步的时候删除数
字(k-1)
MOD
(n+1)，第二步的时候从数字k开始数起。因而问题变为了找到剩下的n
个数字中从k开始数起被删除的第i个数字(注意这时(k-1)
MOD
(n+1)已经被删除了)
，而这恰好就正咐是(g+k)
MOD
(n+1)，(2)成立。
根据(2)，很容易求得n个数里面第i个出圈的数。
就根据这个定理递推计算吧！

‘叁’ 什么是改良圈算法

首先求一个 Hamilton 圈C ，然后适当修改C 以得到具有较小权
的另一个 Hamilton 圈。修改的方法叫做改良圈算法。