本文主要是介绍约瑟夫环问题-基础版（数学归纳法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题：n个人围成一圈，从1开始报数，报到m的人死，然后后面的人接着报数。。。直到最后剩下一个人，求最后这个人的初始编号是多少
可以根据游戏进程进行正向模拟，但是我觉得这种方式是最自然的思考模式，肯定不是最优算法。
实际上：确实不是最优。
更优的算法是根据结果进行倒推：
首先为所有人编号：
初始号：0 1 2 3 4 5 ... n-1
第一轮：0 1 2 3 4 5 ... m-1(死) m m+1 ...n-1
第二轮：m m+1 n+2 .... n-1 0 1 2 ... m-2
...
最后轮：0
所以设f(x)为最后活着的人在剩下人数x+1时的编号
f(1)=0 （最后一个人的时候编号为0）
f(2)=?
剩下2个人的编号情况：既然这个人活下来了，那么死的肯定是另一个人，那个死的人的位置是m-1号（m-1号位置的报m，死），那么存活到最后一轮的人的编号在此轮就是m。
从第一轮第二轮的座位号也可以看出来，第二轮0号位应该是第一轮的m号位，实际上每轮都会往左边移动m个位置，
因为前面的m个人会死一个，m-1个人移动到队尾。
综上可以归纳出：
所以f(i)=f(i-1)+m
考虑到可能超过总长度，所以需要取模
所以
position=0 //f(0)
for(int i=2;i<=n;i++){position=(position+m)%n
}
//注意最后结果是position+1 因为最开始编号是0开始的 而真实报数是1开始的
标题基础版，是因为有个进阶版，这就是我查这道题的源头，群里老哥问到的问题：游戏结束条件从剩下一人变成了剩下一半
待续
这篇关于约瑟夫环问题-基础版（数学归纳法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
