题解 | #约瑟夫环#

题目描述

n个人（0,1,2,3,4...n-1），围成一圈，从编号为k的人开始报数，报数报到m的人出队（报数是1,2,...m这样报的）。下次从出队的人之后开始重新报数，循环往复，当队伍中只剩最后一个人的时候，那个人就是大王。现在，给定n，k，m， 请你求出大王的编号。

输入描述：

输入一行包含三个整数n,k,m
1<=n<=100,1<=k<=n-1,1<=m<=100

输出描述：

输出一个整数

示例1

输入

5 1 2

输出

3

思路

一、循环队列

实现如下：

#include<cstdio>
#define N(a) (a+1)%n  
int main()
{
    int n,k,m,f=0,r=f;
    scanf("%d%d%d",&n,&k,&m);
    int*q=new int[n];
    do q[r]=(r+k)%n,r=N(r);while(r!=f);
    while(N(f)!=r)
    for(int i=0;i<m;++i)
    {
        q[r]=q[f];
        f=N(f);
        if(i!=m-1)r=N(r);
    }
    printf("%d",q[f]);
    delete[]q;
}

二、动态规划

从编号为0开始报数，可用动态规划求解：声明长度为 n 的一维数组 dp ，其中 dp[i] 表示 i 个人玩游戏的大王编号，则 dp[n] 即为题解，相应的状态转移方程为：
dp[i] = (dp[i-1] + m) mod i（i > 1），初始化状态：dp[1] = 0。
状态转移方程的含义是删除某一编号后重新编的号与删除前的编号的映射关系。

从编号为 k 开始，(dp[n]+k)mod n 即可，实现如下：

#include<cstdio>
int main()
{
    int n,k,m,s=0;
    scanf("%d%d%d",&n,&k,&m);
    for(int i=2;i<=n;++i)s=(s+m)%i;
    printf("%d",(s+k)%n);
}