本文实例讲述了PHP使用环形链表解决约瑟夫问题。分享给大家供大家参考，具体如下：
约瑟夫问题：
Josephu问题为：设编号为1，2，...n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。并求出最后出列的人是哪个？
PHP实现环形链表以及约瑟夫问题的解决：
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 "
"; $currentNode = $head; while ($currentNode->next!=$head){ $currentNode = $currentNode->next; echo '第 '.$currentNode->no.' 名小孩
'; } } } /* //创建一个head头,该head 只是一个头，不放入数据 $head = new Child(); $childList = new CycleLink(); $child_1 = new Child(1); $child_2 = new Child(2); $child_3 = new Child(3); $child_4 = new Child(4); $childList->addNode($head,$child_1); $childList->addNode($head,$child_2); $childList->addNode($head,$child_3); $childList->addNode($head,$child_4); $childList->showNode($head); echo "
"; $currentNode = $head; while ($currentNode->next!=$head){ $currentNode = $currentNode->next; echo '第 '.$currentNode->no.' 名小孩
'; } } } /* //创建一个head头,该head 只是一个头，不放入数据 $head = new Child(); $childList = new CycleLink(); $child_1 = new Child(1); $child_2 = new Child(2); $child_3 = new Child(3); $child_4 = new Child(4); $childList->addNode($head,$child_1); $childList->addNode($head,$child_2); $childList->addNode($head,$child_3); $childList->addNode($head,$child_4); $childList->showNode($head); echo "
";
var_dump($head);
$findNode = $childList->findNode($head,3);
echo "";
var_dump($findNode);
$childList->delNode($head,2);
$childList->showNode($head);
echo $childList->getNodeNum();
exit();
*/
/**
* 约瑟夫问题
* 设编号为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 "
当前有 {$n} 个小孩，从第 {$k} 个小孩开始报数，数到 {$m} 退出
";
}
// 数数
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 '
退出小孩编号：' . $currentNode->no;
}
// 移动到下一个小孩
$currentNode = $nextNode;
}
echo '
最后一个小孩编号：' . $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程序设计有所帮助。
原文链接：https://www.f2er.com/php/15775.html