Ausführliche Erklärung des PHP-Beispiels zum Problem mit verlorenen Taschentüchern

Problembeschreibung: Es gibt n Personen in einem Kreis, und dann, beginnend mit einer willkürlich bestimmten Person, mit m Personen als Einheit, dreht sich jede m Person um und die m-te Person wird getötet. Bitten Sie um jemanden, der am Ende nicht getötet wird.

Verbleibende Probleme:

Verwenden Sie PHP für die einfache Implementierung. PHP hat eine Tiefenbeschränkung von 100 Malen für die Rekursion, daher ist hier keine Rekursion erforderlich. Verwenden Sie Schleifen PHP-Arrays haben viele Funktionen, daher ist die Verwendung einer sequentiellen Tabelle (Array) komplizierter, sodass die Effizienz relativ gering ist und nur weniger als 10.000 Daten verarbeitet werden können. Das Durchlaufen der verknüpften Liste ist komplizierter und führt auch zu einer geringen Effizienz. Die Kombination der Sequenzliste und der verknüpften Liste erfolgt später.

Simulationsimplementierung:

1. class Dhc  
   {  
       private function dropHandkerchief($start=0,$distance,$menArray)  
       {  
           $count = count($menArray);    
           $pos = $distance - 1;    
           $start = $start > ($count-1) ? 0 : $start;//开始位置大于总人数则默认从第一个开始    
           $pos = $start + $pos;//第一个要被出列的人的位置，pos为下标，所以要 -1；    
           while($count > 1)    
           {    
               if($pos < $count)//判断要出列的人的位置是否超出数组大小，超出则减去(或取模)数组大小，从头开始    
               {    
                   echo "第". $menArray[$pos] ."人出列<br />";    
                   array_splice($menArray,$pos,1);//删除要出列的人    
                   $count  = count($menArray);//重新计算大小    
                   $pos += $distance - 1;//下一个要出列的人的位置，pos 为要数的第一个人，所以第 n 个人的下标为 pos + n -1    
               }else    
               {    
                   //$pos -= $count;    
                   $pos = $pos % $count;    
               }  
           }    
           echo &#39;<br />&#39;;    
           echo "第" .$menArray[0]. "人被留下";    
       }    
     
       public function drop()  
       {  
           $menArray = array();//    
           $total = 100;//总人数    
           $distance = 50;//间隔人数    
           $start = 3;//从第几个人开始    
           $i = 0;    
           while($i < $total)//初始化    
           {    
               $menArray[$i] = $i + 1;    
               $i++;    
           }    
           $this->dropHandkerchief($start, $distance, $menArray);    
       }  
   }

Mathematische Ableitungsimplementierung: (20170914)

Ändern Sie einfach die Beschreibung des Problems : Es gibt n Personen und die Zahl ist 0 - n-1. Wenn Sie bis m zählen, zählt m weiter, bis nur noch die letzte Person übrig ist Nummer dieser Person.

Beginnen Sie jedes Mal von vorne, wenn jemand stirbt, was einer Reduzierung des Problemmaßstabs entspricht, d. h. dem Lösen von n Lösungsskalen: n, n-1, n-2, n-3 ... 3 , 2 , 1.

Wenn die Zahl der Person, die in der zweiten Runde gestorben ist (Skala von n-1 Personen), x ist (diese Zahl wird nach dem Tod der ersten Person von 0 neu geordnet), kann daraus abgeleitet werden Die Nummer dieser Person in der ersten Runde (wenn die Anzahl der Personen n ist) beträgt: (x + m)%n. Die Anzahl der Personen, die in (n-1) in

(n-2) gestorben sind, beträgt: (x + m)%(n-1)

(n-3) Die Die Nummer der Person, die in (n-1) gestorben ist, ist: (x + m)%(n-2)

(1) Die Nummer der Person, die in (2) gestorben ist, ist: (x + m )%2, zu diesem Zeitpunkt x = 0;

Kehren Sie den obigen Vorgang um. Es ist bekannt, dass x = 0 ist Maßstab ist 2: (x + m) % 2 = x2

Finden Sie den Wert von x3, wenn der Maßstab 3 ist: (x2 + m) % 3 = x3

Finden Sie den Wert von x wenn die Skala n ist.

1. $n = 100;  
   $m = 3;  
   $s = 0;  
     
   $x = 0;  
   for ($i=2; $i<=$n; $i++) {  
       $x = ($x + $m) % $i;  
   }  
   echo ($x + $s) % $n;  
   // $s=0,表示从第 0 个开始数，如果不是从 0 开始，则只需要向后推 $s 个即可

Das obige ist der detaillierte Inhalt vonAusführliche Erklärung des PHP-Beispiels zum Problem mit verlorenen Taschentüchern. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!