POJ 1012 Joseph

http://poj.org/problem?id=1012

题意：约瑟夫问题。前k个为好人，后k个为坏人，求最小m值，使得所有的坏人在第一个好人死前全部死完。

思路：首先引入一下约瑟夫环的递推公式：

        设有n个人（0,...,n-1），数m，则第i轮出局的人为f(i)=(f(i-1)+m-1)%(n-i+1),f(0)=0; （当前序列编号为0~(n-i));

        运用这个公式的话，只需要枚举m就可以了。由于k不大，可以直接打表。

#include<iostream>
#include<string>
#include<cstring>
using namespace std;


int main()
{
    //freopen("D:\txt.txt", "r", stdin);
    int k,n,s;
    int a[15], b[15];
    for (int k = 1; k < 14; k++)
    {
        memset(a, 0, sizeof(a));  //记录第几次出局的人数
        n = 2 * k;  //总人数
        int m = 1;  //枚举m值
        for (int j = 1; j <= k; j++)
        {
            a[j] = (a[j - 1] + m - 1) % (n - j + 1);
            if (a[j] < k)
            {
                j = 0;
                m++;
            }
        }
        b[k] = m;
    }
    while (cin>>s && s)
        cout << b[s] << endl;
    return 0;
}