# 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;
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;
}
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;
}
``````