约瑟夫环问题(数学解法)

约瑟夫环问题:每次从这个圆圈中删除第 m 个数字(第一个为当前数字本身,第二个为当前数字的下一个数字)。当一个数字删除后,从被删除数字的下一个继续删除第 m 个数字。求出在这个圆圈中剩下的最后一个数字。

据说之前,这些数字是死囚,能抽到最后一个的人能活着……

模拟的方法弱爆了,有递推公式的,假设有n个人,每轮第k个人被杀掉,递推公式如下:

如果想知道推导过程,可以看维基百科:"Josephus problem"

即初始sum=0,我们从i=2开始(i就是上面公式的n),每次另sum = (sum+m)%i即可。据说下面这货是动态规划的一种啊……

// N people, Delete mth
int josephus(int n, int m)
{
    int i;
    int sum = 0;
    for(i=2;i<=n;i++)
    {
        sum = (sum+m)%i;
    }
    return sum;
}

Leave a Reply

Your email address will not be published. Required fields are marked *