Introduction à la méthode PHP de résolution du problème de l'anneau de Joseph basée sur des listes chaînées unidirectionnelles

Cet article présente principalement l'implémentation par PHP de la résolution du problème de Joseph Ring basée sur des listes à chaînage unique. Il analyse les principes de l'algorithme et les techniques de fonctionnement associées de PHP à l'aide de listes à chaînage unique pour résoudre le problème de Joseph Ring sur la base d'exemples spécifiques. peut s'y référer

L'exemple de cet article décrit comment résoudre le problème de Joseph Ring basé sur une liste chaînée unidirectionnelle implémentée en PHP. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Problème de l'anneau de Joseph : Après la capture de Chotapat par les Romains, 39 Juifs se sont cachés dans une grotte avec Josèphe et ses amis, 39 Juifs ont décidé qu'ils préféraient mourir plutôt que d'être attrapés par l'ennemi, ils ont donc opté pour une méthode de suicide. 41 personnes se sont alignées en cercle, en commençant par la première personne à compter, et chaque fois que la troisième personne était comptée, la personne devait s'engager. suicide, puis le suivant compte à nouveau jusqu'à ce que tout le monde se suicide. Cependant, Josèphe et ses amis ne voulaient pas obéir. Commencez d'abord par une personne, croisez k-2 personnes (car la première personne a été croisée) et tuez la k-ième personne. Ensuite, dépassez les k-1 personnes et tuez la k-ème personne. Ce processus se poursuit le long du cercle jusqu'à ce qu'il ne reste finalement qu'une seule personne, et cette personne peut continuer à vivre. La question est, étant donné et, où vous situez-vous initialement pour éviter d'être exécuté ? Josèphe a demandé à son ami de faire semblant d'obéir en premier. Il a placé son ami et lui-même aux 16e et 31e positions, échappant ainsi au jeu de la mort.

Des problèmes plus similaires sont : n personnes forment un cercle, numérotés 1, 2,...,n, maintenant en commençant par le numéro 1, en comptant dans l'ordre, lorsque m est signalé, la personne qui a signalé m sort, la personne suivante recommence à 1 et le cycle continue en se demandant quel est le numéro de la dernière personne restante ?

Mise en œuvre du code :

<?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 . &#39; &#39;;
  if($node->nextNode == $head) return;
  printNode($head, $node->nextNode);
}
function show($data){
  echo &#39;<pre class="brush:php;toolbar:false">&#39;;
  print_r($data);
  echo &#39;

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!