约瑟夫问题C++ （萌新学习c++）

Question

约瑟夫问题，希望大佬可以帮帮我

有n人（编号分别为1到n号）围成一圈，从第s人开始报数，报到第m的人出列，然后从出列的下一人重新开始报数，报到第m的人又出列，……，如此重复直到n-1全部出列，只剩最后一个人为止。求剩下的最后一人是谁？

输入

一行，三个整数n，m，s，（0<=n，m，s<=1000）意义如上。

输出

一行，一个正整数，表示最后剩下的人的编号。

输入样例

8 3 1

输出样例

7

要求从第s个数开始，数m个出列，第s个不出列

而我的程序是从s开始直接先出列s再数m个

请问怎么更改代码？

下面是我的代码

#include <iostream>

void JosePhus(int n, int m, int start) {
    int i, *arr = new int[n]; // 动态分配数组
    int count; // 保存当前已站出来的人数

    for(i = 0;i < n; i++) // 初始化，把各位置号存入数组中
        arr[i] = i + 1;
    count = 1;
    start--; // 因为数组下标从0开始，所以要减1
    while(count < n) { // 当前已站出来的人数
        std::cout << arr[start] << ","; // 输出当前要站出来的人的位置号
        for(i = start; i < (n - count); i++)
            arr[i] = arr[i+1]; // 把位置号前移

        // start + m - 1:减1是因为该位置号的人已出列，位置号前移了一位
        // n - count: 当前剩下的人数
        start = (start + m - 1) % (n - count); // 考虑到尾了，要从头开始，所以用取余，或者用判断方法

        count++;
    }
    std::cout << arr[0] << "\n";
}

int main(int argc, const char * argv[]) {
    int n, m, start; // n:人数  m:数到多少出列  start:开始位置

    std::cout << "请输入n,m,start:\n";
    while(std::cin >> n >> m >> start) {
        JosePhus(n, m, start); // 调用解决约瑟夫问题的函数
        std::cout << "请输入n,m,start:\n";
    }
    return 0;
}

Answer 1

#include <iostream>
 
void JosePhus(int n, int m, int start) {
    int i, *arr = new int[n]; // 动态分配数组
    int count = 1;; // 保存当前已站出来的人数
    for(i = 0;i < n; i++) // 初始化，把各位置号存入数组中
        arr[i] = i + 1;
    int sum = n;
    //输出参考    printf("出列顺序为：");
    while(count < n) { // 出列顺序
        start--; // 因为数组下标从0开始，所以要减1
        int index = (start+m-1) % sum;//记录第count次出列的下标 
    //输出参考  std::cout << arr[index] << " "; // 输出当前要站出来的人的位置号
        for(i = index; i < sum-1; i++)//出列相当于人数少了一个，循环上限为sum-1
            arr[i] = arr[i+1]; // 把位置号前移
        start = index + 1;//第count+1次开始位置为上次出列下标位置+1
        sum--;//总人数减一 
        count++;//出列人数+1 
    }
    std::cout<< arr[0] <<"\n";//最后剩下的第一个元素为最后留下的人
}
 
int main(int argc, const char * argv[]) {
    int n, m, start; // n:人数  m:数到多少出列  start:开始位置
 
    std::cout << "请输入n,m,start:\n";
    while(std::cin >> n >> m >> start) {
        JosePhus(n, m, start); // 调用解决约瑟夫问题的函数
        std::cout << "请输入n,m,start:\n";
    }
    return 0;
}