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

约瑟夫问题：

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

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

/** * 链表结构 */class Child{ public $no; public $next=null; public function __construct($no=null){ $this->no = $no; }}/** * 链表操作 */class CycleLink{ private $nodeNum = 0; /** * 添加节点 */ public function addNode($head,$node) { $currentNode = $head; while ($currentNode->next!=null && $currentNode->next!=$head) { $currentNode = $currentNode->next; } $currentNode->next = $node; $currentNode->next->next = $head; $this->nodeNum++; } /** * 删除节点 */ public function delNode($head,$no) { $currentNode = $head; while ($currentNode->next!=$head) { if($currentNode->next->no==$no){ $currentNode->next = $currentNode->next->next; $this->nodeNum--; break; } $currentNode = $currentNode->next; } } /** * 获取节点数量 */ public function getNodeNum(){ return $this->nodeNum; } /** * 查找节点 */ public function findNode($head,$no){ $node = null; $currentNode = $head; while ($currentNode->next!=$head) { if($currentNode->next->no==$no){ $node = $currentNode->next; break; } $currentNode = $currentNode->next; } return $node; } public function getNextNode($head,$node){ if($node->next==$head){ return $node->next->next; } return $node->next; } /** * 显示节点 */ public function showNode($head) { echo "<br/><br/>"; $currentNode = $head; while ($currentNode->next!=$head){ $currentNode = $currentNode->next; echo '第 '.$currentNode->no.' 名小孩<br/>'; } }}/** * 约瑟夫问题 * 设编号为1，2，...n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列， * 它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。 * 并求出最后出列的人是哪个？ */class Josephu{ private $head; private $childList; private $k; private $m; private $n; public function __construct($n,$k,$m){ $this->k = $k; $this->m = $m; $this->n = $n; $this->createList($n); // 创建小孩 echo "<br/><br/>当前有 {$n} 个小孩，从第 {$k} 个小孩开始报数，数到 {$m} 退出<br/><br/>"; } // 数数 public function exec(){ $currentNode = $this->childList->findNode($this->head,$this->k); // 获取第一个开始报数的人 $_num = 0; // 当前数到的值 $surplus_num = $this->n; // 开始报数 while ($surplus_num>1) { // 只要人数大于1，就继续报数 // 当前报数值 $_num++; $nextNode = $this->childList->getNextNode($this->head,$currentNode); // 数至第m个数，然后将其移除。报数恢复到0，重新循环。 if( $_num==$this->m ){ $_num = 0; $surplus_num--; // 当前小孩退出 $this->childList->delNode($this->head,$currentNode->no); echo '<br/>退出小孩编号：' . $currentNode->no; } // 移动到下一个小孩 $currentNode = $nextNode; } echo '<br/>最后一个小孩编号：' . $currentNode->no; } // 创建小孩 private function createList($n){ $this->childList = new CycleLink(); $this->head = new Child(); for ($i=1;$i<=$n;$i++){ $node = new Child($i); $this->childList->addNode($this->head,$node); } $this->childList->showNode($this->head); }}$josephu = new Josephu(4, 1, 2);$josephu->exec();

运行结果：

第 1 名小孩
第 2 名小孩
第 3 名小孩
第 4 名小孩

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

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

希望本文所述对大家PHP程序设计有所帮助。