Detailed explanation of PHP lost handkerchief problem example

Problem description: There are n people in a circle, and then starting from an arbitrarily designated person, taking m people as the unit, m people are killed every time the m person is killed. Ask for someone who will not be killed in the end.

Left issues:

Use PHP for simple implementation. PHP has a depth limit of 100 times for recursion, so there is no need for recursion here, use loops; handle it in PHP There are many functions in arrays, so sequential tables (arrays) are used. Deleting elements in sequential tables is more complicated, so the efficiency is relatively low, and it can only process less than 10,000 data. The traversal in the linked list is more complicated and will also lead to low efficiency. The combination of the sequence list and the linked list will be done later.

Simulation implementation:

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

Mathematical derivation implementation: (20170914)

Simply change the description of the problem: there are n Individuals are numbered 0 - n-1. Count from 0. When m is reached, m will die. The next person will continue counting from 0 until there is only the last person left. Find the initial number of this person.

Start over every time someone dies, which is equivalent to reducing the scale of the problem, that is, solving n-scale solutions: n, n-1, n-2, n-3... 3, 2 , 1.

If the number of the person who died in the second round (scale of n-1 people) is x (this number is re-arranged from 0 after the death of the first person), it can be deduced This person's number in the first round (when the number of people is n) is: (x + m)%n.

The number of the person who died in (n-2) is: (x + m)%(n-1)

(n-3) The number of the person who died in (n-1) is: (x + m)%(n-2)

(1) The number of the person who died in (2) is: (x + m )%2, at this time x = 0;

Reverse the above process, it is known that when the scale is 1, x = 0;

Find the value of x2 when the scale is 2: (x + m) % 2 = x2

Find the value of x3 when the scale is 3: (x2 + m) % 3 = x3

Find the value of x when the scale is 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 个即可

The above is the detailed content of Detailed explanation of PHP lost handkerchief problem example. For more information, please follow other related articles on the PHP Chinese website!