有这么一个古老的问题:一群死刑犯排成圆圈,每隔一人枪毙一个,转完一圈后从头开始继续枪毙,直到剩下最后一个人,这个幸运儿会被释放。
问:一开始站在哪个位置才能活下来?
这就是著名的约瑟夫斯问题,排成的圆圈叫做约瑟夫斯环。
(当然,隔一人只是个特殊情况,约瑟夫斯问题包含了间隔任何人数的计算方法)
在上面维基百科的链接以及知乎的答案里已经有了通用的计算方法,这里就不必讲什么公式和证明了,而是直接用图形来演示:
上一篇中,初学html5动画的我在canvas画布上用彩色小球模拟了烟花喷射的效果,功能虽简单,但在制作中涉及到了几个要点:计算、绘制、显示。而且实现了可兼容旧版的requestAnimationFrame方法,以达到更平滑的动画效果。
接下来,我准备在上一篇的基础上加以改进,实现一个有简单互动的小游戏。
当然,只有小球是远远不够用的,在边调试边开发的过程中,下列功能也逐一实现:
以及之前实现过的渐隐对象,用于显示摧毁后的爆炸效果、全屏闪烁以及文字提示。
那么,先看看效果再讲解代码吧。
操作提示:
这是我在知乎专栏发表的那篇知乎用户排行榜生成器0.2版的源码,为增强专栏的可读性所以在那边只放了压缩版的。这里是完整版,有兴趣者可以自行调试修改。
这段脚本需要登录知乎网站后在浏览器控制台运行,更详细的用法请点上面链接查看。 [阅读全文]
在n个外观完全相同的小球中,有一个与其它球重量不同。如何只用一架天平找到这个球并判断它比其它球轻还是重?最少需要称几次?
这是一个流传极广的经典问题,在网上随便一搜就会发现无数人都提出了自己的见解和算法并争论不休。最常见的是12个小球,至于更多球的计算,就不是人力能及的了。
实际上,这个问题确实是有准确答案的:n次称量最多可以在
个球中找到不同的球,并判断它的轻重。
理论证明可参考The Problem of the Pennies, F. J. Dyson, The Mathematical Gazette , Vol. 30, No. 291 (Oct., 1946), pp. 231-234。
不过这里不打算讲那么多理论,而是直接演示怎么称量并找到这个小球。
算法十分精巧,我尽可能简单地描述了一下。如果还是觉得太抽象,没关系,直接点击这里或者拉到下面看演示就可以了。 [阅读全文]