本篇文章为大家展示了PHP中怎么利用栈解决约瑟夫环问题,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。
约瑟夫环问题: 39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀。然后下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
<?php class ArrayStack { private $size; private $stack = []; public function __construct(){} public function buildStack($num){ $this->size = $num; $index = 0; while($index ++ < $this->size) { $this->stack[] = $index; } } public function pop(){ $item = array_shift($this->stack); $this->size = count($this->stack); return $item; } public function push($item) { $this->stack[] = $item; $this->size = count($this->stack); } public function size() { return $this->size; } public function stack() { return $this->stack; } } interface Joseph { public function handle($num = 0, $step = 0, $survivors = 0); } class StackJoseph implements Joseph { protected $stack; protected $num; protected $step; public function __construct(ArrayStack $stack) { $this->stack = $stack; } public function handle($num = 0, $step = 0, $survivors = 0) { // TODO: Implement handle() method. $this->stack->buildStack($num); $i = 0; while($this->stack->size() > $survivors) { $pop = $this->stack->pop(); if(($i + 1) % $step !== 0) { $this->stack->push($pop); $i ++; } else { $i = 0; } } return $this->stack->stack(); } } function joseph($num, $step, $survivorsNum) { $arrayStack = new ArrayStack(); $joseph = new StackJoseph($arrayStack); return $joseph->handle($num, $step, $survivorsNum); } print_r(joseph(41, 3, 2));
执行结果:
Array ( [0] => 16 [1] => 31 )
上述内容就是PHP中怎么利用栈解决约瑟夫环问题,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。