php使用环形链表解决约瑟夫问题完整示例
本文实例讲述了php使用环形链表解决约瑟夫问题。分享给大家供大家参考，具体如下：
约瑟夫问题：
Josephu问题为：设编号为1，2，...n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。并求出最后出列的人是哪个？
PHP实现环形链表以及约瑟夫问题的解决：
/**
*链表结构
*/
classChild{
public$no;
public$next=null;
publicfunction__construct($no=null){
$this->no=$no;
}
}
/**
*链表操作
*/
classCycleLink{
private$nodeNum=0;
/**
*添加节点
*/
publicfunctionaddNode($head,$node)
{
$currentNode=$head;
while($currentNode->next!=null&&$currentNode->next!=$head){
$currentNode=$currentNode->next;
}
$currentNode->next=$node;
$currentNode->next->next=$head;
$this->nodeNum++;
}
/**
*删除节点
*/
publicfunctiondelNode($head,$no)
{
$currentNode=$head;
while($currentNode->next!=$head){
if($currentNode->next->no==$no){
$currentNode->next=$currentNode->next->next;
$this->nodeNum--;
break;
}
$currentNode=$currentNode->next;
}
}
/**
*获取节点数量
*/
publicfunctiongetNodeNum(){
return$this->nodeNum;
}
/**
*查找节点
*/
publicfunctionfindNode($head,$no){
$node=null;
$currentNode=$head;
while($currentNode->next!=$head){
if($currentNode->next->no==$no){
$node=$currentNode->next;
break;
}
$currentNode=$currentNode->next;
}
return$node;
}
publicfunctiongetNextNode($head,$node){
if($node->next==$head){
return$node->next->next;
}
return$node->next;
}
/**
*显示节点
*/
publicfunctionshowNode($head)
{
echo"
";
$currentNode=$head;
while($currentNode->next!=$head){
$currentNode=$currentNode->next;
echo'第'.$currentNode->no.'名小孩
';
}
}
}
/*
//创建一个head头,该head只是一个头，不放入数据
$head=newChild();
$childList=newCycleLink();
$child_1=newChild(1);
$child_2=newChild(2);
$child_3=newChild(3);
$child_4=newChild(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的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
*并求出最后出列的人是哪个？
*/
classJosephu{
private$head;
private$childList;
private$k;
private$m;
private$n;
publicfunction__construct($n,$k,$m){
$this->k=$k;
$this->m=$m;
$this->n=$n;
$this->createList($n);//创建小孩
echo"
当前有{$n}个小孩，从第{$k}个小孩开始报数，数到{$m}退出
";
}
//数数
publicfunctionexec(){
$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;
}
//创建小孩
privatefunctioncreateList($n){
$this->childList=newCycleLink();
$this->head=newChild();
for($i=1;$i<=$n;$i++){
$node=newChild($i);
$this->childList->addNode($this->head,$node);
}
$this->childList->showNode($this->head);
}
}
$josephu=newJosephu(4,1,2);
$josephu->exec();
运行结果：
第1名小孩
第2名小孩
第3名小孩
第4名小孩
当前有4个小孩，从第1个小孩开始报数，数到2退出
更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》
希望本文所述对大家PHP程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。