讲故事了!
约瑟夫环问题起源于一个犹太故事。： 罗马人攻占了桥塔帕特，41个人藏在一个山洞中躲过了这场浩劫。这41个人中，包括历史学家Josephus（约瑟夫）和他的一个朋友。剩余的39个人为了表示不向罗马人屈服，决定集体自杀。大家制定了一个自杀方案，所有这41个人围成一个圆圈，由第一个人开始顺时针报数，每报数为3的人就立刻自杀，然后再由下一个人重新开始报数，仍然是每报数为3的人就立刻自杀……，直到所有的人都自杀身亡为止。 约瑟夫和他的朋友并不想自杀，于是约瑟夫想到了一个计策，他们两个同样参与到自杀方案中，但是最后却躲过了自杀。请问，他们是怎么做到的？ 分析这道题思路有很多种,我的思路分为两步第一步 抽象成一个队列添加元素到另一个队列中
假设队列A中有n个元素,队A不断进行出队操作,每次元素出队后都判断元素是否符合添加到队B的条件(结合约瑟夫环问题就是:如果是3的倍数,就不符合入队的条件)第二步 改进第一步 可以认为是一个队S,这个队S在不断进行出队和入队的操作(就是出队的元素再次添加到队尾),如果出队元素为不符合再次入队的条件就踢出.相关函数 range() count() array_shift() array_push()
代码实现
function ysf($n,$m){ $i=0; $arr = range(1,$n);//创建:含有100个值的数组 while(count($arr)>1) { ++$i; //不断出队(即删除数组的第一个元素) $survice = array_shift($arr); if($i%$m<>0){ //结合约瑟夫环问题 //报到3就自杀(从队列中踢出),否则等待下一次的审判(再次添加到队尾) array_push($arr, $survice); } elseif($i>count($survice)){$i=0;}#这句代码加不加都无所谓,便于理解 } return $arr;}print_r( ysf(41,3) );######console################Array( [0] => 16 [1] => 31 )这里封装成函数的理由很简单,当我需要的时候,我就能调用它逃过一死了(哈哈哈....) 总结 这个方法执行效率不是太高 .因为操作代价有点大….
function jesph(int $n,int $m){ $arr=range(1,$n); print_r($arr); $count=$n; $k=1;$j=1; $unset=[]; while($count>1){ while(in_array($j,$unset)){ $j++; if($j>$n) $j=1; continue 2; } if($k==$m){ unset($arr[$j]); $unset[]=$j; $count=count($arr); $k=1; }else{ $k++; } $j++; if($j>$n) $j=1; } echo current($arr);}jesph(10,3);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]."的猴子被踢掉了\n"; array_splice($monkeys , $current , 1); killMonkey($monkeys , $m , $current); }}$monkeys = range(1,41);//array(1 , 2 , 3 , 4 , 5 , 6 , 7, 8 , 9 , 10); //monkeys的编号$m = 3; //数到第几只猴子被踢出killMonkey($monkeys , $m);function ysf($n,$m){ $i=0; $arr = range(1,$n);//创建:含有100个值的数组 while(count($arr)>1) { ++$i; //不断出队(即删除数组的第一个元素) $survice = array_shift($arr); if($i%$m<>0){ //结合约瑟夫环问题 //报到3就自杀(从队列中踢出),否则等待下一次的审判(再次添加到队尾) array_push($arr, $survice); } elseif($i>count($survice)){$i=0;}#这句代码加不加都无所谓,便于理解 } return $arr;}print_r( ysf(41,3) ); https://www.cnblogs.com/china90/p/7367396.html
#includeint f(int n, int m){ int s = 0; for (int i = 2; i <= n; i++) s = (s + m) % i; return s;}void main(int agrc,char *argv[]){printf("dasfd ====== %d",f(41,3));}
https://www.cnblogs.com/z-sm/p/4257092.html