约瑟夫环(Josephus)

算法 admin 333℃ 0评论

约瑟夫环问题起源还挺有意思的,这是个一个犹太故事:

罗马人攻占了桥塔帕特,41个人藏在一个山洞中躲过了这场浩劫。这41个人中,包括历史学家Josephus(约瑟夫)和他的一个朋友。剩余的39个人为了表示不向罗马人屈服,决定集体自杀。大家制定了一个自杀方案,所有这41个人围成一个圆圈,由第一个人开始顺时针报数,每报数为3的人就立刻自杀,然后再由下一个人重新开始报数,仍然是每报数为3的人就立刻自杀……,直到所有的人都自杀身亡为止。

约瑟夫和他的朋友并不想自杀,于是约瑟夫想到了一个计策,他们两个同样参与到自杀方案中,但是最后却躲过了自杀。请问,他们是怎么做到的?

问题生死攸关,不得不解:

function josefu($n, $m){
	$arr = range(1, $n);
	$i = 0;

	while(count($arr)>1){
		$head = array_shift($arr);
		$i = $i+1;

		//如果刚好为m,则丢弃,否则直接加入未尾
		if($i % $m != 0){
			array_push($arr, $head);
		}
	}

	return $arr[0];
}

echo josefu(4,2);

 

这是一种简单的迭代模块,也有递规的方式

这里再贴一种模拟推导:

int cir(int n,int m)
{
    int p=0;
    for(int i=2;i<=n;i++)
    {
        p=(p+m)%i;
    }
    return p+1;
}

这种相当于直接利用推导公式:f(N,M)=(f(N1,M)+M)%n

 

真的要找工作了,好好看点算法的东西,过过坎。

最近发现高等数学复习起来也不是那么难,所以在这段找工作期间,也会过一些数学知识。太新的东西就先不用接触了,好好复习学过的了解过的东西,框架,算法,数学知识,php mysql知识点,分布式,缓存的一些应用知识点,看看laravel, 再过点python的东西差不多了

学习是持续的事情,以后的工作中,尽量少分心去看影响自己前进的东西,集中自己的精力去做一些东西会更适合自己

转载请注明:朋克网 » 约瑟夫环(Josephus)

喜欢 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址