问题描述：编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈，从编号为 1 的士兵开始依次报数（1，2，3…这样依次报），数到 m 的 士兵会被杀死出列，之后的士兵再从 1 开始报数。直到最后剩下一士兵，求这个士兵的编号。
则 f(n,m)为输出的编号
1. 当n==1时, f(1,m)=1;
2.那我们现在探讨 当n==k时, f(k,m) 和f(k-1,m) 的关系即可
| old | 1 | 2 | 3 | … | m-1 | m | m+1 | m+2 | … | n |
|---|---|---|---|---|---|---|---|---|---|---|
| new | n-m+1 | n-m+2 | n-m+3 | … | n-1 | 没了 | 1 | 2 | … | n-m |
那么 old 和new 的关系是什么呢?
易得: old = (new+m)%n
可是这里有一种情况: new+m==0 ; 即new 有n-1个, old 有n个
则: old = (new + m-1)%n +1
则: f(k,m)= (f(k-1,m)+ m-1)%n +1
所以约瑟夫环可以写为
int f(n,m):
return n<=1? 1: (f(n-1,m)+ m-1)%n +1
版权声明：本文为qianyedoufulao原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。