作者:倒叙的时光_SX_126 | 来源:互联网 | 2018-03-20 18:37
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 &#39;出列人&#39;.$tail->no;
$cur->next=$tail->next;
$tail=$tail->next;
}
echo &#39;111&#39;.$tail->no;
}
addChild($first,10);
showChild($first);
echo "
";
countChild($first,2,3); //第二个小孩开始数,数到三出列