php面试题中的约瑟夫环

最近忙着做面试题,看到一道题感觉比较有兴趣,查阅相关资料后发现这是一个约瑟夫环的问题。
一群猴子围成一圈,按1,2,3,4,....n一次编号。然后从第1值开始数,数到第m只,把它踢出圈,从它后面再开始数,再数到第m只,再踢它出去...,如此不停进行下去,知道最后剩下一只猴子为止,那只猴子就叫做大王。要求编程模拟此过程,输入m、n输出最后那个大王编号?

下面内容来自网页:
解决问题的核心步骤:(程序的基本算法)
⒈建立一个具有n个链结点,无头结点的循环链表;
⒉确定第1个报数人的位置;
⒊不断地从链表中删除链结点,直到链表为空。
也许看到这里你还不明白,没关系可以看下下面的php代码模拟数据结构

<?php

/*

*@parm int $n  猴子总数

*@parm int $m 每次数到第几只

*/
function king($n,$m) {
$monkey = range(1,$n);//模拟建立一个连续数组
$i = 0;
while(count($monkey) > 1) {
  $i += 1; // 开始查数
  $head = array_shift($monkey); //直接一个一个出列最前面的猴子
  if($i % $m != 0) {
    array_push($monkey,$head); // 如果没数到m或m的倍数,则把该猴放回尾部去.
  } //否则就抛弃掉了
}
return $monkey[0];
}

上一篇:4th day


下一篇:异常处理与网络基础中的tcp,udp协议