约瑟夫环问题

2017-03-04 16:12 Posted in Learn with PHP , algorithm

约瑟夫环问题描述：

一群猴子排成一圈，按 1,2,…,n 依次编号。然后从第 1 只开始数，数到第 m 只,把它踢出圈，从它后面再开始数，再数到第 m 只，在把它踢出去…，如此不停的进行下去，直到最后只剩下一只猴子为止，那只猴子就叫做大王。要求编程模拟此过程，输入 m、n, 输出最后那个大王的编号。

php实现：

<?php
/*
* @param int|array $monkeys
* @param int $m the interval value
* @output monkey king's number
**/
function monkeyKing($monkeys, $m)
{
	if (is_array($monkeys))
	{
		$arr = $monkeys;
	}
	else
	{
		for ($i = 1; $i <= $monkeys; $i++)
		{
			$arr[$i] = $i;
		}
	}
	
	//not find yet
	while (count($arr) > 1)
    {
        //start to find
        for ($counter = 1; $counter <= $m; $counter++)
        {
            if (next($arr))
            {
                if ($counter == $m)
                {
                    unset ($arr[array_search(prev($arr), $arr)]);
                }
            }
            else
            {
                //if we reach the bottom of monkey array, then reset array pointer
                reset ($arr);
                //the monkey that should be kicked out is at bottom of the array
                if ($counter == $m)
                {
                    unset ($arr[array_search(end($arr), $arr)]);
                    reset ($arr);
                }
            }
        }
    }
    
    echo 'No.' . current($arr) . ' is monkey king';
}

BlueBreeze

Blog

约瑟夫环问题