本文实例讲述了PHP使用栈解决约瑟夫环问题算法。分享给大家供大家参考，具体如下：
约瑟夫环问题： 39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀。然后下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
<?phpclass 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)); |
执行结果：
|
1
2
3
4
5
|
Array( [0] => 16 [1] => 31) |
希望本文所述对大家PHP程序设计有所帮助。
原文链接：http://blog.csdn.net/alian_c/article/details/53319319
