介紹
約瑟夫問題(Josephus Problem)是一個古老的數學問題,其名稱源自於猶太歷史學家弗拉維奧·約瑟夫斯(Flavius Josephus)。這個問題描述了一個關於生存和順序的遊戲。
問題的背景是這樣的:
假設有N個人(編號從1到N)站成一個圓圈狀。一開始,從第一個人開始按照順時針方向報數,報到第M個人就將其移出圈子,然後再從下一個人開始重新報數,如此重複,直到只剩下一個人為止。
問題的目標
目標是找到最後生存下來的那個人的編號**。
即,如果 N = 7,M = 3,那麼經過一輪報數和移除操作後,順序會變成3,6,2,7,5,1,最後剩下的是4號。
約瑟夫問題並不僅限於具體的數字,而是一個普遍的抽象問題,可以用數學方式來解決。
解決這個問題的一種經典方法是使用遞迴(recursion)。
基於遞迴的解法如下:
- 如果只有一個人(N=1),那麼他就是最後的生存者,回傳他的編號。
- 否則,從第一個人開始報數,並將每個第M個人移除。
- 移除完畢後,從下一個人開始重新遞迴調用這個過程(N-1個人)。
- 將遞迴返回的結果(即下一輪的最後生存者編號)調整到當前的編號對應的位置,然後回傳結果。
這樣,通過不斷遞迴和移除操作,最後得到的結果就是約瑟夫問題的解。
需要注意的是,
約瑟夫問題的解並不唯一,它取決於初始的 N 和 M 的值。
這個問題在數學和計算機科學中都有廣泛的應用,包括編程、遊戲理論等領域。
李永樂老師的講解
紀錄
先介紹了當k=2時的基本情況,然後討論了更一般的情況。
影片提供了遞推式來解決這個問題,將最後剩下的人表示為f(N, k),其中N表示最初的人數,k表示每隔多少人殺一個。
他們的編號不同,例如原先的 4 號現在成了 1 號,原先的 5 號現在成了 2 號,原先的 6 號現在成了 3 號。
這意味著他們的編號相差3。
這個差值3正好對應到每隔幾人殺一個的k值。
因此,我們需要將這個差值加上k,這樣新的編號就會與原先的編號相同了。
影片解釋了遞推式的計算過程,並提到如果計算結果大於N,則需要減去N,相當於去取餘數。
最後給予一個範例呈現。
N = 8,總共 8 個人。
K = 3,每隔 3 個人殺一個。
最後生存者是 7 號。
流程圖
若想要清楚流程圖,大力推薦參考資料【Josephus Problem - GeeksforGeeks】
當 N = 5, K = 1 時候的流程圖。最後生存者是 3 號。
實作
// return the position of last man survives
function Josephus(n, k) {
let i = 1;
let ans = 0;
while (i <= n) {
// update the value of ans
ans = (ans + k) % i;
// 再進行下一個 i
i++;
}
// 編號從 1 開始
return ans + 1;
}
// This code is contributed by sarveshc111.
let n = 1; // 總人數
let k = 1; // 每次報數的數字
let lastSurvivor = Josephus(n, k);
console.log("最後生存者的編號是:", lastSurvivor);
最後,如果你覺得我的分享對你有幫助,請給予我一個愛心,並且分享這篇文章,這將是對我最大的鼓勵!