约瑟夫问题:M个人围成一圈,从第一个人开始依次从1到N循环报数,每当报数为N时此人出圈,直到剩一人为止

2020-05-10 教育 140阅读

此题可用数学方法求解。


设有n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数    (用数学方法解的时候需要注意应当从0开始编号,因为取余会取到0解。)


实质是一个递推,n个人中最终留下来的序号与n-1个人中留下来的人的序号有一个递推关系式。


假设除去第k个人,则


0, 1, 2, 3, ..., k-2, k-1, k, ..., n-1          // 原始序列 (1)


0, 1, 2, 3, ..., k-2,      , k, ..., n-1      // 除去第k人,即除去序号为k-1的人   (2)


k, k+1, ..., n-1,    0,    1,        ..., k-2// 以序号k为起始,从k开始报0  (3)


0, 1,     ..., n-k-1, n-k, n-k+1, ..., n-2   // 作编号转换,此时队列为n-1人  (4)


变换后就完完全全成为了(n-1)个人报数的子问题,注意(1)式和(4)式,是同一个问题,不同的仅仅是人数。比较(4)和(3),不难看出,0+k=k, 1+k=k+1, ... ,(3)式中'0'后面的数字,((n-3)+k)%n=k-3,((n-2)+k)%n=k-2, 对于(3)式中'0'前面的数字,由于比n小,也可看作(0+k)%n=k,  (1+k)%n=k+1,  故可得出规律:


设(3)中某一数为x' , (4)中对应的数为x,则有:x'=(x+k)%n.


设x为最终留下的人序号时,队列只剩下1人时,显然x=0; 此时可向前回溯至2人时x对应的序号,3人时x对应的序号……直至n人时x的序号,即为所求。


递归法表示如下:

#include 
int main()
{
    int M,N,s=0;
    scanf("%d%d",&M,&N);
    for (int i=2;i<=M;++i)
        s=(s+N)%i;
    printf("%d\n",s+1);
    return 0;
}
声明:你问我答网所有作品(图文、音视频)均由用户自行上传分享,仅供网友学习交流。若您的权利被侵害,请联系fangmu6661024@163.com