1.4 如何利用約瑟夫環來保護你與你的朋友

難度系數：★★★★☆

被考查系數：★★★★☆

題目描述：

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

然而Josephus和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。

約瑟夫問題可用代數分析來求解，假設現在你與m個朋友不幸參與了這個游戲，你要如何保護你與你的朋友？

分析與解答：

實際上只要畫兩個圓圈就可以讓自己與朋友免于死亡游戲，這兩個圓圈中內圈是排列順序，而外圈是自殺順序，如下圖所示。

使用程序來求解的話，只要將陣列當作環狀來處理，在陣列中由計數1開始，每三個數得到一個計數，直到計數到41為止；然后將陣列由索引1開始列出，就可以得知每個位置的自殺順序，這就是約瑟夫排列。41個人報數的約瑟夫排列如下所示（第一個開始對應每個人的站位）：

14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23

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

實現代碼如下：

程序的運行結果為