标签:数学

生命游戏模拟器

生命游戏(Game of Life),或者叫它的全称John Conway's Game of Life。是英国数学家约翰·康威在1970年代所发明的一种元胞自动机。
所谓元胞自动机其实是一种离散的状态机,即无数个独立的格子,每个格子处于某种状态,然后所有格子按照预先设定好的规律进行状态演化。格子们可以是任意维度、任意形状、按任意规律排布的。
而生命游戏就是最简单的元胞自动机之一——在二维平面上的方格子(细胞),每个细胞有两种状态:死或活,而下一回合的状态完全受它周围8个细胞的状态而定。按照以下三条规则进行演化:
1. 活细胞周围的细胞数如果小于2个或多于3个则会死亡;(离群或过度竞争导致死亡)
2. 活细胞周围如果有2或3个细胞可以继续存活;(正常生存)
3. 死细胞(空格)周围如果恰好有3个细胞则会诞生新的活细胞。(繁殖)
这三条规则简称B3/S23。如果调整规则对应的细胞数量,还能衍生出其他类型的自动机。

以上是对生命游戏这个概念的解释,而我2013年时为它编写了一个js版的模拟器,作为个人项目练习之用。具体解释和功能介绍详见知乎专栏:个人项目开发示例:生命游戏

这里只是为了放个地址方便访问。

点击打开模拟器

19+

素数螺旋

本文启发自知乎问题:极坐标表示 5000 到 50000 之间的素数画点到纸上为什么会形成一条斐波那契螺旋线?

把一个自然数n用极坐标表示,也就是在坐标(n*cos n,n*sin n)的位置绘制一个点;而当你把所有素数绘制到纸上之后,会发现它是一个包含了许多条空白线条的圆形:

很显然,空白是合数导致的,但为什么合数会排列成一条条曲线呢?

王小龙已经做了精彩的回答。不过为了更直观地理解,我写了这个小程序:

[阅读全文]

13+

约瑟夫斯问题:最后生还者

有这么一个古老的问题:一群死刑犯排成圆圈,每隔一人枪毙一个,转完一圈后从头开始继续枪毙,直到剩下最后一个人,这个幸运儿会被释放。

问:一开始站在哪个位置才能活下来?

这就是著名的约瑟夫斯问题,排成的圆圈叫做约瑟夫斯环。

(当然,隔一人只是个特殊情况,约瑟夫斯问题包含了间隔任何人数的计算方法)

在上面维基百科的链接以及知乎的答案里已经有了通用的计算方法,这里就不必讲什么公式和证明了,而是直接用图形来演示:

[阅读全文]

6+

小球称重问题:用天平称量几次才能找到有问题的球?

在n个外观完全相同的小球中,有一个与其它球重量不同。如何只用一架天平找到这个球并判断它比其它球轻还是重?最少需要称几次?

这是一个流传极广的经典问题,在网上随便一搜就会发现无数人都提出了自己的见解和算法并争论不休。最常见的是12个小球,至于更多球的计算,就不是人力能及的了。

实际上,这个问题确实是有准确答案的:n次称量最多可以在个球中找到不同的球,并判断它的轻重。
理论证明可参考The Problem of the Pennies, F. J. Dyson, The Mathematical Gazette , Vol. 30, No. 291 (Oct., 1946), pp. 231-234。
不过这里不打算讲那么多理论,而是直接演示怎么称量并找到这个小球。

算法十分精巧,我尽可能简单地描述了一下。如果还是觉得太抽象,没关系,直接点击这里或者拉到下面看演示就可以了。 [阅读全文]

11+