据说这是新浪的一道面试题,被很多公司和单位转载,比较经典,大家‘亲切’的称之为‘猴王问题’,题目的大概意思如下:
有 一群猴子排成一圈,按1,2,...,n依次编号。
然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数, 再数到第m只,在把它踢出去...,
如此不停的进行下去, 直到最后只剩下一只猴子为止,那只猴子就叫做大王。
要求:编程模拟此过程,输入m、n, 输出最后那个大王的编号。
下面提供一种自己认为比较容易理解的解题方法:
function getKingMonkey($n,$m){ $monkey=range(1,$n); //构建猴子数组 $i=0; //遍历猴子数组 while( list($k,$value)=each($monkey)){ if(count($monkey)==1){ echo $value. "是猴王"; exit(); } if(++$i==$m){ echo $monkey[$k].'踢出去'.' '; unset($monkey[$k]); //把变量 清除 $i=0; //指针归位 } //如果已经数到最后的话 则继续进行下一轮的循环 if(!current($monkey)){ reset($monkey); } } }