phpアルゴリズム要約
5人がりんごをたくさん盗んで、翌日盗品を分けようとした.夜、一人で散歩して、すべての野菜と果物を5つに分けましたが、1つ増えて、ついでにこれを木の上のサルに投げて、自分で1/5を持って隠しました.他の4人もそう思っていたので、最初の人のように5つに分けて多くのものをサルに投げ、1/5を盗んだ.次の日、盗品を分けて、5つに分けてサルに投げました.最後の一人が分けた.りんごはいくつありますか.
サルの群れがぐるぐる並んで、1,2,...,nの順に番号をつけます.そして1匹目から数えて、m匹目まで数えて、それを輪から蹴り出して、その後ろから数えて、m匹目まで数えて、それを蹴り出して...、このようにひっきりなしに進んで、最後にサルが1匹しか残っていないまで、そのサルは大王と呼ばれていました.このプロセスをプログラミングしてシミュレーションし、m、nを入力し、最後の王の番号を出力する必要があります.
ハノータ問題はインドの古い伝説である.天地を切り開いた神ブラマはある寺にダイヤモンドの棒を3本残した.最初の棒には64個の円の金片が覆われていて、最大の1つは下にあり、残りの1つは1つより小さく、順番に積み重ねられ、寺の僧たちは倦まずにこの棒から別の棒に運んで、利用できるようになった.真ん中の棒は助けになりますが、毎回1つしか運べず、大きいのは小さい上に置くことはできません.解答結果は自分で計算を実行してください.プログラムは末尾を参照してください.膨大な数字(円片を移動する回数)18446744073709551615に直面して、僧侶たちは一生の精力を尽くしても金片の移動を完成することはできないようだ.
その後、この伝説はハンノタゲームに変わりました.
1.ロッドA,B,Cが3本あります.Aロッドには皿がいくつかあります
2.皿を1枚動かすたびに、小さいのは大きな上にしか重ねられない
3.全ての皿をAロッドからCロッドに全て移す
研究の結果、ハンノッタの解読は簡単で、移動規則に従って金片を一方向に移動することであることが分かった.
例えば3階ハノータの移動:A→C,A→B,C→B,A→C,B→A,B→C,A→C
また,ハノータ問題もプログラム設計における古典的な再帰問題である.
for ($i = 1; ; $i++)
{
if ($i%5 == 1) {
// , $t
$t = $i - round($i/5) - 1;
if($t % 5 == 1)
{
// , $r
$r = $t - round($t/5) - 1;
if($r % 5 == 1)
{
// , $s
$s = $r - round($r/5) - 1;
if($s % 5 == 1)
{
// , $x
$x = $s - round($s/5) - 1;
if($x % 5 == 1)
{
// , $y
$y = $x - round($x/5) - 1;
if ($y % 5 == 1) {
echo $i;
break;
}
}
}
}
}
}
}
サルの群れがぐるぐる並んで、1,2,...,nの順に番号をつけます.そして1匹目から数えて、m匹目まで数えて、それを輪から蹴り出して、その後ろから数えて、m匹目まで数えて、それを蹴り出して...、このようにひっきりなしに進んで、最後にサルが1匹しか残っていないまで、そのサルは大王と呼ばれていました.このプロセスをプログラミングしてシミュレーションし、m、nを入力し、最後の王の番号を出力する必要があります.
function king($n, $m){
$monkeys = range(1, $n);
$i=0;
$k=$n;
while (count($monkeys)>1) {
if(($i+1)%$m==0) {
unset($monkeys[$i]);
} else {
array_push($monkeys,$monkeys[$i]);
unset($monkeys[$i]);
}
$i++;
}
return current($monkeys);
}
$a = king(5, 2);
var_dump($a);
ハノータ問題はインドの古い伝説である.天地を切り開いた神ブラマはある寺にダイヤモンドの棒を3本残した.最初の棒には64個の円の金片が覆われていて、最大の1つは下にあり、残りの1つは1つより小さく、順番に積み重ねられ、寺の僧たちは倦まずにこの棒から別の棒に運んで、利用できるようになった.真ん中の棒は助けになりますが、毎回1つしか運べず、大きいのは小さい上に置くことはできません.解答結果は自分で計算を実行してください.プログラムは末尾を参照してください.膨大な数字(円片を移動する回数)18446744073709551615に直面して、僧侶たちは一生の精力を尽くしても金片の移動を完成することはできないようだ.
その後、この伝説はハンノタゲームに変わりました.
1.ロッドA,B,Cが3本あります.Aロッドには皿がいくつかあります
2.皿を1枚動かすたびに、小さいのは大きな上にしか重ねられない
3.全ての皿をAロッドからCロッドに全て移す
研究の結果、ハンノッタの解読は簡単で、移動規則に従って金片を一方向に移動することであることが分かった.
例えば3階ハノータの移動:A→C,A→B,C→B,A→C,B→A,B→C,A→C
また,ハノータ問題もプログラム設計における古典的な再帰問題である.
function hanoi($n,$x,$y,$z){
if($n==1){
echo 'move disk 1 from '.$x.' to '.$z."
";
}else{
hanoi($n-1,$x,$z,$y);
echo 'move disk '.$n.' from '.$x.' to '.$z."
";
hanoi($n-1,$y,$x,$z);
}
}
hanoi(3,'A','B','C');