C++循环链表求解约瑟夫同题

题目描述

编写程序实现N个人围成一圈,每个人都有一个编号,编号由入圈的顺序决定,第一个入图的人编号为1,最后一个为N,从第k(1<=k<=N)个人开始报数,数到m (1<=m<=N)的人将出圈,然后下一个人继续从1开始报数,直至所有人全部出圈,求依次出的编号。

源代码

以下是C++实现的N个人围成一圈，按照指定规则报数并出圈的程序代码：

#include <iostream>
#include <vector>

using namespace std;

// 求解约瑟夫问题
vector<int> josephus(int n, int k, int m) {
    vector<int> result; // 存储依次出圈的编号

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

    int current = k - 1; // 当前报数的人的索引
    while (!people.empty()) {
        current = (current + m - 1) % people.size(); // 计算当前报数的人的索引

        result.push_back(people[current]); // 将当前报数的人的编号加入结果中
        people.erase(people.begin() + current); // 从列表中删除当前报数的人

        // 更新当前报数的人的索引
        if (current == people.size()) {
            current = 0;
        }
    }

    return result;
}

int main() {
    int n, k, m;
    cout << "Please input the number of people: ";
    cin >> n;
    cout << "Please input the value of k: ";
    cin >> k;
    cout << "Please input the value of m: ";
    cin >> m;

    vector<int> result = josephus(n, k, m);

    // 输出依次出圈的编号
    cout << "The sequence of people going out: ";
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
    cout << endl;

    return 0;
}

在上面的代码中，我们定义了一个函数josephus来求解约瑟夫问题。该函数接受三个参数：n表示人数，k表示从第几个人开始报数，m表示数到多少的人出圈。函数内部使用一个vector来存储人员编号，初始化为1到n。然后，根据规则依次报数并出圈，直到所有人全部出圈。最后，将依次出圈的编号存储在另一个vector中，并返回该vector作为结果。

在主函数中，我们通过用户输入获取人数n、起始报数的位置k和数到多少的人出圈m。然后调用josephus函数求解约瑟夫问题，并输出依次出圈的编号。