约瑟夫算法

猴子选大王
通过问题模型分析,数量n猴子喊数m的踢出队伍,当第一次踢出猴子时,后面的猴子重新喊数,则可看成子问题。故分治算法。

子问题与父问题变化为对应位置的变化,故可以建立子问题和父问题的位置映射关系方程p(x)=(x+m)%n。

通过得到关系方程,从结果逐步逆推结果的上一次对应位置,来最终获取到初始时的有效位置,则获取到最终结果。
(经典算法,约瑟夫曲线)。

即算法例子:
($n猴子数量,$m报数,$p各个子问题位置)
$dara=array_fill(1,$n);
$p=0;
for ($i=2;$i<$n-1;$i++) {
$p=($p+$m) % $n;
}
return $p+1;

坚持原创技术分享,您的支持将鼓励我继续创作!