求猴子选大王的算法分析

Question

/*
 *       约瑟夫环
 *  
 *  N只猴子选大王，方法如下：按照1，2，3....n给猴子编号，
 *  然后按编号顺序坐成1圈，
 *  从1号猴子开始按编号顺序报数至 m ，报到 m 的猴子退出圈外，
 *  退出的猴子的下一只猴子重新从1开始报数至m，报到m的猴子退出，
 *  如此循环直至剩下一只猴子就是大王。要求编写一程序，n和m都是入参，
 *  返回最后一只猴子的编号。
 */
         public void King(int n, int m) {
// 总人数 M ，数到第 N 个排除。
int k = 0;
for (int i = 2; i <= n; i++){
k = (k + m) % i;
System.out.println("k=" + k);
}
System.out.println("第" + (++k) + "位当上了猴子大王。");
}k = (k + m) % i;    这段代码是怎么分析出来的？？？

Answer 1

这一行注释写错了。这是反推。（k从0到n-1计数）
n==1时，k1==0
n==2时，k2==m%2
n==3时，k3==(k2 + m%3)%3==(k2 + m)%3，这是因为m%3的那位被请走，从k3到k2的序号值需要用m%3调整差异，因为调整后值可能突破3所以再%3
最终确立前述程序中的
k''=(k' + m) % n这也反映了运行效率高的算法可读性往往差。这个题用链表做，哪个都能看懂。

Answer 2

这个效率为 O(N) 的算法还不是最简算法。在《具体数学》（Concrete Mathematics）一书第一章的最后还有效率为 O(1) 的算法。