约瑟夫环问题

编号1~n
报数 k 的人死
某一阶段的人数 i
特殊报数 m

思路

先编号n-1来算，再逆推，记得结果都要+1

• f[1] = 0，
• f[i] = (f[i-1] + k) % i

变形

1. 先杀死第m个人，再报数k的人死。
   poj 3517 And Then There Was One

#include <iostream>
using namespace std;
int main()
{
    int n, k, m;
    int ans;
    while(cin >> n >> k >> m && (n || m || k))
    {
        ans = 0;
        for(int i=2; i<=n-1; i++)
            ans = (ans+k)%i;
        ans = (ans + m)%n; //最后换成+m
        cout << ans + 1 << endl;
    }
    return 0;
}

2. 第1轮，报1的人死，
   第2轮，报2的人死，
   ……
   ……
   第n-1轮，报n-1的人死。
   hdu 5643 King's Game

#include <iostream>
using namespace std;

int main()
{
    int t, n;
    int ans;
    while(cin >> t)
    {
        while(t--)
        {
            cin >> n;
            ans =0;
            for(int i=2, j=n-1; i<=n; i++,j--)
                ans = (ans + j)%i; //换成+j
            cout << ans+1 << endl;
        }
    }
    return 0;
}

3. 编号1~n，要保留编号为x的人，求k的值（暴力求解）
   ZOJ1088——System Overload

#include <iostream>
using namespace std;
//第一轮第m死，之后为了保留x，求k的最小值
int  joseph(int n, int k)
{
    int ans =0;
    for(int i=2; i<n; i++)
        ans = (ans+k)%i;
    ans = (ans + 1)%n;
    return ans+1;
}

int main()
{
    int n, i;
    while(cin >> n && n)
    {
        for(i=1; ; i++)  //没有限制条件，可以大于n！！！
        {
            if(joseph(n, i) == 2)  //保留第2个
                break;
        }
        cout << i << endl;
    }
    return 0;
}