本系列博客習(xí)題來自《算法(第四版)》，算是本人的讀書筆記执赡，如果有人在讀這本書的镰踏，歡迎大家多多交流。為了方便討論沙合，本人新建了一個(gè)微信群(算法交流)奠伪，想要加入的，請(qǐng)?zhí)砑游业奈⑿盘?hào)：zhujinhui207407 謝謝首懈。另外绊率，本人的個(gè)人博客 http://www.kyson.cn 也在不停的更新中，歡迎一起討論
知識(shí)點(diǎn)
- 約瑟夫問題
題目
1.3.37 Josephus 問題究履。在這個(gè)古老的問題中滤否，N 個(gè)身陷絕境的人一致同意通過以下方式減少生存人數(shù)。他們圍坐成一圈（位置記作 0 到 N-1）并從第一個(gè)人開始報(bào)數(shù)最仑，報(bào)到 M 的人會(huì)被殺死藐俺，直到最后一個(gè)人留下來炊甲。傳說中 Josephus 找到了不會(huì)被殺死的位置。編寫一個(gè) Queue 的用例 Josephus欲芹，從命令行接受 N 和 M 并打印出人們被殺死的順序（這也將顯示 Josephus 在圈中的位置）蜜葱。
1.3.37 Josephus problem. In the Josephus problem from antiquity, N people are in dire straits and agree to the following strategy to reduce the population. They arrange them- selves in a circle (at positions numbered from 0 to N–1) and proceed around the circle, eliminating every Mth person until only one person is left. Legend has it that Josephus figured out where to sit to avoid being eliminated. Write a Queue client Josephus that takes N and M from the command line and prints out the order in which people are eliminated (and thus would show Josephus where to sit in the circle).
% java Josephus 7 2
1 3 5 0 4 2 6
分析
本人所有簡(jiǎn)書的算法文章詳細(xì)分析已經(jīng)移入小專欄：算法四習(xí)題詳解，歡迎大家訂閱
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
答案
public class Josephus {
public static void main(String[] args) {
int m = 3;
int N = 41;
Queue<Integer> queue = new Queue<Integer>();
for (int i = 0; i < N; i++)
queue.enqueue(i);
while (!queue.isEmpty()) {
for (int i = 0; i < m - 1; i++)
queue.enqueue(queue.dequeue());
StdOut.print(queue.dequeue() + " ");
}
StdOut.println();
}
}
打印的結(jié)果為:
2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 30
因此耀石，第31個(gè)人是最后一個(gè)被殺死的牵囤，第16個(gè)人是倒數(shù)第二個(gè)被殺死的
代碼索引
視頻講解
廣告
我的首款個(gè)人開發(fā)的APP壁紙寶貝上線了，歡迎大家下載滞伟。
