经典语法题-JZTXT

1. 约瑟夫环问题

题目描述

已知\(n\)个人（以编号\(1，2，3，...，n\)分别表示）围坐在一张圆桌周围，从编号为\(k\)的人开始报数，数到\(m\)的那个人出圈，他的下一个人又从\(1\)开始报数，数到\(m\)的那个人又出圈；按照这个规律一直重复下去，最后一个出局的人为游戏的最终胜利者。

输入格式

\(n\) \(m\) \(k\)

输出格式

输出胜利者的编号

输入样例

11 3 1

输出样例

C++代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m, k;
bool st[N];

int main()
{
    cin >> n >> m >> k;
    
    int cnt = 0, j = 0; //cnt表示出环的人数，j表示报的数
    for (int i = k; ; i = (i + 1) % n) //模拟报数的人的编号
    {
        if (i == 0) i = n;
        while (st[i])
        {
            i = (i + 1) % n;
            if (i == 0) i = n;
        }
        
        j ++ ;
        
        if (j % m == 0)
        {
            cnt ++ ;
            st[i] = true;
        }
        
        if (cnt == n - 1) break;
    }
    
    for (int i = 1; i <= n; i ++ )
        if (!st[i])
            cout << i << endl;
    
    return 0;
}