【原创】求出被淘汰人员的编号顺序
面试题目:如上图所示,假设参与人数为n,编号分别为1、2、3、4……n,开始报数编号为x,每次报数为m次,数到谁,谁就出局,然后从下一位继续报数,例如,共有6人,编号为1、2、3、4、5、6,从编号为2的位置开始报数,每次报3次,2、3、4,4淘汰,最终淘汰编号依次为4、1、5、3、6、2,如果如果输入参数n=8,x=2,m=5,则淘汰的依次编号为多少?
解题方案:【面试题非原创,方案为原创】
// 参数代表含义 n=6,x=2,m=3$n = 8; $x = 2; $m = 5;$arr = array();// 获取可计算的数据for($i=1; $i<=$n; $i++){$arr[$i] = 1;}// $arr = array(1=>1,2=>1,3=>1,4=>1,5=>1,6=>1,7=>1,8=>1);// 初始需要淘汰的编号$j = $x+$m-1;$new = array();for($i=0; $i<$n; $i++){$arr[$j] = 0;$new[] = $j;for($y=0; $y<$m; $y++){$j++;$j = getNextKey($j, $n, $arr);}}var_dump($new); // array(6,3,1,8,2,5,7,4)// 获取有效的游戏编号function getNextKey($j, $n, $arr){if($j > $n){$j = $j – $n;}if(array_sum($arr) == 0){ // 如果为0的话,说明已经全部淘汰了return;}if($arr[$j] == 1){ // 如果为1,说明是有效编号return $j;}else{ // 否则是无效编号$j++;$j = getNextKey($j, $n, $arr);return $j;}}