快捷導(dǎo)航

PHP實(shí)現(xiàn)的基于單向鏈表解決約瑟夫環(huán)問題示例

更新時(shí)間：2017年09月30日 16:50:22 作者：CyborgLin

這篇文章主要介紹了PHP實(shí)現(xiàn)的基于單向鏈表解決約瑟夫環(huán)問題,結(jié)合具體實(shí)例形式分析了php使用單鏈表解決約瑟夫環(huán)問題的算法原理與相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了PHP實(shí)現(xiàn)的基于單向鏈表解決約瑟夫環(huán)問題。分享給大家供大家參考，具體如下：

約瑟夫環(huán)問題：在羅馬人占領(lǐng)喬塔帕特后，39 個(gè)猶太人與Josephus及他的朋友躲到一個(gè)洞中，39個(gè)猶太人決定寧愿死也不要被敵人抓到，于是決定了一個(gè)自殺方式，41個(gè)人排成一個(gè)圓圈，由第1個(gè)人開始報(bào)數(shù)，每報(bào)數(shù)到第3人該人就必須自殺，然后再由下一個(gè)重新報(bào)數(shù)，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個(gè)人開始，越過k-2個(gè)人（因?yàn)榈谝粋€(gè)人已經(jīng)被越過），并殺掉第k個(gè)人。接著，再越過k-1個(gè)人，并殺掉第k個(gè)人。這個(gè)過程沿著圓圈一直進(jìn)行，直到最終只剩下一個(gè)人留下，這個(gè)人就可以繼續(xù)活著。問題是，給定了和，一開始要站在什么地方才能避免被處決？Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個(gè)與第31個(gè)位置，于是逃過了這場(chǎng)死亡游戲。

更多的類似問題是：n個(gè)人圍成圈，依次編號(hào)為1,2,..,n，現(xiàn)在從1號(hào)開始依次報(bào)數(shù)，當(dāng)報(bào)到m時(shí)，報(bào)m的人退出，下一個(gè)人重新從1報(bào)起，循環(huán)下去，問最后剩下那個(gè)人的編號(hào)是多少？

代碼實(shí)現(xiàn)：

<?php
class Node{
  public $value;   // 節(jié)點(diǎn)值
  public $nextNode;  // 下一個(gè)節(jié)點(diǎn)
}
function create($node, $value){
  $node->value = $value;
}
function addNode($node, $value){
  $lastNode = findLastNode($node);
  $nextNode = new Node();
  $nextNode->value = $value;
  $lastNode->nextNode = $nextNode;
}
/* 找到最后的節(jié)點(diǎn) */
function findLastNode($node){
  if(empty($node->nextNode)){
    return $node;
  }else{
    return findLastNode($node->nextNode);
  }
}
/* 刪除節(jié)點(diǎn) 必須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);
  }
}
/* 節(jié)點(diǎn)數(shù) */
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);

更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《PHP基本語法入門教程》、《php面向?qū)ο蟪绦蛟O(shè)計(jì)入門教程》、《php字符串(string)用法總結(jié)》及《php程序設(shè)計(jì)算法總結(jié)》

希望本文所述對(duì)大家PHP程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: