猿の群れの中で王になる方法を教えてあげましょうか.
2021 ワード
今日クラスメートQとチャットしているとき、突然質問がありました.
問題はこうです.
サルの群れがぐるぐる並んで、1,2,...,nの順に番号をつけます.そして1匹目から数えて、m匹目まで数えて、それを輪から蹴り出して、その後ろから数えて、m匹目まで数えて、それを蹴り出して...、このようにひっきりなしに進んで、最後にサルが1匹しか残っていないまで、そのサルは大王と呼ばれていました.このプロセスをプログラミングしてシミュレーションし、m、nを入力し、最後の王の番号を出力する必要があります.
設計手順は次のとおりです.
結果は次のとおりです.
つまり、サルの群れ全体で31位(初期は0から)にランクインする必要があるので、このサルの群れの中で王になることを保証することができます.
付録:ネット上の他の人の1つのプログラム
問題はこうです.
サルの群れがぐるぐる並んで、1,2,...,nの順に番号をつけます.そして1匹目から数えて、m匹目まで数えて、それを輪から蹴り出して、その後ろから数えて、m匹目まで数えて、それを蹴り出して...、このようにひっきりなしに進んで、最後にサルが1匹しか残っていないまで、そのサルは大王と呼ばれていました.このプロセスをプログラミングしてシミュレーションし、m、nを入力し、最後の王の番号を出力する必要があります.
設計手順は次のとおりです.
<?php
$g = 40; // : -1
/**
*
*
* @param array
* @param int
* @param int
* @param int
*/
function joseph($arr, $m, $s, $q){
global $g;
//
$n = count($arr);
if ($n == $q) return $arr;
//
/**
* ,
*/
/*
$i=0;
while ($i <= $g) {
if ( ! isset($arr[$i])) {
$i++;
continue;
}
if ($s != $m) {
$s++;
} else {
unset($arr[$i]);
$s = 1;
}
$i++;
}
*/
foreach ($arr as $key => $val) {
if ($s != $m) {
$s++;
} else {
$s = 1;
unset ($arr[$key]);
}
}
return joseph($arr, $m, $s, $q);
}
//
for ($i = 0 ; $i <= $g; $i++) {
$arr[] = $i;
}
var_dump(joseph($arr, 3, 1, 2));
/*End of php*/
結果は次のとおりです.
array 30 => int 30
つまり、サルの群れ全体で31位(初期は0から)にランクインする必要があるので、このサルの群れの中で王になることを保証することができます.
付録:ネット上の他の人の1つのプログラム
<?php
/**
*
*
*/
$data = array('0'=>0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16);
$begin = 1;
echo '<pre>';
while(count($data) != 1) {
echo 'begin:' . $begin;
mark(&$data,&$begin);
echo 'rs:';
var_dump($data);
}
echo 'last numeric:' . $begin . '<br />';
echo 'result:' . $data[array_rand($data)];
function mark($arr,$begin) {
foreach($arr as $key=>$value) {
if($begin++ % 3 == 0 ) {
unset($arr[$key]);
}
}
}
?>