OJ 1018 报数游戏

描述

 

n个人围成一圈（编号为1 - n），从第1个人开始报数，报到k的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。

例如：n = 3，k = 2。2号先出列，然后是1号，最后剩下的是3号。

输入

 

输入为单组测试数据。

输入2个数n和k，表示n个人，数到k出列。(2 <= n, k <= 200)

输出

 

输出一个整数表示最后剩下的人的编号。

输入样例 1 

10 3

输出样例 1

4

题目是一个亚瑟夫环的问题，题目说明了到了第n号就要删除一个数据，并且后面重新从一开始，一直循环，直到结束，也就是一步一步一个一个被删除，如果只有一个很好分析就是第一个即序号为1，如果是两个那么就是在1，2之间报数知道一个人被踢出，如n=4，那么就是1，2，1，2，就是报数的1，2，3，4最后2被踢出所以序号为1 ，三也是一样的，三个数那就是1，2，3，1//2，3，2，3最后，随着递推会发现一个规律，假设用f表示找序号，有k个人，报n则踢出,例子中n=4，那么f(1)=0,f(2)=1,f(3)=2……-->f(2)=(f(1)+n)%2=0+1=1,f(3)=(f(2)+n)%3=1+1=2……f(k)=(f(k-1)+n)%k。也就得到公式，f(k)=(f(k-1)+n)%k，如果k=1那么一定是0，所以可以利用1的特殊来建立函数，1可推2，2可推3，依此类推得到最后的答案。

 

#include <iostream>

using namespace std;
int n,k;
int f()
{
    int s=0;
    for(int i=2;i<=k;i++)
        s=(s+n)%i;
    return s+1;
}
int main()
{
    while(cin>>k>>n)
    {
        cout<<f()<<endl;

    }

    return 0;
}