约瑟夫环围圈报数问题


N 个人围成一圈顺序编号,从 1 号开始按 1、2、31 顺序报数,报 3 者退出圈外,其余的人再从 1、2、3 开始报数,报 3 的人再退出圈外,依次类推。

请按退出顺序输出每个退出人的原序号。

要求使用环行链表编程。

输入格式

第一行包含整数 T,表示共有 T 组测试数据。

每组数据一行,一个整数 N。

输出格式

每组数据输出一行,一个结果,包含每个退出人的原序号,用空格隔开。

数据范围

1≤T≤5,
1≤N≤50

输入样例:

1
4

输出样例:

3 2 4 1

思路

这个题目最典型的做法就是用队列来模拟,但其实我们可以换一种思路。我们可以直接获得下一个报到3的人,也就是代码中的 start = (start + 3 % m - 1 + m) % m,+3可以获得下一个报到3的人,但是由于3可能大于m,所以这个取模,然后-1是因为减完以后可能小于0,所以这里+m,然后再模m即可。

代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 50;

int a[N];
int m;

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> m;
        int start = 0;
        for (int i = 0; i < N; i++) a[i] = i + 1;
        for (; m > 0; m--)
        {
            start = (start + 3 % m - 1 + m) % m;
            cout << a[start] << " ";
            copy(a + start + 1, a + m, a + start);
        }
        cout << endl;
    }
    return 0; 
}

 

百度未收录
  • 分享:
评论
还没有评论
    发表评论 说点什么