How to solve php Joseph problem

"Joseph Ring" is a mathematical application problem: a group of monkeys line up in a circle and are numbered sequentially according to 1, 2,...,n. Then start counting from the 1st one, count to the mth one, kick it out of the circle, start counting from behind it, count to the mth one, kick it out..., and continue in this way until the end. Until there is only one monkey left, that monkey is called the king. Programming is required to simulate this process, input m, n, and output the number of the last king.

Listed below are three ways to solve this problem with PHP:

1. Remove the recursion in logical order

2. Algorithm

3. Linear table application

Method 1, remove

logically

function getKingMokey($n, $m)  
{  
    $monkey[0] = 0;  
    //将1-n只猴子顺序编号 入数组中
    for($i= 1; $i<= $n; $i++)   
    {   
        $monkey[$i] = $i;  
    }  
    $len = count($monkey);  
    //循环遍历数组元素(猴子编号)
    for($i= 0; $i< $len; $i= $i)  
    {  
        $num = 0;  
        /* 
         * 遍历$monkey数组，计算数组中值不为0的元素个数（剩余猴子的个数） 
         * 赋值为$num，并获取值不为0的元素的元素值 
        */
        foreach($monkeyas$key => $value)   
        {   
           if($value == 0) continue;   
           $num++;   
           $values = $value;   
        }  
        //若只剩一只猴子 则输出该猴子编号(数组元素值) 并退出循环 
        if($num == 1)   
        {   
            return$values;  
            exit;   
        }  
        /*  
         * 若剩余猴子数大于1（$num > 1）  
         * 继续程序  
        */
        //将第$i只猴子踢出队伍(相应数组位置元素值设为0) 
        $monkey[$i] = 0;  
        /* 
         * 获取下一只需要踢出队伍的猴子编号 
         * 在$m值范围内遍历猴子 并设置$m的计数器 
         * 依次取下一猴子编号 
         * 若元素值为0，则该位置的猴子已被踢出队伍 
         * 若不为0，继续获取下一猴子编号，且计数器加1 
         * 若取得的猴子编号大于数组个数 
         * 则从第0只猴子开始遍历(数组指针归零) 步骤同上 
         * 直到计数器到达$m值 * 最后获取的$i值即为下一只需要踢出队伍的猴子编号 
         */
        //设置计数器 
        for($j= 1; $j<= $m; $j++)   
        {   
            //猴子编号加一，遍历下一只猴子 
            $i++;  
            //若该猴子未被踢出队伍,获取下一只猴子编号 
            if($monkey[$i] > 0) continue;  
            //若元素值为0，则猴子已被踢出队伍，进而循环取下一只猴子编号 
            if($monkey[$i] == 0)   
            {   
                //取下一只猴子编号 
                for($k= $i; $k< $len; $k++)  
                {   
                    //值为0，编号加1 
                    if($monkey[$k] == 0) $i++;  
                    //否则，编号已取得，退出 
                    if($monkey[$k] > 0) break;  
                }   
             }  
            //若编号大于猴子个数，则从第0只猴子开始遍历(数组指针归零) 步骤同上 
            if($i == $len) $i = 0;  
            //同上步骤，获取下一只猴子编号
            if($monkey[$i] == 0)   
            {   
                for($k= $i; $k< $len; $k++)   
                {  
                    if($monkey[$k] == 0) $i++;  
                    if($monkey[$k] > 0) break;  
                }   
            }   
        }  
    }  
}  
//猴子个数 
$n = 10;  
//踢出队伍的编号间隔值 
$m = 3;  
//调用猴王获取函数
echo getKingMokey($n, $m)."是猴王";  
方法二，递归算法
[php] view
 plain copy
function killMonkey($monkeys , $m , $current = 0){  
    $number = count($monkeys);  
    $num = 1;  
    if(count($monkeys) == 1){  
        echo$monkeys[0]."成为猴王了";  
        return;  
    }  
    else{  
        while($num++ < $m){  
            $current++ ;  
            $current = $current%$number;  
        }  
        echo$monkeys[$current]."的猴子被踢掉了<br/>";  
        array_splice($monkeys , $current , 1);  
        killMonkey($monkeys , $m , $current);  
    }  
}  
$monkeys = array(1 , 2 , 3 , 4 , 5 , 6 , 7, 8 , 9 , 10); //monkeys的编号
$m = 3; //数到第几只猴子被踢出
killMonkey($monkeys , $m);

Method 3, linear table application

1. function yuesefu($n,$m) {    
       $r=0;    
       for($i=2; $i<=$n; $i++) {  
           $r=($r+$m)%$i;    
       }  
       return$r+1;    
   }    
   echo yuesefu(10,3)."是猴王";

   The above is the detailed content of How to solve php Joseph problem. For more information, please follow other related articles on the PHP Chinese website!