大家好，又见面了，我是你们的朋友全栈君。
第一次出队的那个人的编号是( m-1)%n ，第二次重新开始的编号是m%n
约瑟夫环是一个经典的数学问题，我们不难发现这样的依次报数，似乎有规律可循。为了方便导出递推式，我们重新定义一下题目。
问题： N个人编号为1，2，……，N，依次报数，每报到M时，杀掉那个人，求最后胜利者的编号。
这边我们先把结论抛出了。之后带领大家一步一步的理解这个公式是什么来的。
一般解法
找到出列的人，把它删掉。这个人的编号是(m-1)%n，m是报数，n是总的人数
时间复杂度是O(nm)
递推公式：
f(N,M)=(f(N−1,M)+M)%N
- f(N,M)表示，N个人报数，每报到M时杀掉那个人，最终胜利者的编号
- f(N−1,M)表示，N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号
公式理解：
python 代码：
# -*- coding:utf-8 -*-
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
# 用列表来模拟环，新建列表range(n)，是n个小朋友的编号
if not n or not m:
return -1
lis = range(n)
i = 0
while len(lis)>1:
i = (m-1 + i)%len(lis) # 递推公式
lis.pop(i)
return lis[0]
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/136192.html原文链接：https://javaforall.net
