1.需求---- 經(jīng)典約瑟夫問題

首先究反，我們需要知道什么是約瑟夫問題寻定？即設有n個人圍成一圈，現(xiàn)從第m個人開始報數(shù)精耐，數(shù)到第m1人淘汰或者退出狼速，然后從出列的下一個m+1個人重新報數(shù)，數(shù)到m的人出列..........如此循環(huán)卦停，直到所有的人全部出列（延伸直到剩下一個玩家時游戲結(jié)束）向胡，約瑟夫的問題是：對于任意給定的n,m,k求出按次序得到的出列人序列恼蓬。

? 后續(xù)根據(jù)這個問題進行了拓展，如確定m為1僵芹，即從第1個人開始報數(shù)处硬，直到剩下一個時游戲結(jié)束，這個玩家就是游戲獲勝者拇派。在n,k知道的情況下求最后留下的是原來第幾號的那位荷辕。

需求： 萬變不離其宗，后續(xù)的變體其實都是在n,m,k基礎上進行控制變量的件豌，因此我們可以寫一個代碼疮方，覆蓋這三個變量求解約瑟夫問題，針對m變量是1的情況下也可以覆蓋茧彤。

2.解題思路分析

為了簡化出列的過程： m=1

首先我們把這n個人的序號編號從0~n-1（理由很簡單骡显，由于m是可能大于n的，而當m大于等于n時曾掂，那么第一個出列的人編號是m%n蟆盐，而m%n是可能等于0的，這樣編號的話能夠簡化后續(xù)出列的過程）遭殉，當數(shù)到m-1的那個人出列石挂，因此我們編號完成之后，開始分析出列的過程：

第一次出列：

一開始的時候险污，所有人的編號排成序列的模式即為：

0,1,2,3,4,5...n-2痹愚，n-1

那么第一次出列的人的編號則是(m-1)%n1，那么在第一個人出列之后蛔糯，從他的下一個人又開始從0開始報數(shù)拯腮，為了方便我們設k1 = m%n1（n1為當前序列的總?cè)藬?shù)）那么在第一個人出列之后，k1則是下一次新的編號序列的首位元素蚁飒，那么我們得到的新的編號序列為：

k1动壤，k1+1，k1+2淮逻，k1+3...n-2琼懊，n-1，0爬早，1哼丈，2...k1-3，k1-2 (k1-1第一次已出列)

那么在這個新的序列中筛严，第一個人依舊是從0開始報數(shù)醉旦，那么在這個新的序列中，每個人報的相應數(shù)字為：

0,1，2,3....n-2

那么第二次每個人報的相應數(shù)字與第一次時自己相應的編號對應起來的關系則為：

0 --> k1

1 --> k1+1

2 --> k1+2

...

n-2 ---> (k1+n-2)%n1(n1為當前序列的總?cè)藬?shù)车胡，因為是循環(huán)的序列檬输，k1+n-1可能大于總?cè)藬?shù))

那么這時我們要解決的問題就是n-1個人的報數(shù)問題（即n-1階約瑟夫環(huán)的問題）

可能以上過程你還是覺得不太清晰，那么我們重復以上過程匈棘，繼續(xù)推導剩余的n-1個人的約瑟夫環(huán)的問題：

那么在這剩下的n-1個人中丧慈，我們也可以為了方便，將這n-1個人編號為：

0,1,2,3,4...n-2

那么此時出列的人的編號則是（m-1） % n2（n2為當前序列的總?cè)藬?shù)）羹饰，同樣的我們設k2 = m % n2伊滋，那么在這個人出列了以后，序列重排队秩，重排后新的編號序列為：

k2笑旺，k2+1，k2+2馍资，k2+3...n-2筒主，n-1，0鸟蟹，1乌妙，2...k2-3，k2-2 (k2-1第一次已出列)

那么在這個新的序列中建钥，第一個人依舊是從1開始報數(shù)藤韵，那么在這個新的序列中，每個人報的相應數(shù)字為：

1,2熊经，3,4....n-2

那么這樣的話是不是又把問題轉(zhuǎn)化成了n-2階約瑟夫環(huán)的問題呢泽艘？

后面的過程與前兩次的過程一模一樣，那么遞歸處理下去镐依，直到最后只剩下一個人的時候匹涮，便可以直接得出結(jié)果

當我們得到一個人的時候（即一階約瑟夫環(huán)問題）的結(jié)果，那么我們是否能通過一階約瑟夫環(huán)問題的結(jié)果槐壳，推導出二階約瑟夫環(huán)的結(jié)果呢然低？

借助上面的分析過程，我們知道务唐，當在解決n階約瑟夫環(huán)問題時雳攘，序號為k1的人出列后，剩下的n-1個人又重新組成了一個n-1階的約瑟夫環(huán)绍哎，那么

假如得到了這個n-1階約瑟夫環(huán)問題的結(jié)果為ans（即最后一個出列的人編號為ans）来农，那么我們通過上述分析過程，可以知道崇堰，n階約瑟夫環(huán)的結(jié)果

(ans + k)%n(n為當前序列的總?cè)藬?shù))，而k = m%n

則有：

n階約瑟夫環(huán)的結(jié)果

(ans + m % n)%n，那么我們還可以將該式進行一下簡單的化簡：

當m<n時海诲，易得上式可化簡為：（ans + m）% n

而當m>=n時繁莹，那么上式則化簡為：（ans % n + m%n%n）% n

即為：（ans % n + m%n）% n

而 （ans + m）% n = （ans % n + m%n）% n

因此得證

(ans + m % n)%n = （ans + m）% n

這樣的話，我們就得到了遞推公式特幔，由于編號是從0開始的咨演，那么我們可以令

f[1] = 0； //當一個人的時候蚯斯，出隊人員編號為0

f[n] = (f[n-1] + m)%n //m表示每次數(shù)到該數(shù)的人出列薄风，n表示當前序列的總?cè)藬?shù)

而我們只需要得到第n次出列的結(jié)果即可，那么不需要另外聲明數(shù)組保存數(shù)據(jù)拍嵌，只需要直接一個for循環(huán)求得n階約瑟夫環(huán)問題的結(jié)果即可

由于往往現(xiàn)實生活中編號是從1-n遭赂，那么我們把最后的結(jié)果加1即可。

---------------------

(原文：https://blog.csdn.net/jiangjiang_jian/article/details/81744435)

3.代碼邏輯

定義函數(shù)
1）首先考慮特殊情況横辆，即k=1的時候撇他，就相當于是順序一個接一個淘汰，那么最后存活的是編號為n的人

2）設n個人狈蚤，通過輸入?yún)?shù)n困肩，生成一個長度為n的列表（注意這里的n不能為1，一直都是這個1脆侮，它也就是最后一個）锌畸，這里使用range函數(shù)生成序列，注意range函數(shù)的后半括號是包括的靖避，即如range（5）是從0,1,2,3,4.所以需要設為range（1潭枣，n+1）

3) 在上一步知道，該問題轉(zhuǎn)換為n-1階約瑟夫環(huán)的問題筋蓖，要數(shù)到k的就把那個位置刪除卸耘，其中第一次出列的號碼是n+k-1/當前序列長度，通過n-1次循環(huán)迭代粘咖，下一次的出列號碼是上一次出列號碼+k-1/當前刪去出列的新序列蚣抗，直到剩下的人數(shù)為1，才退出循環(huán)

4,）設置主函數(shù)瓮下，輸入n,m,k.運行循環(huán)即可

4.實驗結(jié)果展示