Explication détaillée de l'exemple de problème de mouchoir perdu PHP

Description du problème : il y a n personnes dans un cercle, puis en partant d'une personne arbitrairement désignée, avec m personnes comme unité, chaque m personne se tourne vers la mième personne pour être tuée. Demandez quelqu'un qui ne sera pas tué à la fin.

Problèmes restants :

Utilisez PHP pour une implémentation simple. PHP a une limite de profondeur de 100 fois pour la récursivité, il n'y a donc pas besoin de récursion ici, utilisez des boucles pour le gérer ; PHP Il existe de nombreuses fonctions dans les tableaux, donc des tableaux séquentiels (tableaux) sont utilisés. La suppression d'éléments dans des tableaux séquentiels est plus compliquée, donc l'efficacité est relativement faible et ne peut traiter que moins de 10 000 données. Le parcours dans la liste chaînée est plus compliqué et conduira également à une faible efficacité. La combinaison de la liste de séquences et de la liste chaînée sera effectuée plus tard.

Implémentation de la simulation :

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

   Copier après la connexion

Implémentation de la dérivation mathématique : (20170914)

Changer simplement la description du problème : Il y a n personnes et le nombre est 0 - n-1. Commencez à compter à partir de 0. En comptant jusqu'à m, m mourra la personne suivante continuera à compter de 0 jusqu'à ce qu'il ne reste plus que la dernière personne. numéro de cette personne.

Recommencer à chaque fois que quelqu'un meurt, ce qui équivaut à réduire l'ampleur du problème, c'est-à-dire résoudre n échelles de solutions : n, n-1, n-2, n-3... 3 , 2 , 1.

Si le numéro de la personne décédée au deuxième tour (échelle de n-1 personnes) est x (ce nombre est réarrangé de 0 après le décès de la première personne), on peut en déduire Le numéro de cette personne au premier tour (lorsque le nombre de personnes est n) est : (x + m)%n. Le numéro de la personne décédée en (n-1) en

(n-2) est : (x + m)%(n-1)

(n-3) Le le numéro de la personne décédée en (n-1) est : (x + m)%(n-2)

(1) Le numéro de la personne décédée en (2) est : (x + m )%2, à ce moment x = 0;

Inversez le processus ci-dessus, on sait que lorsque l'échelle est 1, x = 0;

Trouvez la valeur de x2 lorsque le l'échelle est 2 : (x + m) % 2 = x2

Trouver la valeur de x3 lorsque l'échelle est 3 : (x2 + m) % 3 = x3

Trouver la valeur de x lorsque l'échelle est n.

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 个即可

   Copier après la connexion

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!