经典的猴子选大王问题

我到金山面试PHP的时候遇到的题目，这道题是ACM中很经典的题型，我肯定不陌生。今天再拿出来看的时候又是另一番滋味，写极客导航之后我已经很久不研究算法方面的问题了。

另外说句实话，实际开发中除了用到数据结构方面的知识外，算法用的的非常少。至于说PHP效率不行，不适合做复杂的运算，我倒是没发现。

题目：帮猴子选大王
有N只猴子要选大王，选举规则如下：所有猴子按1,2,3……N编号围成一圈，从编号为1的猴子开始顺序1，2……m报数，凡报到m号的退出圈外，如此循环报数，直到圈内只剩一只猴子时，这只猴子就是大王。输入N,M得出猴王的编号。

如输入：6，2；
输出：5；

建议自己先尝试解看看。

下面是我用php做的演示

 function yuesefu($n,$m) {   
 $r=0;   
 for($i=2; $i<=$n; $i++) {  
 $r=($r+$m)%$i;   
 }  
 return $r+1;   
 }   
 print\_r(yuesefu(6,2));//结果输出  
?>

该题其实就是经典的”约瑟夫问题”,我们不需要知道中间刷下来猴的顺序，只关心最后留下来的猴。所以算法将非常简单，一个循环就能搞定。

算法分析推导：（说明：mod为取余）

时间O(n)，空间O(1)

设f(n)为初始有n只猴时最后一只退出圈外的猴的编号，那么有如下递推式：
f(n) = (f(n-1) + m) mod n

下面说说这个公式是怎么来的：
以n=5, m=3为例，一开始有这么5只猴：
0 1 2 3 4

第一轮报数后2号退出圈外，圈子里剩下来的猴的编号是这些：
3 4 0 1

这里把3号写在最前面了，因为轮到3开始报数。这个时候我们看看当n=4时的答案，即初始圈子为：
0 1 2 3

我们把n=4的初始圈子的所有数x变换成(x+3)mod5，得到：
3 4 0 1

发现规律没有？这恰好就是n=5时第一轮结束后的圈子状态，也就是说我们可以根据n=4的答案推出n=5时的答案。之后我们通过手工演算一下就能发现n=z时的圈子第一轮结束后(即m-1号自杀后)的圈子状态，可以由n=z-1的初始圈子施以变换x -> (x+m) mod z得到。于是我们可以从n=1开始(此时的答案是0)，推出n=2的答案，再推出n=3，直到计算到所要求的n。

举个n=6，m=3的例子推算一下；

n=2 -> 1 (0+3)mod2
n=3 -> 1 (1+3)mod3
n=4 -> 0 (1+3)mod4
n=5 -> 3 (0+3)mod5
n=6 -> 0 (3+3)mod6

最后答案就是0，原题中因为我们是从1开始编号，所以最后要加1；

最后用c++演示的代码：

int monkey(int n,int m) {   
 int r=0;   
 for(i=2; i<=n;i++) {  
  r=(r+m)%i;   
 }  
 return r+1;   
}   
int main()  
{  
 int n = 0,m = 0;  
 scanf("%d %d",&n,&m);//输入n,m的值  
 printf("%d",monkey(n,m));//输出函数的返回值  
 return 0;  
}