源码网,源码论坛,源码之家,商业源码,游戏源码下载,discuz插件,棋牌源码下载,精品源码论坛

 找回密码
 立即注册
查看: 226|回复: 24

[PHP编程] php使用环形链表解决约瑟夫问题完整示例

[复制链接]

7万

主题

861

回帖

32万

积分

论坛元老

Rank: 8Rank: 8

积分
329525
发表于 2018-8-7 11:30:48 | 显示全部楼层 |阅读模式
这篇文章主要介绍了php使用环形链表解决约瑟夫问题,简单描述了约瑟夫问题并结合实例形式分析了php基于环形链表解决约瑟夫问题的相关操作技巧,注释中包含较为详尽的说明便于理解,需要的朋友可以参考下

本文实例讲述了php使用环形链表解决约瑟夫问题。分享给大家供大家参考,具体如下:

约瑟夫问题:

Josephu问题为:设编号为1,2,...n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。并求出最后出列的人是哪个?

PHP实现环形链表以及约瑟夫问题的解决:

/**
 * 链表结构
 */
class Child{
  public $no;
  public $next=null;
  public function __construct($no=null){
    $this->no = $no;
  }
}
/**
 * 链表操作
 */
class CycleLink{
  private $nodeNum = 0;
  /**
   * 添加节点
   */
  public function addNode($head,$node)
  {
    $currentNode = $head;
    while ($currentNode->next!=null && $currentNode->next!=$head) {
      $currentNode = $currentNode->next;
    }
    $currentNode->next = $node;
    $currentNode->next->next = $head;
    $this->nodeNum++;
  }
  /**
   * 删除节点
   */
  public function delNode($head,$no)
  {
    $currentNode = $head;
    while ($currentNode->next!=$head) {
      if($currentNode->next->no==$no){
        $currentNode->next = $currentNode->next->next;
        $this->nodeNum--;
        break;
      }
      $currentNode = $currentNode->next;
    }
  }
  /**
   * 获取节点数量
   */
  public function getNodeNum(){
    return $this->nodeNum;
  }
  /**
   * 查找节点
   */
  public function findNode($head,$no){
    $node = null;
    $currentNode = $head;
    while ($currentNode->next!=$head) {
      if($currentNode->next->no==$no){
        $node = $currentNode->next;
        break;
      }
      $currentNode = $currentNode->next;
    }
    return $node;
  }
  public function getNextNode($head,$node){
    if($node->next==$head){
      return $node->next->next;
    }
    return $node->next;
  }
  /**
   * 显示节点
   */
  public function showNode($head)
  {
    echo "<br/><br/>";
    $currentNode = $head;
    while ($currentNode->next!=$head){
      $currentNode = $currentNode->next;
      echo '第 '.$currentNode->no.' 名小孩<br/>';
    }
  }
}
/*
//创建一个head头,该head 只是一个头,不放入数据
$head     = new Child();
$childList   = new CycleLink();
$child_1   = new Child(1);
$child_2   = new Child(2);
$child_3   = new Child(3);
$child_4   = new Child(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 "<pre>";
var_dump($head);
$findNode = $childList->findNode($head,3);
echo "<pre>";
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的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。
 * 并求出最后出列的人是哪个?
 */
class Josephu{
  private $head;
  private $childList;
  private $k;
  private $m;
  private $n;
  public function __construct($n,$k,$m){
    $this->k = $k;
    $this->m = $m;
    $this->n = $n;
    $this->createList($n);  // 创建小孩
    echo "<br/><br/>当前有 {$n} 个小孩,从第 {$k} 个小孩开始报数,数到 {$m} 退出<br/><br/>";
  }
  // 数数
  public function exec(){
    $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 '<br/>退出小孩编号:' . $currentNode->no;
      }
      // 移动到下一个小孩
      $currentNode = $nextNode;
    }
    echo '<br/>最后一个小孩编号:' . $currentNode->no;
  }
  // 创建小孩
  private function createList($n){
    $this->childList = new CycleLink();
    $this->head = new Child();
    for ($i=1;$i<=$n;$i++){
      $node = new Child($i);
      $this->childList->addNode($this->head,$node);
    }
    $this->childList->showNode($this->head);
  }
}
$josephu = new Josephu(4, 1, 2);
$josephu->exec();

运行结果:

第 1 名小孩
第 2 名小孩
第 3 名小孩
第 4 名小孩


当前有 4 个小孩,从第 1 个小孩开始报数,数到 2 退出

更多关于PHP相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结

希望本文所述对大家PHP程序设计有所帮助。

回复

使用道具 举报

0

主题

1万

回帖

0

积分

中级会员

Rank: 3Rank: 3

积分
0
发表于 2022-12-5 23:38:06 | 显示全部楼层
的vgdsvsdvdsvdsvds
回复 支持 反对

使用道具 举报

0

主题

8878

回帖

0

积分

中级会员

Rank: 3Rank: 3

积分
0
发表于 2022-12-6 18:59:21 | 显示全部楼层
天天源码社区。。。。
回复 支持 反对

使用道具 举报

0

主题

2万

回帖

0

积分

中级会员

Rank: 3Rank: 3

积分
0
发表于 2023-2-13 15:11:34 | 显示全部楼层
老大你好你好好你好
回复 支持 反对

使用道具 举报

2

主题

2万

回帖

69

积分

注册会员

Rank: 2

积分
69
发表于 2023-3-20 18:11:01 | 显示全部楼层
很不错的源码论坛
回复 支持 反对

使用道具 举报

2

主题

2万

回帖

221

积分

中级会员

Rank: 3Rank: 3

积分
221
发表于 2023-3-30 04:26:44 | 显示全部楼层
很好,谢谢分享
回复 支持 反对

使用道具 举报

3

主题

2万

回帖

50

积分

注册会员

Rank: 2

积分
50
发表于 2023-8-14 15:39:09 | 显示全部楼层
撒房产税陈飞飞
回复 支持 反对

使用道具 举报

15

主题

2万

回帖

122

积分

注册会员

Rank: 2

积分
122
发表于 2023-8-20 12:13:29 | 显示全部楼层
还可以不错
回复 支持 反对

使用道具 举报

0

主题

2万

回帖

0

积分

中级会员

Rank: 3Rank: 3

积分
0
发表于 2023-8-29 20:34:40 | 显示全部楼层
灌灌灌灌水
回复 支持 反对

使用道具 举报

2

主题

2万

回帖

69

积分

注册会员

Rank: 2

积分
69
发表于 2023-10-15 06:39:10 | 显示全部楼层
好东西一定要看看!
回复 支持 反对

使用道具 举报

高级模式
B Color Image Link Quote Code Smilies

本版积分规则

手机版|小黑屋|网站地图|源码论坛 ( 海外版 )

GMT+8, 2025-2-9 02:56 , Processed in 0.176229 second(s), 26 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表