【原创】求出被淘汰人员的编号顺序

【原创】求出被淘汰人员的编号顺序

面试题目:如上图所示,假设参与人数为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;
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据