题目描述

约瑟夫斯(Josephus)问题是一个出现在计算机科学和数学中的问题。 在计算机编程的算法中,类似问题又称为约瑟夫环。 约瑟夫斯问题:有n个囚犯站成一个圆圈,准备处决。 首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。 接着,再越过k-1个人,并杀掉第k个人。 这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。

给定了n和k,一开始要站在什么地方才能避免被处决?

# -*- coding: utf-8 -*-
# @Time         : 2019-09-18 21:57
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : josephus.py
# @Blog         : https://sysujayce.github.io/
# @Github       : https://github.com/SysuJayce


"""
递推公式:
当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 res


print(josephus(5, 2))