PKU版本Josephus problem的讨论

Sat, Nov 22, 2014

今天考试时候用的时间最长的一道题目就是约瑟夫问题（的变式）。据说这个变式是学校特色（求证？），暂且称之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）重写会有更好的效果吗？