猿の群れの中で王になる方法を教えてあげましょうか.

2021 ワード

今日クラスメートQとチャットしているとき、突然質問がありました.
問題はこうです.
サルの群れがぐるぐる並んで、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]);
		}
	}
}
?>