约瑟夫环

# -*- coding: utf-8 -*-# @Time         : 2019-09-18 21:57# @Author       : Jayce Wong# @ProjectName  : job# @FileName     : josephus.py# @Blog         : https://blog.51cto.com/jayce1111# @Github       : https://github.com/SysuJayce"""约瑟夫斯（Josephus）问题是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。约瑟夫斯问题：有n个囚犯站成一个圆圈，准备处决。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。给定了n和k，一开始要站在什么地方才能避免被处决？递推公式：当n = 1时，f(1, k) = 1当n > 1时，f(n, k) = (f(n - 1, k) + k) mod n**注意**当编号从1开始的时候，如果计算得到f(n, k) = 0，那么需要将其还原为n然后继续递推"""def josephus(n, k):    if n <= 1:        return 1    res = 1    # 注意这里我们使用递推公式的时候，计算的是f(i, k)，因此需要对i取模    for i in range(2, n + 1):        res = (res + k) % i if (res + k) % i != 0 else i    return resprint(josephus(5, 2))