个人中心
gpt4 book ai didi

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

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 31 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章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报起，循环下去，问最后剩下那个人的编号是多少?

代码实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
<?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程序设计有所帮助.

原文链接：http://blog.csdn.net/mxdzchallpp/article/details/51777371 。

最后此篇关于PHP实现的基于单向链表解决约瑟夫环问题示例的文章就讲到这里了,如果你想了解更多关于PHP实现的基于单向链表解决约瑟夫环问题示例的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

31 4 0
文章推荐： php判断文件上传图片格式的实例详解
文章推荐： Android动画：Interpolator插值器使用和自定义详解
文章推荐： SQL实现LeetCode(197.上升温度)
文章推荐： 另类玩法！使用 Rest API 操作 RabbitMQ
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com