P1996 约瑟夫问题 题解

P1996 约瑟夫问题 题解

题目：

约瑟夫问题

题目描述

$n$ 个人围成一圈，从第一个人开始报数,数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

输入格式

输入两个整数 $n,m$。

输出格式

输出一行 $n$ 个整数，按顺序输出每个出圈人的编号。

样例 #1

样例输入 #1

10 3
1

样例输出 #1

3 6 9 2 7 1 8 5 10 4
1

提示

$1\le m,n\le 100$

Code:

#include
using namespace std;               
int main()
{
	int n,m;
	cin>>n>>m;
	int a[n+1],j=n,k=1;
    for(int i=1;i<n;i++)a[i]=i+1;    
    a[n]=1;                                    
    for(int p=1;p<=n;p++)                             
    {
        while(k<m)                          
        {
            j=a[j];
            k++;
        } 
        printf("%d ",a[j]); 
        a[j]=a[a[j]]; 
		k=1;
    }                 
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23