约瑟夫环问题.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2019/10/20 6:48 PM
# @Author  : Slade
# @File    : 约瑟夫环问题.py

'''
N个人的编号为：
0   1   2   3   ...     N-1
第一个自杀的人是（M-1）%N，比如M = 3，第一个被淘汰的就是2，排列变化如下：
0   1   2 ...   M-2     M   ... N-1
因为M-1死了，所以又要从0开始报数，排列变化如下：
M   M+1   ... N-1 0   1   2   ... M-2
将上面的排列顺序重新编号：
M   M+1   ... N-1 0   1   2   ... M-2
0   1   ...     ...     ...       M-1
问题变为（N-1）个人，报到为（M-1）的人自杀，问题规模减小了。这样一直进行下去，最后剩下编号为0的人。用函数表示：F(1)=0
倒数第二个自杀的人，必然倒数第三轮自杀的人后的那个，所以：
F(2) = F(1) + M，所以递归公式为：F(i) = F(i-1) + M，因为可能会超出总人数范围，所以要求模
F(i) = (F(i-1) + M)%i
'''

'''
以下是新环与旧环中下一个要人扔海里的人位置:
旧环   0   1   2        4   5   6   7   8   9
新环   6   7   8        0   1   2   3   4   5

N = 10 , M = 4
如何由新环中的 3    得到旧环中的 7 呢。其实可以简单地逆推回去 :
新环=(旧环中编号-最大报数值)%旧总人数
旧环 = (新环中编号+最大报数值)%旧总人数

来自：https://www.cnblogs.com/nxf-rabbit75/p/10707989.html
'''
'''
约瑟夫环问题：一圈共有N个人，开始报数，报到M的人自杀，然后重新开始报数，问最后自杀的人是谁？
问题重述：N个人（编号0~(N-1))，从0开始报数，报到(M-1)的自杀，剩下的人继续从0开始报数。求最后自杀者的编号。
'''

def getNumber(N, M):
    result = 0
    for i in range(2, N + 1):
        print(result)
        result = (result + M) % i
    return result + 1