Skip to content

14089: 【原4089】约瑟夫环

题目

题目描述

author: 程序设计思想与方法助教组_刘威 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4089 ## 问题描述 设计并实现一个解决约瑟夫环问题的类Joseph。当需要解决一个n个人间隔为m的约瑟夫环问题,可以构建一个对象Joseph obj(n, m),然后调用obj.simulate()输出模拟删除过程。

输入输出描述

输入

  • 输入为两个正整数n和m,空格分隔,分别代表编号长度和间隔长度,编号长度n<=50。

输出

  • 输出为n个整数,空格分隔。

程序运行示例1

Sample Input 1

10 4

Sample Output 1

5 9 3 8 4 1 10 2 7 6

程序运行示例2

Sample Input 2

30 11

Sample Output 2

12 23 4 16 28 10 24 7 21 6 22 9 27 15 3 26 18 13 8 5 11 17 25 2 30 1 20 14 19 29

注意

  • 约瑟夫环的起始编号为1,编号为[1, n]

  • 注意判断数组是否溢出。

  • m的值可以大于n。

FineArtz's solution

/* 约瑟夫环 */
#include <iostream>
using namespace std;

class Node{
public:
    int index;
    Node *next;
};

int main(){
    int n, m;
    cin >> n >> m;
    Node *head, *p, *q;
    head = p = new Node;
    p->index = 0;
    for (int i = 2; i <= n; ++i){
        q = new Node;
        q->index = i - 1;
        p->next = q;
        p = q;
    }
    p->next = head;
    q = head->next;
    while (q->next != q){
        for (int i = 1; i < m; ++i){
            p = q;
            q = q->next;
        }
        cout << q->index + 1 << " ";
        p->next = q->next;
        delete q;
        q = p->next;
    }
    cout << q->index + 1 << endl;
    delete q;
    return 0;
}

ligongzzz's solution

#include "iostream"
using namespace std;

constexpr auto maxNum = 1000;

class Joseph {
    bool exi[maxNum];
public:
    int n, m;
    Joseph(int n,int m):n(n),m(m){
        for (int i = 0; i <= n; i++) exi[i] = true;
    }

    void simulate() {
        int num = n;
        int cal = 0, sci = 1;
        while (num > 0) {
            if (!exi[sci]) {
                sci++;
                if (sci> n)
                    sci = 1;
                continue;
            }
            if (cal == m) {
                cout << sci;
                cal = 0;
                exi[sci] = false;
                num--;
                if (num > 0)
                    cout << " ";
            }
            sci++;
            cal++;
            if (sci>n)
                sci = 1;
        }
    }
};

int main() {
    int m, n;
    cin >> m >> n;
    Joseph j(m, n);

    j.simulate();

    return 0;
}