约瑟夫环问题：逃出生天

题目描述

在一次逃生中，pzc 闯入了一座魔堡。魔王准备进行献祭仪式，将 pzc 和他的奴隶们围成一个圈，并从第一个开始，隔一个献祭一个人。

例如，有 5 个人，献祭顺序为 2，4，1，5，3。

魔王突然心情大好，决定放走最后一个留下来的人。为了活命，pzc 需要找出最后留下来的人的编号。

输入格式

第一行一个整数 N，表示参与献祭的人数。

输出格式

输出一行一个整数，表示最后留下来的那个编号。

样例 #1

样例输入 #1

5

样例输出 #1

3

样例 #2

样例输入 #2

10

样例输出 #2

5

解题思路

这是一个经典的约瑟夫环问题。

首先，我们可以用一个列表来表示 N 个人，初始状态下所有人的状态都是存活的。然后，我们可以用一个指针 cur 来指向当前要献祭的人。每次献祭之后，我们将指针向后移动 k-1 个位置，表示下一个要献祭的人。

当指针移动到了列表的末尾时，我们需要将指针重新指向列表的开头。这可以通过取余运算来实现，即 cur = (cur + k - 1) % N。

每次献祭之后，我们将当前要献祭的人的状态设置为死亡，并将列表中存活的人数减 1。重复执行这个过程，直到只剩下最后一个存活的人。

最后剩下的那个人的编号就是我们要求的答案。

代码实现

def josephus(N):
    people = [True] * N  # 初始状态下所有人都是存活的
    cur = 0  # 当前要献祭的人的索引

    for _ in range(N - 1):  # 执行 N-1 次献祭
        count = 0  # 记录当前已经数过的存活的人的数量
        while count < k:
            if people[cur]:
                count += 1
            if count == k:
                people[cur] = False  # 献祭当前的人
            cur = (cur + 1) % N  # 将指针移到下一个存活的人

    # 找到最后一个存活的人的编号
    for i in range(N):
        if people[i]:
            return i + 1
    return -1  # 如果没有找到存活的人，则返回 -1

N = int(input())
print(josephus(N))