题目描述

有$100$个人围成一圈，每个人有一个唯一的编号，从$1$到$100$。他们从编号为$1$的人开始依次报数，每报到$M$的人自动退出圈圈。接着，下一个人重新从$1$开始报数。如此循环，直到剩余的人数少于$M$为止。请输出最后剩余的人的原始编号，按从小到大的顺序，以英文逗号分隔。

解题思路

本题类似于经典的“约瑟夫环”问题，但终止条件有所不同。约瑟夫问题通常是直到最后只剩一个人，而本题的终止条件是当剩余人数少于$M$时停止。

具体步骤如下：

1. 初始化：创建一个包含$1$到$100$的数组或列表，表示所有人的编号。
2. 模拟过程：
   • 从当前起始位置开始，每数到第$M$个人时，将其从列表中移除。
   • 移除后，下一个人作为新的起始位置，重新开始从$1$报数。
3. 终止条件：当剩余的人数小于$M$时，停止删除过程。
4. 输出结果：将剩余的人的编号按从小到大的顺序排序，并以英文逗号分隔输出。

需要注意的是：

• 输入$M$的合法性检查，如果$M \leq 1$或$M \geq 100$，则输出“ERROR!”。
• 在模拟过程中，需要有效地处理环形结构，可以通过取模运算来实现。

代码分析

• 使用vector<int>来存储当前圈中的人的编号。
• 使用一个变量current来记录当前报数的位置索引。
• 在每次删除时，通过计算 (current + M - 1) % people.size() 来确定要删除的位置。
• 删除后，current更新为被删除位置的下一个位置，注意处理环形。
• 循环进行，直到剩余人数少于$M$。
• 最后，对剩余的人的编号进行排序并格式化输出。

cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    int M;
    cin >> M;
    if(M <=1 || M >=100){
        cout << "ERROR!";
        return 0;
    }
    // 初始化100个人
    vector<int> people;
    for(int i=1;i<=100;i++) people.push_back(i);
    int current =0;
    while(people.size() >= M){
        // 找到第M个人的位置
        current = (current + M -1) % people.size();
        // 删除该人
        people.erase(people.begin()+current);
    }
    // 排序
    sort(people.begin(), people.end());
    // 输出
    string res = "";
    for(int i=0;i<people.size();i++){
        res += to_string(people[i]);
        if(i != people.size()-1) res += ",";
    }
    cout << res;
}

python

def main():
    M = int(input())  # 读取输入的M值
    if M <= 1 or M >= 100:
        print("ERROR!")  # 输入不合法时输出错误信息
        return

    # 初始化100个人
    people = list(range(1, 101))  # 创建一个包含1到100的列表
    current = 0

    # 模拟报数和删除过程
    while len(people) >= M:
        current = (current + M - 1) % len(people)  # 找到第M个人的位置
        people.pop(current)  # 删除该人

    # 对剩余的人进行排序
    people.sort()

    # 输出结果，按格式连接
    result = ",".join(map(str, people))  # 将列表转换为字符串并以逗号分隔
    print(result)


if __name__ == "__main__":
    main()

java

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();  // 读取输入的M值

        if (M <= 1 || M >= 100) {
            System.out.println("ERROR!");  // 输入不合法时输出错误信息
            return;
        }

        // 初始化100个人
        List<Integer> people = new ArrayList<>();
        for (int i = 1; i <= 100; i++) {
            people.add(i);  // 添加编号1到100
        }

        int current = 0;

        // 模拟报数和删除过程
        while (people.size() >= M) {
            current = (current + M - 1) % people.size();  // 找到第M个人的位置
            people.remove(current);  // 删除该人
        }

        // 对剩余的人进行排序
        Collections.sort(people);

        // 输出结果，按格式连接
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < people.size(); i++) {
            result.append(people.get(i));  // 添加编号
            if (i != people.size() - 1) {
                result.append(",");  // 连接逗号
            }
        }
        System.out.println(result.toString());  // 输出结果
    }
}

题目内容

$100$个人围成一圈，每个人有一个编码，编号从$1$开始到$100$。

他们从$1$开始依次报数，报到为$M$的人自动退出圈圈，然后下一个人接着从$1$开始报数，直到剩余的人数小于$M$。

请问最后剩余的人在原先的编号为多少？

输入描述

输入一个整数参数 $M$

输出描述

如果输入参数$M$小于等于$1$或者大于等于$100$，输出“$ERROR!$”；

否则按照原先的编号从小到大的顺序，以英文逗号分割输出编号字符串

样例1

输入

3

输出

58,91

说明

输入$M$为$3$，最后剩下两个人。

样例2

输入

4

输出

34,45,97

说明

输入$M$为$4$，最后剩下三个人。