环形链表解决约瑟夫问题-PHP源码
php代码:
//环形链表
/*
解决约瑟夫问题
设定编号1-n个人 约定起始编号k的人从1开始报数,报到m的那个人出列。他的下一位又从1开始报数,数到M的那个人又出列,
依次类推,直到所有人都出列为止,求出列顺序,和最后出列编号
*/
header("content-type:text/html;charset=utf-8");
class Child{
public $no;
public $next=null;
public function __construct($no){
$this->no=$no;
}
}
function addChild(&$first,$n)
{
$cur=null;
for($i=0;$i<=$n-1;$i++){
$child = new child($i+1);
if($i==0){
$first = $child;
$first->next=$child;
$cur=$first;
}else{
$cur->next=$child;
$child->next=$first;
$cur=$cur->next;
}
}
}
function showChild($first){
$cur=$first;
while($cur->next != $first){
echo $cur->no;
$cur=$cur->next;
}
echo $cur->no;
}
function countChild($first,$m,$k)
{
$tail=$first;
//考虑从第几个孩子开始
for($i=0;$i<$m-1;$i++){
$tail=$tail->next;
}
while($tail->next!=$tail) //剔除到链表中只有一个元素为止
{
for($i=0;$i<$k-1;$i++){
$cur=$tail;//记录他的前一个位置
$tail=$tail->next;
}
echo '出列人'.$tail->no;
$cur->next=$tail->next;
$tail=$tail->next;
}
echo '111'.$tail->no;
}
addChild($first,10);
showChild($first);
echo "
";
countChild($first,2,3); //第二个小孩开始数,数到三出列
/phpyy/49060.htmlwww.phpzy.comtrue/phpyy/49060.htmlTechArticle环形链表解决约瑟夫问题-PHP源码 php代码: //环形链表 /* 解决约瑟夫问题 设定编号1-n个人 约定起始编号k的人从1开始报数,报到m的那个人出列。他的下一位又从1开始报数,数到M的那个...
PHP之友评论