遞推關係

Question

的josephus problem可以通過下文遞歸solved：

josephus(n, k) = (josephus(n - 1, k) + k-1) % n + 1 
josephus(1, k) = 1 

這怎麼遞推關係已經得到的？

Answer 1

這一段是從維基百科足夠..

當索引從一個開始，則在從第一 的Person移位的人是在位置（（S-1）\ BMOD N）+ 1，其中n是總人數 。設f（n，k）表示倖存者的位置。 第k個人死亡後，我們剩下一個n-1的圓圈，並且 我們從原始 問題的編號爲（k \ bmod n）+1的人開始下一個計數。如果我們從1開始計數，那麼倖存者在 剩餘圓中的位置將是f（n-1，k） 換檔此考慮的事實，我們開始在（K \ BMOD N）+1產生復發

f(n,k)=((f(n-1,k)+k-1) \bmod n)+1,\text{ with }f(1,k)=1\,,

Answer 2

約瑟夫（N，K）=（約瑟夫（N - 1 ，k）+ k-1）％n + 1 ......（1）

用簡單的話說 - 以公式中的「+1」開始。這意味着1次迭代已經完成。現在，我們將剩下n-1個人/元素。我們需要以k的間隔遞歸地處理n-1個元素。但是，現在，由於要刪除的最後一個元素位於第k個位置，因此我們將繼續。因此，增加了k-1。此外，這種添加可能會擾亂數組的索引。因此％n完成了保持數組索引在界限內。 希望它清晰明瞭:)。