题解 | #约瑟夫环#

约瑟夫环

https://www.nowcoder.com/practice/e417cfe32c74416ca38247f619ddb322

题目链接

约瑟夫环

题目描述

有 n 个人（编号 0 到 n-1）围成一圈，从编号为 s 的人开始报数，报数依次为 1, 2, ..., m。报到 m 的人出队。下一次从出队者的下一个人开始重新报数，循环往复，直到队伍中只剩最后一个人，该人即为"大王"。给定三个整数 n, s, m，请输出最后剩下的"大王"编号。

输入描述:

在一行中输入三个整数 n, s, m，用空格隔开。
约束条件：1 <= n <= 1000, 0 <= s < n, 1 <= m <= 1000。

输出描述:

输出一个整数，表示最后剩下的"大王"编号。

示例说明:

输入 5 1 2
初始队列编号为 [0,1,2,3,4]，从编号 1 开始报数：
1. 1(报1), 2(报2) -> 2 出队，剩余 [0,1,3,4]；
2. 从 3 开始报数：3(报1), 4(报2) -> 4 出队，剩余 [0,1,3]；
3. 从 0 开始报数：0(报1), 1(报2) -> 1 出队，剩余 [0,3]；
4. 从 3 开始报数：3(报1), 0(报2) -> 0 出队，剩余 [3]。
输出 3。

解题思路

这是一个经典的约瑟夫环问题。最直观的解法是模拟整个游戏过程。

思路一：模拟法 (直接但效率较低)

我们可以使用一个列表（如 C++ 的 vector 或 Python 的 list）来存储所有人的编号。然后，我们模拟一轮又一轮的报数和淘汰过程。

初始化: 创建一个包含 0, 1, ..., n-1 的列表 people。
定位起点: 报数从编号为 s 的人开始。在我们的列表中，这个人的初始索引（下标）就是 s。我们用一个变量 current_pos 来追踪每次报数开始时的位置，初始值为 current_pos = s。
循环淘汰: 我们需要淘汰 n-1 个人。外层可以是一个循环 n-1 次。
- 计算淘汰位置: 在每一轮中，我们需要从 current_pos 开始数 m 个人。由于列表是环形的，并且大小在动态变化，我们可以用取模运算来找到要淘汰的人的索引。
  - 要数的步数是 m。但由于 current_pos 本身是第1步，我们实际上需要再前进 m-1 步。
  - 因此，淘汰者的索引为 remove_idx = (current_pos + m - 1) % people.size()，其中 people.size() 是当前圈子里的人数。
- 执行淘汰: 从列表中移除位于 remove_idx 的元素。
- 更新起点: 下一轮报数从被淘汰者的下一个位置开始。在列表中，这个位置恰好就是刚刚移除元素的索引 remove_idx。所以，我们更新 current_pos = remove_idx。
得出结果: 当循环结束后，列表中只会剩下一个人，其编号就是最终的"大王"。

思路二：数学递推法 (高效)

约瑟夫环问题存在一个著名的数学解法。

标准问题: 首先考虑一个标准化的约瑟夫问题：n 个人（编号0到n-1），从编号0开始，每次数m个人。其幸存者的编号可以通过一个递推公式得到。设 f(n, m) 为该问题的解。
- 当只有1个人时，幸存者显然是0号，即 f(1, m) = 0。
- 当有 n 个人时，第一个被淘汰的是 (m-1) % n 号。剩下 n-1 个人，并将问题规模缩小。可以推导出递推关系：f(n, m) = (f(n-1, m) + m) % n。
迭代计算: 我们可以从 f(1,m) 开始，迭代计算出 f(n,m)。
- winner = 0 (对应 f(1, m))
- for i from 2 to n:
  - winner = (winner + m) % i
- 这个循环结束后，winner 就是标准问题（从0开始）的解。
调整起点: 我们的题目是从编号 s 开始，而不是从 0 开始。这相当于将标准问题的结果整体"旋转"s个位置。所以，最终的答案是 (winner + s) % n。

这种方法避免了模拟中的大量数据删除操作，效率极高。

代码

模拟法

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    int n, s, m;
    cin >> n >> s >> m;
    
    // 初始化一个从 0 到 n-1 的列表
    vector<int> people(n);
    numeric_limits<int>::max();
    iota(people.begin(), people.end(), 0);
    
    int current_pos = s;
    while (people.size() > 1) {
        // 计算并找到要移除的元素的索引
        int remove_idx = (current_pos + m - 1) % people.size();
        
        // 从列表中移除元素
        people.erase(people.begin() + remove_idx);
        
        // 更新下一次开始的位置
        current_pos = remove_idx;
    }
    
    cout << people[0] << endl;
    
    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s = sc.nextInt();
        int m = sc.nextInt();

        List<Integer> people = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            people.add(i);
        }

        int currentPos = s;
        while (people.size() > 1) {
            int removeIdx = (currentPos + m - 1) % people.size();
            people.remove(removeIdx);
            currentPos = removeIdx;
             // 防止列表大小为0时取模
            if (people.isEmpty()) break;
        }

        System.out.println(people.get(0));
    }
}

n, s, m = map(int, input().split())

people = list(range(n))

current_pos = s
while len(people) > 1:
    # 计算淘汰者的索引
    remove_idx = (current_pos + m - 1) % len(people)
    
    # 移除淘汰者
    people.pop(remove_idx)
    
    # 更新下一次开始的位置
    current_pos = remove_idx

print(people[0])

数学递推法

c++
java
python

#include <iostream>

using namespace std;

int main() {
    int n, s, m;
    cin >> n >> s >> m;
    
    int winner = 0; // f(1, m)
    // 迭代计算标准问题 f(n, m) 的解
    for (int i = 2; i <= n; ++i) {
        winner = (winner + m) % i;
    }
    
    // 根据起始点 s 调整结果
    int final_winner = (winner + s) % n;
    
    cout << final_winner << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s = sc.nextInt();
        int m = sc.nextInt();

        int winner = 0; // f(1, m)
        // 迭代计算标准问题 f(n, m) 的解
        for (int i = 2; i <= n; i++) {
            winner = (winner + m) % i;
        }

        // 根据起始点 s 调整结果
        int finalWinner = (winner + s) % n;

        System.out.println(finalWinner);
    }
}

n, s, m = map(int, input().split())

# 迭代计算标准问题（从0开始）的解
winner = 0 # f(1, m)
for i in range(2, n + 1):
    winner = (winner + m) % i

# 根据起始点 s 调整最终结果
final_winner = (winner + s) % n

print(final_winner)

算法及复杂度

模拟法
- 时间复杂度： $\mathcal{O}(N^2)$ 。总共需要进行 N-1 次淘汰。在每次淘汰中，从列表（如 std::vector 或 Python list）中删除一个元素需要 $\mathcal{O}(N)$ 的时间。
- 空间复杂度： $\mathcal{O}(N)$ ，用于存储所有人的编号。
数学递推法
- 时间复杂度： $\mathcal{O}(N)$ 。只需要一个简单的循环来计算递推公式。
- 空间复杂度： $\mathcal{O}(1)$ 。只使用了几个变量来存储中间结果。