This article describes the problem of solving the Joseph ring based on a circular linked list. Share it for your reference, as follows:
Let’s first review the problem of Joseph’s ring: N people form a circle, start counting from the first one, the M-th one will be killed, and the last one will be left, and the rest will be killed. For example, N=6, M=5, the order of being killed is: 5, 4, 6, 2, 3, 1.
It was introduced earlierHow to solve the Joseph ring with associative array, The method of solving Joseph's ring in a circular linked list is as follows:
<?php
header("content-type:text/html;charset=utf-8");
class Child{
public $no;
public $next=null;
public function __construct($no){
$this->no=$no;
}
}
function addChild($n,&$first){ //$n is the number of people, create a ring link table for($i=0;$i<$n;$i++){
$child=new Child($i+1);
if($i==0){
$first=$child;
$cur=$child;
$cur->next=$cur;
}else{
$cur->next=$child;
$child->next=$first;
$cur=$cur->next;
}
}
}
function showHero($first){
$cur=$first;
while($cur->next!=$first){
echo "<br/>People's number:".$cur->no;
$cur=$cur->next;
}
echo "<br/>People's number:".$cur->no;
}
function countChild($first,$m,$k){
$cur=$first;
for($i=0;$i<$m-1;$i++){
$cur=$cur->next;
}
$j=0;
while($cur!=$cur->next){
if($j==$k-2){
echo "<br/>Delist number:".$cur->next->no;
$cur->next=$cur->next->next;
$cur=$cur->next;
$j=0;
}else{
$cur=$cur->next;
$j++;
}
}
echo "<br/>Last delisting number:".$cur->no;
}
addChild(10,$first);
showHero($first);
echo "<hr/>";
countChild($first,2,3); //The second person starts counting and counts to three and departs the column?>
Running results:
People's number：1 People's number：2 People's number：3 People's number：4 People's number：5 People's number：6 People's number：7 People's number：8 People's number：9 People's number：10 -------------------------------------------------------------------------------- Delisting number：4 Delisting number：7 Delisting number：10 Delisting number：3 Delisting number：8 Delisting number：2 Delisting number：9 Delisting number：6 Delisting number：1 最后Delisting number：5
For more information about PHP related content, please check out the topic of this site:PHP data structure and algorithm tutorial》、《Summary of PHP Programming Algorithm》、《Summary of usage of php strings》、《Complete collection of PHP array (Array) operation techniques》、《Summary of common traversal algorithms and techniques for PHP"and"Summary of PHP mathematical operation skills》
I hope this article will be helpful to everyone's PHP programming.