链表之单链表约瑟夫问题（二）

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后[1]  结果+1即为原问题的解。

　　约瑟夫环：递归算法

　　假设下标从0开始，0，1，2 .. m-1共m个人，从1开始报数，报到k则此人从环出退出，问最后剩下的一个人的编号是多少？

　　现在假设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（*）

　　我们把该式转化为:

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

　　则你会发现: （(**)+3）%10则转化为(*)式了

　　也就是说，我们求出9个人中第9次出环的编号，最后进行上面的转换就能得到10个人第10次出环的编号了

　　设f(m,k,i)为m个人的环，报数为k，第i个人出环的编号，则f(10,3,10)是我们要的结果

　　当i=1时，  f(m,k,i) = (m+k-1)%m

　　当i!=1时，  f(m,k,i)=

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/50444098