Josephus Problem （约瑟夫环数学解法）

       约瑟夫环是一个非常经典的数学问题，n个人围成一圈，从1开始报数，每当有人报到m时，他被淘汰，下一个人继续从1开始报数，问最后的获胜者是谁？        有一种很经典的算法是用链表/数组来模拟整个游戏的过程，但是当n , m 都很大的时候这个方法就显然行不通了。有没有更便捷的方式来解决这个问题呢？       我们可以从数学的角度来分析一下这个问题。首先我们通过思考可以得到一个很显然的结论，n个人时的获胜者和这n个人淘汰掉一个人继续游戏下的获胜者一定是同一个人。（有点像废话...）所以如果我们能确定 n-1个人时候的获胜者也就可以得到 n 个人时候的情况，因为两者的排列存在一种对应关系。 考虑n = 6 m = 3的情况        0 1 2 3 4 5        3 4 5 0 1 2 可以很明显的看出上下两行存在着 + m 模 n的对应关系。        这样这个问题就可以通过递推的方式解决了， f[i] 为 场上有 i 个人时，最后获胜者的编号（从零开始）。        那么就存在着这样的递推式   f[i] = ( f[i-1] + k ) % i   我们还可以知道 f[1] = 0 所以可以通过这个递推式轻松的得到答案啦~

代码实现：（HDU 2925）

/*
    @Author: wchhlbt
    @Date:   2017/3/9
*/
#include <bits/stdc++.h>
#define Fori(x) for(int i=0;i<x;i++)
#define Forj(x) for(int j=0;j<x;j++)
#define maxn 1005
#define inf 0x3f3f3f3f
#define ONES(x) __builtin_popcount(x)
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;

const double eps =1e-8;
const int mod = 10007;
const double PI = acos(-1.0);

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int main()
{
    int n,d;
    while(cin>>n>>d && n+d){
        int ans = 0;
        for(int i = 2; i<=n; i++)
            ans = (ans+d)%i;
        cout << n << " " << d << " " << ans+1 << endl;
    }
    return 0;
}
           

这个问题还可以进一步优化，当n非常大，k却很小的时候，我们甚至没有必要遍历所有的 i ，考虑这个式子ans = (ans+d)%i ， 当 i已经很大了的时候可能 ans + k*d < i , 这种情况下我们完全没有必要一步一步的去模拟，因为这个数值始终没有变化，所以可以一次性跳跃若干的值达到优化算法的目的。

AC代码：（HDU 3089）

/*
    @Author: wchhlbt
    @Date:   2017/3/14
*/
#include <bits/stdc++.h>


#define Fori(x) for(int i=0;i<x;i++)
#define Forj(x) for(int j=0;j<x;j++)
#define maxn 1005
#define inf 0x3f3f3f3f
#define ONES(x) __builtin_popcount(x)
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;

const double eps =1e-8;
const int mod = 10007;
const double PI = acos(-1.0);

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int main()
{
    ll n,k;
    while(scanf("%I64d%I64d",&n,&k)!=EOF){
        if(k==1){
            printf("%I64d\n",n);
            continue;
        }
        ll ans = 0;
        for(ll i = 2; i<=n; ){
            if(ans+k<i){
                ll num;
                if((i-1-ans)%(k-1)==0)
                    num = (i-1-ans)/(k-1) - 1;
                else
                    num = (i-1-ans)/(k-1);
                if(i+num>n){
                    ans = (ans + (n+1-i)*k)%n;//因为目前ans保存的是只有i-1个人时的幸存编号
                    break;
                }
                i += num;
                ans = (ans + num*k)%i;
            }
            else{
                ans = (ans+k)%i;
                i++;
            }
        }
        printf("%I64d\n",ans+1);
    }
    return 0;
}