gary_smlw15
2021-03-21 00:39
采纳率: 25%
浏览 98

约瑟夫问题C++ (萌新学习c++)

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

有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;
}

2条回答 默认 最新

相关推荐 更多相似问题