qq_41904237
gary_smlw15
2021-03-21 00:39
采纳率: 33.3%
浏览 63

约瑟夫问题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条回答 默认 最新

  • qq_43414873
    小白小白你好菜 2021-03-21 09:29
    已采纳
    #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;
    }
    点赞 1 评论
  • qq_43414873
    小白小白你好菜 2021-03-21 09:30

    点赞 1 评论

相关推荐