这篇文章主要介绍了php基于环形链表解决约瑟夫环问题,结合具体实例形式分析了php环形链表的定义及基于环形链表解决约瑟夫环的具体步骤与相关操作技巧,需要的朋友可以参考下。

本文实例讲述了php基于环形链表解决约瑟夫环问题，分享给大家供大家参考，具体如下：

先来重温一下约瑟夫环问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是:5，4，6，2，3，1。

前面介绍了关联数组解决约瑟夫环的方法，环形链表解决约瑟夫环的方法如下：

1. <?php 
2. header("content-type:text/html;charset=utf-8"); 
3. class Child{ 
4. public $no; 
5. public $next=null; 
6. public function __construct($no){ 
7. $this->no=$no; 
8.    } 
9. } 
10. function addChild($n,&$first){    //$n是人的个数，创建环形链表 
11.   for($i=0;$i<$n;$i++){ 
12.     $child=new Child($i+1); 
13.     if($i==0){ 
14.     $first=$child; 
15.     $cur=$child; 
16.     $cur->next=$cur; 
17.     }else{ 
18.     $cur->next=$child; 
19.     $child->next=$first; 
20.     $cur=$cur->next; 
21.          } 
22.    } 
23. } 
24. function showHero($first){ 
25. $cur=$first; 
26. while($cur->next!=$first){ 
27. echo "<br/>人的编号：".$cur->no; 
28. $cur=$cur->next; 
29.      } 
30.      echo "<br/>人的编号：".$cur->no; 
31. } 
32. function countChild($first,$m,$k){ 
33.   $cur=$first; 
34.   for($i=0;$i<$m-1;$i++){ 
35.   $cur=$cur->next; 
36.   } 
37.   $j=0; 
38.   while($cur!=$cur->next){ 
39.     if($j==$k-2){ 
40.       echo "<br/>出列编号：".$cur->next->no; 
41.       $cur->next=$cur->next->next; 
42.       $cur=$cur->next; 
43.       $j=0; 
44.     }else{ 
45.       $cur=$cur->next; 
46.       $j++; 
47.     } 
48.   } 
49.   echo "<br/>最后出列编号：".$cur->no; 
50. } 
51. addChild(10,$first); 
52. showHero($first); 
53. echo "<hr/>"; 
54. countChild($first,2,3); //第二个人开始数，数到三出列 
55. ?> 

运行结果：

1. 人的编号：1 
2. 人的编号：2 
3. 人的编号：3 
4. 人的编号：4 
5. 人的编号：5 
6. 人的编号：6 
7. 人的编号：7 
8. 人的编号：8 
9. 人的编号：9 
10. 人的编号：10 
11. -------------------------------------------------------------------------------- 
12.  
13. 出列编号：4 
14. 出列编号：7 
15. 出列编号：10 
16. 出列编号：3 
17. 出列编号：8 
18. 出列编号：2 
19. 出列编号：9 
20. 出列编号：6 
21. 出列编号：1 
22. 最后出列编号：5

Tags: php环形链表 php约瑟夫环

分享到：