PHP丟手帕問題實例詳解

問題描述：有n個人圍成一圈，然後從任意指定的一個 人那裡為起點，以m個人為單位，每轉m個人第m個人被殺死。求最後不會被殺死的人。

遺留問題：

在此用php做簡單的實現，php中對遞歸有100次的深度限制，所以在此不用遞歸，用循環；php中處理陣列的函數比較多，所以採用順序表（陣列），順序表刪除元素比較複雜，所以效率比較低，只能處理10000一下的資料。鍊錶中的遍歷比較複雜，同樣會導致效率低下，以後再做順序表與鍊錶的結合。

模擬實作：

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

數學推導實作：（20170914）

簡單改變問題的描述：有n個人，編號是0 - n-1，從0 開始數，數到m 則m 死，下一個人繼續從0 開始數，直到只剩最後一個人，求這個人最開始的編號。

每死一個人就重新開始，相當於減小了問題的規模，就是要解n 個規模的解：n, n-1, n-2, n-3 …… 3, 2 , 1。

假如在第二輪(n-1個人的規模)中死的那個人編號是x（這個編號是第一個人死後，重新從0 開始編排的），則可以推導出這個人在第一輪（人數為n 時）的編號是：(x + m)%n。

(n-2)中死的人在(n-1)中的編號是：(x + m)%(n-1)

(n-3)中死的人在(n-1)的編號是：(x + m)%(n-2)

( 1 )中死的人在( 2 )中的編號是：(x + m )%2， 此時x = 0;

把上面的過程倒過來，已知規模為1 時，x = 0；

求規模為2 時，x2 的值： (x + m) % 2 = x2

求規模為3 時，x3 的值：(x2 + m) % 3 = x3

#求規模為n 時x 的值。

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

以上是PHP丟手帕問題實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！