luoguP1996 约瑟夫问题

- 2.5K通过
- 4.7K提交
题目提供者 Timothy
标签洛谷原创云端
难度普及-
时空限制 1s / 128MB

题目背景

约瑟夫是一个无聊的人！！！

题目描述

n个人(n<=100)围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈,……依次类推,直到所有的人都出圈,请输出依次出圈人的编号.

输入输出格式

输入格式：

n m

输出格式：

出圈的编号

输入输出样例

输入样例#1：

10 3

输出样例#1：

3 6 9 2 7 1 8 5 10 4

说明

你猜，你猜，你猜猜猜......

猜不着吧，我也不告诉你！！！

思路:

　 首先这道题暴力可以过....(数据水死了qwq)

接着，本题我们可以用数组建立标志位(链表)等方法求解，但如果用上数据结构中循环链的思想，则更贴切题意，解题效率更高。ｎ人围成一圈，把一人看成一个结点，ｎ人之间的关系采用链接方式，即每一结点有一个前继结点和一个后继结点，每一个结点有一个指针指向下一个结点，最后一个结点指针指向第一个结点。这就是单循环链的数据结构。当ｍ人出列时，将ｍ结点的前继结点指针指向ｍ结点的后继结点指针，即把ｍ结点驱出循环链。

　　1、建立循环链表。

　　当用数组实现本题链式结构时，数组q[i]作为"指针"变量来使用，q[i]存放下一个结点的位置。设立指针j指向当前结点，则移动结点过程为j=q[j]，当数到m时，m结点出链，则q[j]=q[q[j]]。当直接用链来实现时，则比较直观，每个结点有两个域：一个数值域，一个指针域，当数到m时，m出链，将m结点的前继结点指针指向其后继结点；

　　2、设立指针，指向当前结点，设立计数器，计数数到多少人；

　　3、沿链移动指针，每移动一个结点，计数器值加１，当计数器值为ｍ时，则ｍ结点出链，计数器值置为１。

　　4、重复３，直到n个结点均出链为止。

上代码:

1）

///暴力 
#include<iostream>
using namespace std;

bool chu[101];
int n,m,q,i,j;

int main()
{
    cin>>n>>m; 
    do
    {
        i++;
        if(i==n+1)
            i=1;
        if(!chu[i])
            q++;
        if(q==m)
        {
            q=0;
            cout<<i<<" ";
            chu[i]=true;
            j++;
        }
    }while(j!=n);
    return 0;
}

2）

///队列+数组模拟链表 
#include <iostream>
using namespace std;

const int N = 101;
int n,m,gs,k;
int q[N];///next is what(嘻嘻)

int main()
{
    cin>>n>>m;
    for(int i=1;i<n;i++)
        q[i]=i+1;
    q[n]=1;
    int nxt=n;
    while(gs<n)
    {
        k=1;
        while(k<m)
        {
            nxt=q[nxt];
            k++;
        }
        cout<<q[nxt]<<" ";
        gs++;
        ///delete the nxt
        q[nxt]=q[q[nxt]];
    }
    return 0;
}