簡介
問題大意：m個人圍坐成一圈，編號為0~m-1，從0號的人開始報數，他先報0，報到k-1的那個人出局，然后下一個人繼續從0開始報，下一個報到k-1的人又出局……一直重復直到最后環內剩下一個人，求這個人的編號，
首先我們自然是可以用鏈表把這個題模擬出來的，但是這里還有一種稍加推導得到遞推關系，然后遞回的方法，
基礎
假設現在有0~9，十個人，k=4，所以每次從0開始，報到3的人就會出局，現在用一張圖將這個情況完整展現出來，
從上圖可以看到，第一輪報數的時候每個人將要報的數是和自己編號一樣的，每一次移除一個人之后，整個環中的人報的數會發生變化，可以看到4變成了0，5變成了1……以此類推，也就是說環中的人每一輪報的數都會發生變化，我們要求的是最后出局的人（也就是最后一輪報“0”，并且整個環只剩下他一個的那個人）在最開始的時候報的數是啥，也就是他的初始編號是啥，
這個時候我們發現，以10人環和9人環這兩列為例，下面一輪的每一個人要推出這個人在上一輪報的是啥，只需要（下面的數+k）%上一輪的人數 即可，那我們又可以看到當剩下一人的時候，他報的數肯定是0，而既然每一輪的人能夠推出它在上一輪所報的數，而且每一輪的總人數都會減少1，滿足遞回的性質，那么我們就可以用遞回的方法，從最底端推上來，
int joseph(int m,int k){
if(m == 1) return 0; //到了最底層，也就是上圖中的1人環的時候它在這一輪報的數肯定是0啦，
else {
int temp = (joseph(m-1,k)+k)%m; //如果不是最底層，那么就要由這個人在下一層報的數來推出他在上一層報的數
return temp;
}
}
進階
增加難度：按出局的順序輸出 出局的人的編號，
因為我們上面只是因為知道最后一個人肯定是報0，而知道了他在這一輪報的數，可以求出這個人在上一輪報的數這樣層層地推上去來求解這個人在最后的編號的，
那么這個時候要求在他前面就淘汰出局的人的編號，因為最后一個人我們相當于是遞回進到了最深層然后再層層回傳的，最后一層只有一個人我們肯定也知道就剩那一個人編號為0，那么如果我們不遞回進入到最深層，在中間這些層，每次需要被淘汰的肯定還是在那一層報k-1的那個人，那么既然知道了在某一層被淘汰的人報的數，又知道怎么遞推得到他最初報的數，那么每一層被淘汰的人的初始編號也就不難求得了，
加一個變數i來控制遞回深入的層數，i 其實也就表示我這個函式求的是在第 i 輪被淘汰的那個人的最初編號，
//總共有m個人，每次報到k-1的時候，那個人就出局
int joseph(int m,int k,int i) {
if(i==1) return (k-1)%m; //如果是到了那一層的話，我們也知道在這一層這個被淘汰的人報的數肯定是k-1，那么就回傳k-1，讓上面的遞回層去遞推從而得到它的最初編號，只不過因為k有可能比m大所以還要對m取模，
else return ((Joseph(m-1,k,i-1)+k)%m); //還在遞回中間層的話，就是將下一層遞回回傳的資料去進行遞推得到這個人在這一層報的數然后繼續回傳上一層交由上一層去遞推，
}
for(int i=1;i<=m;i++){ //從1到m，依次輸出在第i輪被淘汰的人的編號，
cout<<joseph(m,k,i)<<endl;
}
有了上面的思路之后，如果題目再稍微變一下，比如從1-n編號（因為取模的問題，直接將其用0~n-1去做然后最后全部再加一會好一些），也不難解決，
參考資料
https://blog.csdn.net/yanweibujian/article/details/50876631（文中圖片來自于此博客）
https://www.cnblogs.com/daimingming/p/3242406.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/297476.html
標籤：其他
上一篇：17w字的軟體測驗靈魂考題：全部掌握拿下阿里P7騰訊T3.2
下一篇：Dokcer核心技術