Einführung in die PHP-Methode zur Lösung des Joseph-Ring-Problems basierend auf einseitig verknüpften Listen

Dieser Artikel stellt hauptsächlich die PHP-Implementierung zur Lösung des Joseph-Ring-Problems basierend auf einfach verknüpften Listen vor. Er analysiert die Algorithmusprinzipien und die damit verbundenen Betriebstechniken von PHP, um das Joseph-Ring-Problem anhand spezifischer Beispiele zu lösen kann darauf verweisen

Das Beispiel in diesem Artikel beschreibt, wie das Joseph-Ring-Problem basierend auf einer in PHP implementierten einseitig verknüpften Liste gelöst wird. Teilen Sie es als Referenz mit allen. Die Einzelheiten lauten wie folgt:

Josephus-Ring-Problem: Nachdem die Römer Chotapat erobert hatten, versteckten sich 39 Juden in einer Höhle mit Josephus und seinen Freunden, 39 Juden entschieden, dass sie lieber sterben würden, als vom Feind gefangen zu werden, also entschieden sie sich für eine Selbstmordmethode: 41 Personen stellten sich in einem Kreis auf, beginnend mit der ersten Person, die gezählt wurde, und jedes Mal, wenn die dritte Person gezählt wurde, musste die Person begehen Selbstmord, und dann zählt der nächste erneut, bis alle Selbstmord begehen. Josephus und seine Freunde wollten jedoch nicht nachkommen. Beginnen Sie zunächst mit einer Person, kreuzen Sie k-2 Personen (da die erste Person gekreuzt wurde) und töten Sie die k-te Person. Gehen Sie dann an k-1 Personen vorbei und töten Sie die k-te Person. Dieser Prozess setzt sich im Kreis fort, bis schließlich nur noch eine Person übrig bleibt und diese Person weiterleben kann. Die Frage lautet: Wo stehen Sie überhaupt, um einer Hinrichtung zu entgehen? Josephus bat seinen Freund, zuerst so zu tun, als würde er gehorchen. Er platzierte seinen Freund und sich selbst auf der 16. und 31. Position und entging so dem Todesspiel.

Weitere ähnliche Probleme sind: n Personen bilden einen Kreis, nummeriert mit 1, 2, ..., n, jetzt beginnend mit Nummer 1, nacheinander zählend, wenn m gemeldet wird, verlässt die Person, die m gemeldet hat, den Kreis. Die nächste Person beginnt wieder bei 1 und der Zyklus geht weiter, wobei gefragt wird, welche Nummer die letzte verbleibende Person hat.

Code-Implementierung:

<?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;

'; } $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);

Das obige ist der detaillierte Inhalt vonEinführung in die PHP-Methode zur Lösung des Joseph-Ring-Problems basierend auf einseitig verknüpften Listen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!