PHP 손수건 분실 문제 예시에 대한 자세한 설명

문제 설명: n명이 원 안에 있고, 임의로 지정한 사람부터 시작하여 m명을 단위로 하여 m명이 돌아서 m번째 사람이 죽는다. 결국 죽지 않을 사람을 구하십시오.

남은 문제:

여기서는 PHP를 사용하여 재귀에 대한 깊이 제한이 100회이므로 여기서는 재귀할 필요가 없습니다. PHP에는 배열 처리를 위한 많은 기능이 있습니다. 따라서 시퀀스 테이블(배열)을 사용하므로 순차적 목록에서 요소를 삭제하는 것이 더 복잡하므로 효율성이 상대적으로 낮고 10,000개 미만의 데이터만 처리할 수 있습니다. 연결리스트에서의 순회는 더 복잡하고 효율성도 떨어지게 됩니다. 시퀀스 목록과 연결리스트의 조합은 나중에 이루어질 것입니다.

시뮬레이션 구현:

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명 규모)가 다음과 같다면 한 라운드의 사망자 수(사람 수가 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

척도가 2일 때 x3의 값을 찾으세요. scale is 3 (x2 + m) % 3 = x3

scale이 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!