PHPハンカチ紛失問題例を詳しく解説

問題の説明: 円の中に n 人がいて、任意に指定した人から始めて、m 人を単位として、毎ターン、m 人の中の m 人目が殺害されます。最後に殺されない人を求めてください。

残りの問題:

ここで簡単な実装を行うには PHP を使用します。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 。

2周目(n-1人規模)で死亡した人の数が1周目(人数nの場合)で死亡した人の数は(x+m)%nとなります。 (n-1) で

(n-2) で亡くなった人の数は: (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

りー

以上がPHPハンカチ紛失問題例を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。