P1996 约瑟夫问题

- 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[];

int n,m,q,i,j;

int main()

{

    cin>>n>>m;

    do

    {

        i++;

        if(i==n+)

            i=;

        if(!chu[i])

            q++;

        if(q==m)

        {

            q=;

            cout<<i<<" ";

            chu[i]=true;

            j++;

        }

    }while(j!=n);

    return ;

}

2）

///队列+数组模拟链表

#include <iostream>

using namespace std;

const int N = ;

int n,m,gs,k;

int q[N];///next is what(嘻嘻)

int main()

{

    cin>>n>>m;

    for(int i=;i<n;i++)

        q[i]=i+;

    q[n]=;

    int nxt=n;

    while(gs<n)

    {

        k=;

        while(k<m)

        {

            nxt=q[nxt];

            k++;

        }

        cout<<q[nxt]<<" ";

        gs++;

        ///delete the nxt

        q[nxt]=q[q[nxt]];

    }

    return ;

}

巴特西

luoguP1996 约瑟夫问题

P1996 约瑟夫问题

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章