PHP实现的基于单向链表解决约瑟夫环问题示例

yipeiwu_com5年前PHP代码库

本文实例讲述了PHP实现的基于单向链表解决约瑟夫环问题。分享给大家供大家参考,具体如下:

约瑟夫环问题:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

更多的类似问题是:n个人围成圈,依次编号为1,2,..,n,现在从1号开始依次报数,当报到m时,报m的人退出,下一个人重新从1报起,循环下去,问最后剩下那个人的编号是多少?

代码实现:

<?php
class Node{
  public $value;   // 节点值
  public $nextNode;  // 下一个节点
}
function create($node, $value){
  $node->value = $value;
}
function addNode($node, $value){
  $lastNode = findLastNode($node);
  $nextNode = new Node();
  $nextNode->value = $value;
  $lastNode->nextNode = $nextNode;
}
/* 找到最后的节点 */
function findLastNode($node){
  if(empty($node->nextNode)){
    return $node;
  }else{
    return findLastNode($node->nextNode);
  }
}
/* 删除节点 必须head为引用传值 */
function deleteNode(&$head, $node, $m, $k = 1){
  if($k + 1 == $m){
    if($node->nextNode == $head){
      $node->nextNode = $node->nextNode->nextNode;
      $head = $node->nextNode;
      return $node->nextNode;
    }else{
      $node->nextNode = $node->nextNode->nextNode;
      return $node->nextNode;
    }
  }else{
    return deleteNode($head, $node->nextNode, $m, ++$k);
  }
}
/* 节点数 */
function countNode($head, $node, $count = 1){
  if($node->nextNode == $head){
    return $count;
  }else{
    return countNode($head, $node->nextNode, ++$count);
  }
}
function printNode($head, $node){
  echo $node->value . ' ';
  if($node->nextNode == $head) return;
  printNode($head, $node->nextNode);
}
function show($data){
  echo '<pre>';
  print_r($data);
  echo '</pre>';
}
$head = new Node();
create($head, 1);
addNode($head, 2);
addNode($head, 3);
addNode($head, 4);
addNode($head, 5);
addNode($head, 6);
addNode($head, 7);
addNode($head, 8);
addNode($head, 9);
addNode($head, 10);
addNode($head, 11);
addNode($head, 12);
$lastNode = findLastNode($head);
$lastNode->nextNode = $head;
$count = countNode($head, $head);
$tmpHead = $head;
while ($count > 2) {
  $tmpHead = deleteNode($head, $tmpHead, 3, 1);
  $count = countNode($head, $head);
}
printNode($head, $head);

更多关于PHP相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《PHP基本语法入门教程》、《php面向对象程序设计入门教程》、《php字符串(string)用法总结》及《php程序设计算法总结

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

相关文章

解决php-fpm.service not found问题的办法

前言 本文给大家详细介绍了解决php-fpm.service not found问题的相关内容,文中介绍的非常详细,下面来一起看看详细的介绍: 环境介绍 环境:ubuntu 16.04...

解析php中如何调用用户自定义函数

先放上来别人的例子吧:call_user_func函数类似于一种特别的调用函数的方法,使用方法如下:    复制代码 代码如下:function a($b,...

PHP获取数组表示的路径方法分析【数组转字符串】 原创

本文实例讲述了PHP获取数组表示的路径方法。分享给大家供大家参考,具体如下: 问题: 文件解析过程中发现一段路径用数组的形式存储,现需要将完整路径以字符串形式输出 解决方法: $ho...

由php if 想到的些问题

复制代码 代码如下:<?php  /* PHP code */  header("Content-type: text/...

腾讯CMEM的PHP扩展编译安装方法

本文实例讲述了腾讯CMEM的PHP扩展编译安装方法。分享给大家供大家参考。具体如下: CMEM是什么? CMEM全称为Cloud Memory,是腾讯提供的高性能内存级持久化存储服务,适...