大家好，欢迎来到IT知识分享网。
问题：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开始的
标题基础版，是因为有个进阶版，这就是我查这道题的源头，群里老哥问到的问题：游戏结束条件从剩下一人变成了剩下一半
待续
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/13595.html
