ジョセフ リング問題のリンク リスト解法と数学的解法 (PHP)

ジョセフの指輪の問題

猿のグループが円形に並び、1、2、...、n と順番に番号が付けられます。次に、1 番目から数え始め、m 番目まで数え、円の外に追い出し、後ろから数え始め、m 番目まで数え、追い出します...このようにして最後まで続けます。猿は一匹だけ残っており、その猿は王様と呼ばれています。このプロセスをシミュレートするには、m、n を入力し、最後の王の番号を出力するプログラミングが必要です。

リンクリスト解法

function king($n,$m){    $monky = range(1,$n);    $i = 0;    while(count($monky)>1){        $i+=1;        $head = array_shift($monky);        if($i%$m!=0){            array_push($monky,$head);        }    }    return $monky[0];}echo king(10,3);

数学的解法

x' = 2 3 4 5 0

x = 0 1 2 3 4

x' = (x+m)%n

function king2($n,$m){    $r = 0;    for($i=2;$i<=$n;$i++){        $r = ($r+$m)%$i;    }    return $r+1;}echo king2(10,3);

著作権声明: この記事はブロガーによるオリジナルの記事であり、ブロガーの許可なく複製することはできません。