算法之约瑟夫环研究

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

 1)   {
	    $t = $m%$c+$t;     //用循环截数来模当前数组圈子中的人数,得到起始位(起始位要加上原来的起始位)
		//echo '$t_0:'.$t.'
'; if($t>$c) $t=$t%$c;//溢出:如果起始位比圈中总人数大,则取模,看它循环到哪一位了。如$c=7,$t=8,余数为1 echo '$t_1:' .$t. '
'; $t=$t>0 ? --$t : 0; //数组中下标是从0开始的故--$t,如果$t<=0,情况:取模为0,则起始位为最后一位。 //echo '$t_2:'.$t.'
'; array_splice($a,$t,1);   //将不幸的兄弟踢出去 --$c;                    //圈中人数减一 if($t==0) $t=$c;         //如果$t=0表示起始位为最后一位,此时将$t置为$c,表示从最后一位开始数数 //echo '$c:'.$c; } return reset($a); } $n = 10; $m = 3; $king = getKingMonkey1($n,$m); echo $king; ?>

相关文章

发表评论

返回顶部