約瑟夫環問題解決採用閉包函式實現
摘要：
約瑟夫環問題採用最優演算法實現，主要採用php的閉包函式（用於回撥且沒有函式名的函式），結合php自帶的陣列函式 array_keys 獲取陣列鍵值函式、
array_values 獲取陣列元素值函式、其中最重要的陣列函式array_splice()陣列定向指定位置移除函式。
約瑟夫...
約瑟夫環問題採用最優演算法實現，主要採用php的閉包函式（用於回撥且沒有函式名的函式），結合php自帶的陣列函式 array_keys 獲取陣列鍵值函式、
array_values 獲取陣列元素值函式、其中最重要的陣列函式array_splice()陣列定向指定位置移除函式。
約瑟夫環問簡述：一 群猴子排成一圈，按1，2，…，n依次編號。然後從第1只開始數，數到第m只,把它踢出圈，從它後面再開始數，再數到第m只，在把它踢出去…，如此不停的 進行下去，直到最後只剩下一隻猴子為止，那隻猴子就叫做大王。要求程式設計模擬此過程，輸入m、n, 輸出最後那個大王的編號。
function monkey($n,$m){
$arr=range(1,$n);
$fn=function ($m,&$arr)use(&$fn){
if(count($arr)==1){
return true;
}
$arrKey=array_keys($arr);
if(count($arr)>=$m){
//$arrKey=array_keys($arr);
$key=$arrKey[$m-1];
unset($arr[$key]);
$arr=array_merge(array_splice($arr,$m-1),array_splice($arr,0,$m-1));
}else{
$fla=$m%count($arr);
$key=$arrKey[$fla-1];
unset($arr[$key]);
}
$fn($m,$arr);
};
$fn($m,$arr);
$value=array_values($arr);
echo $value['0'];
}
monkey(5,3);
時間複雜度分析：
，對於時間複雜度，要通過邏輯思考，回撥函式要執行(n-m)次合併陣列，回撥函式要執行($m)次取模，表示式為：(n-m)+m大O表達為：O(n);