詳見：http://blog.yemou.net/article/query/info/tytfjhfascvhzxcyt355

假設(shè)下標(biāo)從0開始，0，1，2 .. m-1共m個人，從1開始報數(shù)，報到k則此人從環(huán)出退出，問最后剩下的一個人的編號是多少？

現(xiàn)在假設(shè)m=10

0 1 2 3 ?4 5 6 7 8 9 ? ?k=3

第一個人出列后的序列為：

0 1 3 4 5 6 7 8 9

即:

3 4 5 6 7 8 9 0 1（*）

我們把該式轉(zhuǎn)化為:

0 1 2 3 4 5 6 7 8 (**)

則你會發(fā)現(xiàn): （(**)+3）%10則轉(zhuǎn)化為(*)式了

也就是說，我們求出9個人中第9次出環(huán)的編號，最后進行上面的轉(zhuǎn)換就能得到10個人第10次出環(huán)的編號了?

設(shè)f(m,k,i)為m個人的環(huán)，報數(shù)為k，第i個人出環(huán)的編號，則f(10,3,10)是我們要的結(jié)果

當(dāng)i=1時，? f(m,k,i) = (m+k-1)%m

當(dāng)i!=1時，? f(m,k,i)= ( f(m-1,k,i-1)+k )%m

所以程序如下：

int?fun(int?m,int?k,int?i){ ????if(i==1) ????????return?(m+k-1)%m; ????else ????????return?(fun(m-1,k,i-1)+k)%m; } int?main(int?argc, char* argv[]) { ????? ????for(int?i=1;i<=10;i++) ????????printf("第%2d次出環(huán)：%2d\n",i,fun(10,3,i)); ????return?0; }

?

第 1次出環(huán)： 2 第 2次出環(huán)： 5 第 3次出環(huán)： 8 第 4次出環(huán)： 1 第 5次出環(huán)： 6 第 6次出環(huán)： 0 第 7次出環(huán)： 7 第 8次出環(huán)： 4 第 9次出環(huán)： 9 第10次出環(huán)： 3

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的约瑟夫环：递归算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。