本文实例讲述了php使用环形链表解决约瑟夫问题，分享给大家供大家参考，具体如下：

约瑟夫问题：

Josephu问题为：设编号为1，2，...n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。并求出最后出列的人是哪个？

PHP实现环形链表以及约瑟夫问题的解决：

1. /** 
2.  * 链表结构 
3.  */ 
4. class Child{ 
5.   public $no; 
6.   public $next=null; 
7.   public function __construct($no=null){ 
8.     $this->no = $no; 
9.   } 
10. } 
11. /** 
12.  * 链表操作 
13.  */ 
14. class CycleLink{ 
15.   private $nodeNum = 0; 
16.   /** 
17.    * 添加节点 
18.    */ 
19.   public function addNode($head,$node) 
20.   { 
21.     $currentNode = $head; 
22.     while ($currentNode->next!=null && $currentNode->next!=$head) { 
23.       $currentNode = $currentNode->next; 
24.     } 
25.     $currentNode->next = $node; 
26.     $currentNode->next->next = $head; 
27.     $this->nodeNum++; 
28.   } 
29.   /** 
30.    * 删除节点 
31.    */ 
32.   public function delNode($head,$no) 
33.   { 
34.     $currentNode = $head; 
35.     while ($currentNode->next!=$head) { 
36.       if($currentNode->next->no==$no){ 
37.         $currentNode->next = $currentNode->next->next; 
38.         $this->nodeNum--; 
39.         break; 
40.       } 
41.       $currentNode = $currentNode->next; 
42.     } 
43.   } 
44.   /** 
45.    * 获取节点数量 
46.    */ 
47.   public function getNodeNum(){ 
48.     return $this->nodeNum; 
49.   } 
50.   /** 
51.    * 查找节点 
52.    */ 
53.   public function findNode($head,$no){ 
54.     $node = null; 
55.     $currentNode = $head; 
56.     while ($currentNode->next!=$head) { 
57.       if($currentNode->next->no==$no){ 
58.         $node = $currentNode->next; 
59.         break; 
60.       } 
61.       $currentNode = $currentNode->next; 
62.     } 
63.     return $node; 
64.   } 
65.   public function getNextNode($head,$node){ 
66.     if($node->next==$head){ 
67.       return $node->next->next; 
68.     } 
69.     return $node->next; 
70.   } 
71.   /** 
72.    * 显示节点 
73.    */ 
74.   public function showNode($head) 
75.   { 
76.     echo "<br/><br/>"; 
77.     $currentNode = $head; 
78.     while ($currentNode->next!=$head){ 
79.       $currentNode = $currentNode->next; 
80.       echo '第 '.$currentNode->no.' 名小孩<br/>'; 
81.     } 
82.   } 
83. } 
84. /* 
85. //创建一个head头,该head 只是一个头，不放入数据 
86. $head     = new Child(); 
87. $childList   = new CycleLink(); 
88. $child_1   = new Child(1); 
89. $child_2   = new Child(2); 
90. $child_3   = new Child(3); 
91. $child_4   = new Child(4); 
92. $childList->addNode($head,$child_1); 
93. $childList->addNode($head,$child_2); 
94. $childList->addNode($head,$child_3); 
95. $childList->addNode($head,$child_4); 
96. $childList->showNode($head); 
97. echo "<pre>"; 
98. var_dump($head); 
99. $findNode = $childList->findNode($head,3); 
100. echo "<pre>"; 
101. var_dump($findNode); 
102. $childList->delNode($head,2); 
103. $childList->showNode($head); 
104. echo $childList->getNodeNum(); 
105. exit(); 
106. */ 
107. /** 
108.  * 约瑟夫问题 
109.  * 设编号为1，2，...n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列， 
110.  * 它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。 
111.  * 并求出最后出列的人是哪个？ 
112.  */ 
113. class Josephu{ 
114.   private $head; 
115.   private $childList; 
116.   private $k; 
117.   private $m; 
118.   private $n; 
119.   public function __construct($n,$k,$m){ 
120.     $this->k = $k; 
121.     $this->m = $m; 
122.     $this->n = $n; 
123.     $this->createList($n);  // 创建小孩 
124.     echo "<br/><br/>当前有 {$n} 个小孩，从第 {$k} 个小孩开始报数，数到 {$m} 退出<br/><br/>"; 
125.   } 
126.   // 数数 
127.   public function exec(){ 
128.     $currentNode = $this->childList->findNode($this->head,$this->k);  // 获取第一个开始报数的人 
129.     $_num = 0;  // 当前数到的值 
130.     $surplus_num = $this->n; 
131.     // 开始报数 
132.     while ($surplus_num>1) {  // 只要人数大于1，就继续报数 
133.       // 当前报数值 
134.       $_num++; 
135.       $nextNode = $this->childList->getNextNode($this->head,$currentNode); 
136.       // 数至第m个数，然后将其移除。报数恢复到0，重新循环。 
137.       if( $_num==$this->m ){ 
138.         $_num = 0; 
139.         $surplus_num--; 
140.         // 当前小孩退出 
141.         $this->childList->delNode($this->head,$currentNode->no); 
142.         echo '<br/>退出小孩编号：' . $currentNode->no; 
143.       } 
144.       // 移动到下一个小孩 
145.       $currentNode = $nextNode; 
146.     } 
147.     echo '<br/>最后一个小孩编号：' . $currentNode->no; 
148.   } 
149.   // 创建小孩 
150.   private function createList($n){ 
151.     $this->childList = new CycleLink(); 
152.     $this->head = new Child(); 
153.     for ($i=1;$i<=$n;$i++){ 
154.       $node = new Child($i); 
155.       $this->childList->addNode($this->head,$node); 
156.     } 
157.     $this->childList->showNode($this->head); 
158.   } 
159. } 
160. $josephu = new Josephu(4, 1, 2); 
161. $josephu->exec(); 

运行结果：

第 1 名小孩

第 2 名小孩

第 3 名小孩

第 4 名小孩

当前有 4 个小孩，从第 1 个小孩开始报数，数到 2 退出

Tags: php环形链表 php约瑟夫

分享到：