今天考试时候用的时间最长的一道题目就是约瑟夫问题(的变式)。据说这个变式是学校特色(求证?),暂且称之PKU版本Josephus problem。之前一直超时,用了一个多小时优化终于出来了。回寝室之后,对门同学试图跑k=20的情况,我说这个肯定超过unsigned long的范围了(算法也木有我快www)。于是脑洞大开,用Python重写代码,打算有空时试一试。

问题描述

2k个小孩坐一圈,前k个自称“好人”,后k个自称“坏人”。现从第一个孩纸开始报数,报到m的离开,剩下的继续从1开始报数,报到m的再离开。现在求最小的整数m,使得离开的前k人都是“坏人”。

代码思路

我就是纯(蠢)模拟(数学大神快来碾压我www),定义一堆关于游戏过程的变量。其中用到的比较关键(我认为比较关键)的优化是:游戏过程中,m不需要用m,可以用(m % 现在剩下人数)来代替,这个是算法复杂度的优化。其他的优化基本上是在优化常数了,这里略去。

我的代码放在GitHub:gist上。请大家多提交建议,多提交Pull Request~

解决过程

一开始的时候没有用上面那个“关键优化”,于是跑到10的时候根本跑不出了(实验室的电脑是顶级i7饿)。用上之后,1-9加起来8ms,10-12加起来200多ms,10和13加起来300多ms,真心是个飞跃。出题者很良心地没有添加13以上的测试数据,于是开心地Pass了。

讨论

首先有一个很反常的现象:k=3的值比k=2小;k=9的值比k=8小。猜想27会不会有这种情况?3的幂都有此情况吗?(我暂时没有能力测试。)

回寝室之后,对门的脑洞大开,和我说想跑个k=20的情况。我说变量要溢出了。结果确实溢出了。换用unsigned long用MBP跑了40分钟后无果,风扇口都可以当吹风机了,果断放弃。准备有空的时候去DigitalOcean开一个处理器密集型的虚拟机,跑个几天试试看0.0

今天尝试解决约瑟夫问题让我对算法的重要性有深刻印象。一个好的算法真的是很重要的,数据结构与算法都是核心科技。

这两个问题要肿么解?有木有复杂度合理的算法?用其他适合计算的语言(比如Wolfram Language)重写会有更好的效果吗?