2023短学期0906题解

yoongi blog / 2023-09-06 / 原文

1.出圈
Description
设有n个人围坐一圈并按顺时针方向从1到n编号，从第1个人开始进行1到m的报数，报数到第个m人，此人出圈，再从他的下一个人重新开始1到m的报数，如此进行下去直到所剩下一人为止。

Input
输入多行，每行２个数，分别表示n和m.

Output
计算每一行中最后剩下这个人的编号．

Samples
input
10 3
output
4

Analysis
这道题是一个经典的约瑟夫问题（Josephus Problem），可以使用模拟或者数学方法来解决。以下是解题思路：

😋模拟方法：

首先，创建一个包含n个人编号的列表，表示所有人。
设置一个变量current_index，用于跟踪当前报数的人的索引，初始值为0。
进行循环，直到只剩下一个人为止。在每一轮循环中：
从当前人开始，按顺时针方向数m个人。
找到要出圈的人，将其从列表中移除。
更新current_index以指向下一个人。
循环结束后，剩下的那个人就是答案。

😀数学方法：

有一个数学公式可以直接计算出最后剩下的人的编号。这个公式是：

f (n, m) = (f (n -1, m) + m-1）% n + 1

其中，f(n, m)表示n个人报数到m出圈后最后剩下的人的编号。
使用递归或迭代方式计算f(n, m)，当n等于1时，最后剩下的人的编号就是1。
这两种方法都可以用来解决这个问题。模拟方法更直观，而数学方法则更快速。根据你的偏好和编程经验，你可以选择其中一种方法来实现。

Solution

模拟方法

#include <iostream>
#include <vector>

using namespace std;

int josephusSimulation(int n, int m) {
    vector<int> people(n);
    for (int i = 0; i < n; ++i) {
        people[i] = i + 1; // 初始化人的编号
    }

    int current_index = 0;
    while (people.size() > 1) {
        current_index = (current_index + m - 1) % people.size(); // 找到要出圈的人
        people.erase(people.begin() + current_index); // 移除出圈的人
    }

    return people[0];
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        int result = josephusSimulation(n, m);
        cout << result << endl;
    }
    return 0;
}

数学方法（推荐👍）

#include <iostream>
using namespace std;

int f (int n, int m){
    if (n == 1) {
        return 1;
    }   
    return (f (n - 1, m) + m - 1) % n + 1;    
}

int main (){
    int n,m;
    while （cin >> n>>m）{
        cout << f (n, m) << endl;
    }
    return 0;
}