自殺逃生算法！C語言算法之約瑟夫環問題

2018-08-25 15:51:31 C語言源代碼計劃

約瑟夫問題

更多C/C++學習資料，請私信我“代碼”，即可獲取

據說著名猶太曆史學家 Josephus有過以下的故事：在羅馬人佔領喬塔帕特後，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧願死也不要被敵人到，於是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然後再由下一個重新報數，直到所有人都自殺身亡為止。

然而Josephus 和他的朋友並不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，於是逃過了這場死亡遊戲。解法約瑟夫問題可用代數分析來求解，將這個問題擴大好了，假設現在您與m個朋友不幸參

與了這個遊戲，您要如何保護您與您的朋友？只要畫兩個圓圈就可以讓自己與朋友免於死亡遊戲，這兩個圓圈內圈是排列順序，而外圈是自殺順序，如下圖所示：

更多C/C++學習資料，請私信我“代碼”，即可獲取

使用程式來求解的話，只要將陣列當作環狀來處理就可以了，在陣列中由計數1開始，每找到三個無資料區就填入一個計數，直而計數達41為止，然後將陣列由索引1開始列出，就可以得知每個位置的自殺順序，這就是約瑟夫排列，41個人而報數3的約琴夫排列如下所示： 14 14 14 36 36 361 1 1 38 38 38 15 15 15 2 2 2 24 24 2430 30 30 3 3 3 16 16 1634 34 34 4 4 4 25 25 25 17 17 175 5 5 40 40 40 31 31 31 6 6 6 18 18 1826 26 26 7 7 7 37 37 3719 19 19 8 8 8 35 35 35 27 27 279 9 9 20 20 20 32 32 32 10 10 1041 41 41 21 21 21 11 11 1128 28 28 39 39 39 12 12 12 22 22 2233 33 3313 13 1329 29 2923 23 23

由上可知，最後一個自殺的是在第31個位置，而倒數第二個自殺的要排在第16個位置，之前的人都死光了，所以他們也就不知道約琴夫與他的朋友並沒有遵守遊戲規則了。