约瑟夫斯问题的快速入门及例题展示

创作时间:

作者:

@小白创作中心

约瑟夫斯问题的快速入门及例题展示

引用

CSDN

https://m.blog.csdn.net/m0_75262255/article/details/139187507

约瑟夫斯问题简介

约瑟夫斯问题，又称约瑟夫环，通常运用递归或循环进行求解，一般指的是给定总人数sum和每次排除的步长step，来确定按照规则来求得最终的“幸存者”。

起源

在罗马军队围攻下，约瑟夫斯和他的40名士兵被困在一个洞穴中，他们决定通过一种方式来决定谁将被牺牲，以期至少让一部分人能够生存。他们围成一个圈，从某个人开始报数，每数到某个固定的数（比如每数到第3个人），那个人就会被排除（在这里是被杀掉或退出圈子）。然后从下一个人继续开始报数，依此类推，直到只剩下最后一个人为止，这个人就是最终的幸存者。

原理

我们假设总人数为10，每次的步长为3，从编号为1号的人开始循环报数，报到3的人淘汰，最终剩下的一个人获胜，我们可以通过不断的循环得到下面的思路和图解：

从1号开始报数，1、2、3，3号淘汰，剩余1，2，4，5，6，7，8，9，10。
从4号开始报数，4、5、6，6号淘汰，剩余1，2，4，5，7，8，9，10。
从7号开始报数，7、8、9，9号淘汰，剩余1，2，4，5，7，8，10。
从10号开始报数，10、1、2，2号淘汰，剩余1，4，5，7，8，10。
由于3号已经出局，所以我们从4号开始，4、5、7，7号淘汰，剩余1，4，5，8，10。
从8号开始报数，8、10、1，1号淘汰，剩余4，5，8，10。
从4号开始报数，4、5、8，8号淘汰，剩余4，5，10。
从10号开始报数，10、4、5，5号淘汰，剩余4，10。
从10号开始报数（很巧，又是10），10、4、10，10号淘汰，剩余4，4号为最终的幸存者。

图解如下：

约瑟夫斯问题的例题

接下来我们来看看约瑟夫斯问题的例题

例题一：分苹果

第一道题出自某校OJ，大致题意是这样的：一个学校的老师想要分苹果，但是分到最后发现苹果多出两个，因此老师想要借助“约瑟夫斯问题”的思路找出幸运儿。

现在n个小朋友围成一圈，编号从1-n，第一个人从1数起，数到7的那个人就被淘汰出局，接下来的人又从1数起，数到7再次被淘汰（如果人数不满7个就循环着数）……最后剩下的一个人就是赢得苹果的那位“幸运儿”。其中n不超过1000。

分析

这道题就是约瑟夫斯问题的应用，我们可以模拟上面的循环对问题进行求解。

首先我们需要f[1009]用来存储每个位置上的小朋友编号，初始时f[i]=i+1，表示从1到k编号。
n稍后会被赋值为k，表示剩余小朋友数量；i和j用于循环控制，count用于计数，ans存储最后的幸存者编号。
将输入的总人数赋值给n，用于动态跟踪剩余人数。
外层的while(n>1)循环持续到只剩下一个小朋友。
内部首先检查f[i]是否不为0，即该位置是否有小朋友。如果是，则count++。
当count达到7时，执行淘汰操作：f[i]=0表示该位置的小朋友被淘汰，count=0重置计数器，n--;减少剩余人数。
移动到下一个位置，可以用if(i==k)i=0确保循环回到数组开头，形成闭环。
在循环结束后，查找数组中不为0的元素，将其值赋给ans作为最终的幸存者编号并返回结果。

因此根据分析，我们可以轻松完成对问题的解答。

代码

是不是期待已久了？代码如下：

int jos(int k) {
    int f[1009],j=1,i,count = 0,ans = 0,n;
    n=k;
    for(int i=0;i<k;i++)f[i]=i+1; i=0;
    while(n>1) {
        if(f[i]!=0)count++;
        if(count==7) {
            f[i] = 0;
            count = 0;
            n--;
        }
        i++;
        if(i==k)i=0;
    }
    for(i=0;i<k;i++) if(f[i]!=0)ans = f[i];
    return ans;
}