約瑟夫及相似問題的解法
關乎約瑟夫問題的理解與解法
約瑟夫問題的變形以及相關問題
約瑟夫問題介紹
- 約瑟夫問題的產生是據說著名猶太曆史學家josephus有過以下的故事:羅馬人佔領僑塔帕特後,39個 猶太人與josephus和他的朋友躲到一個洞中,39個猶太人決定先後自殺從而不用被敵人抓到,決定了一個自殺方法,所有人圍成一個圈,由第一個人開始報數,每報數到第三個該人就必須自殺,隨後從此人後面一位重新開始報數,josephus和他的朋友並不像遵從,於是josephus和他的朋友先假裝遵從,隨後站在了第16個和31的位置上,免去了性命之憂。這就是著名的約瑟夫問題。
-
現如今很多關於這種背景的思維題,比如報數出列,出列後從下一位繼續報數,直到剩餘兩位成為誘餌,其他人為獵手等的軍事遊戲,還是猴子爭王的背景題...在這些題目的背後都是這樣一種執行規則:
約瑟夫問題的解決
- 首先這種問題的背景都是,由總數為N的單位圍成一個圈,以q為一個小單位不斷迴圈,第q個除去,隨後繼續迴圈,直到最後剩餘(q-1)個單位停止。
- 首先以最原始的約瑟夫問題來看:(41個人輪番自殺)
-
首次41個人按0-40的編號排成一個圓圈,此時的話第41個加一應該注意跳轉成0。如下圖:
- 首先定義一個長度為41的陣列,隨後定義一個計數變數來統計剩餘的人數,初始化為41個人,隨後用step來表示報數,定義一個編號index。然後就可以用同種的迴圈語句來實現了。主要就是當''' i++ = 40;'''就應該讓其回到第一個位置0上去。從而達到轉圈的目的。每次去除一個人之後計數變數自減1。迴圈結束後遍歷陣列找出存活的人的編號。
- 所以根據 這種方法,對於相關性的問題,index 為下標,q為迴圈單位的N個元素,count為剩餘元素應該是'''index = (index+1)%count'''。