约瑟夫环问题
前言
约瑟夫环问题是一个很很经典的问题,问题的描述大概如下:$0,1, \dots ,n-1$这$n$个数字排成一个圆圈,从数字$0$开始,每次从这个圆圈里删除第$m$个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。
可以用队列来模拟或者是递推来解决这个问题。
玩游戏
$n$ 个小朋友围成一圈,玩数数游戏。
小朋友们按顺时针顺序,依次编号为 $1 \sim n$。
初始时,$1$ 号小朋友被指定为领头人。
游戏一共会行进 $k$ 轮。
在第 $i$ 轮中,领头人会从他的顺时针方向的下一个人开始,按顺时针顺序数 $a_{i}$ 个人。
其中,最后一个被领头人数到的人被淘汰出局,这也意味着该轮游戏结束。
出局者的顺时针方向的下一个人被指定为新领头人,引领新一轮游戏。
例如,假设当游戏即将开始第 $i$ 轮时,还剩下 $5$ 个小朋友,编号按顺时针顺序依次为 $8,10,13,14,16$,并且当前领头人为 $13$ 号小朋友,$a_{i}=12$,则第 $i$ 轮游戏结束后,最后一个被数到的小朋友为 $16$ 号小朋友,他将被淘汰出局,并且处于其下一位的第 $8$ 号小朋友将被指定为新领头人。
现在,请你求出每一轮次被淘汰的小朋友的编号。
输入格式
第一行包含两个整数 $n,k$。
第二行包含 $k$ 个整数 $a_{1},a_{2}, \dots ,a_{k}$。
输出格式
一行,$k$ 个整数,其中第 $i$ 个整数表示在第 $i$ 轮中被淘汰的小朋友的编号。
数据范围
前三个测试点满足 $2 \leq n \leq 10$。
所有测试点满足 $2 \leq n \leq 100$,$1 \leq k \leq n?1$,$1 \leq a_{i} \leq {10}^{9}$。
输入样例1:
1 7 5 2 10 4 11 4 1
输出样例1:
4 2 5 6 1
输入样例2:
3 2 2 5
输出样例2:
3 2
解题思路
数据范围比较小,所有可以直接开个队列来模拟。一开始先将$1,2, \dots, n$按顺序放到队列中,每次都从队头开始数,每数到一个数就把这个数放到队尾,因此队列就起到一个循环枚举的作用。当数完$k$个数后,此时队头的数就是要删除的数,把这个数从队头删除。
$a_{i}$的取值范围很大,但由于是环形的枚举,因此$a_{i}~mod~n$就可以去掉重复的循环枚举,为最终枚举的次数。因此时间复杂度为$O \left( n^{2} \right)$。
AC代码如下:
1 #include2 #include 3 #include 4 using namespace std; 5 6 queue<int> q; 7 8 int main() { 9 int n, m; 10 scanf("%d %d", &n, &m); 11 for (int i = 1; i <= n; i++) { 12 q.push(i); 13 } 14 15 while (m--) { 16 int val; 17 scanf("%d", &val); 18 val %= q.size(); 19 20 for (int i = 0; i < val; i++) { 21 q.push(q.front()); 22 q.pop(); 23 } 24 25 printf("%d ", q.front()); 26 q.pop(); 27 } 28 29 return 0; 30 }
如果$n$的数据范围很大,就需要用递推的做法了。
圆圈中最后剩下的数字
$0,1, \dots ,n?1$ 这 $n$ 个数字 $\left( {n>0} \right)$ 排成一个圆圈,从数字 $0$ 开始每次从这个圆圈里删除第 $m$ 个数字。
求出这个圆圈里剩下的最后一个数字。
数据范围
$1 \leq n,m \leq 4000$
样例
输入:n=5 , m=3 输出:3
解题思路
这题的数据范围用模拟也可以过,时间复杂度为$O \left( n^{2} \right)$。但下面讲递推的做法,时间复杂度为$O \left( n \right)$。
我们假设在这$n$个人中删除$n-1$个人后最终留下的人为$x$,这个人在长度为$n$的序列中的下标就是$x$。一开始在长度为$n$的序列中删除第$m$个人,如下图:
接下来进行第二次的删除操作,从被删除的下一个人开始,也就是下标为$m$开始继续数$m$个人然后删除。此时序列的长度变成了$n-1$,我们为这个环剩余的数字重新编号,使得开始数的那个数的下标为$0$,也就是$m$这个数的下标为$0$,顺时针往后的每个数下标都加$1$,直到$m-2$这个数时,下标为$n-2$,如下图(新的下标的颜色为红色):
可以发现新的下标编号加上$m$再模$n$就是将原来的下标编号。原来在长度为$n$的序列中,$x$所在的下标重新编号后变成了$y$,即$x = \left( {y+m} \right) \%n$。$x$位置和$y$位置上的数是同一个(就是最终留下来的那个数),只是下标的编号不一样。
所以我们发现,如果求出了在长度为$n-1$的序列中从第$0$个人开始,每次数$m$个人将其删掉,最终留下的那个人的下标编号(在长度为$n-1$的序列中的下标),那么就可以反推回这个最终留下的人在长度为$n$的序列中的下标(加$m$模$n$)。
我们用$f \left( {n,m} \right)$来表示在$n$个人中,每次从被删掉的下一个人开始数$m$个人将其删除(一开始从$0$开始数),最终留下的那个人的编号。
第一次删掉一个人后,序列长度变成了$n-1$,并且重新进行编号,因此在长度为$n-1$的序列中,最后留下的人的编号就是$f \left( {n-1,m} \right)$。
当我们得到新编号后,会发现与旧编号有个映射关系,也就是新的编号加上$m$模$n$后,就得到旧编号。
现在留下的人在$n-1$的序列中的新编号是$f \left( {n-1,m} \right)$,因此转换为在$n$的序列中的旧编号就是$f \left( {n,m} \right) = \left( {f \left( {n-1,m} \right) + m} \right) \% n$。
因此递推公式为($m$可以省略):$$f \left( {i,m} \right) = \left( {f \left( {i-1,m} \right) + m} \right) \% i$$
所以我们找到了$n$和$n-1$的递推关系,其中边界是只有一个人,此时编号为$0$,即$f \left( 1 \right) = 0$。
我们可以用递归或循环递推的写法来写。
当数据规模不大的时候可以用递归,AC代码如下:
1 class Solution { 2 public: 3 int lastRemaining(int n, int m){ 4 if (n == 1) return 0; 5 return (lastRemaining(n - 1, m) + m) % n; 6 } 7 };
循环递推写法的AC代码如下:
1 class Solution { 2 public: 3 int lastRemaining(int n, int m){ 4 int ret = 0; // f(1) = 0 5 for (int i = 2; i <= n; i++) { // 从2开始,一直求到n 6 ret = (ret + m) % i; // f(i) = (f(i-1) + m) % i 7 } 8 return ret; 9 } 10 };
下面是一道变形题目。
招聘
某公司招聘,有 $n$ 个人入围,HR在黑板上依次写下 $m$ 个正整数 $A_{1},A_{2}, \dots, A_{m}$,然后这 $n$ 个人围成一个圈,并按照顺时针顺序为他们编号 $0,1,2, \dots, n?1$。
录取规则是:
第一轮从 $0$ 号的人开始,取用黑板上的第 $1$ 个数字,也就是 $A_{1}$。
黑板上的数字按次序循环使用,即如果某轮用了第 $k$ 个,如果 $k 每一轮按照黑板上的次序取用到一个数字 $A_{x}$,淘汰掉从当前轮到的人开始按照顺时针顺序数到的第 $A_{x}$ 个人。 下一轮开始时轮到的人即为被淘汰掉的人的顺时针顺序下一个人,被淘汰的人直接回家,所以不会被后续轮次计数时数到。 经过 $n?1$ 轮后,剩下的最后 $1$ 人被录取,所以最后被录取的人的编号与 $\left( {n,m,A_{1},A_{2}, \dots, A_{m}} \right)$ 相关。 输入包含多组测试数据。 第一行包含整数 $T$,表示共有 $T$ 组测试数据。 接下来 $T$ 行,每行包含若干个整数,依次存放 $n,m,A_{1},A_{2}, \dots, A_{m}$,表示一组数据。 输出共 $T$ 行,每行对应相应的那组数据确定的录取之人的编号。 $0 样例里只有 $1$ 组测试数据,说的是有 $4$ 人入围(编号 $0 \sim 3$)。 黑板上依次写下 $2$ 个数字:$3$、$1$,那么: 第一轮:当前轮到 $0$ 号,数到数字 $3$,顺时针数第 $3$ 个人是 $2$ 号,所以淘汰 $2$ 号,下一轮从 $3$ 号开始,目前剩余:$0$、$1$、$3$; 第二轮:当前数到 $3$ 号,取到数字 $1$,顺时针数第 $1$ 个人是 $3$ 号,所以淘汰 $3$ 号,下一轮从 $0$ 号开始,目前剩余:$0$、$1$; 第三轮:当前轮到 $0$ 号,循环取到数字 $3$,顺时针数第 $3$ 个人是 $0$ 号,所以淘汰 $0$ 号,最后只剩下 $1$ 号,所以录取 $1$ 号,输出 $1$; 可以发现在这一题中,每次数的人的个数不再是一个固定的数$m$了。但递推公式还是成立的,只需要把$m$改为相应的从$i$变到$i-1$要数的那个数$a \left[ {\left( n-i \right) \% m} \right]$就可以了。 $a \left[ {\left( n-i \right) \% m} \right]$表示,如果要从长度为$i$的序列中删除一个数,那么应该数第$n-i $个数,即$a \left[ n-i \right]$,因为数组$a$的数是循环取的,因此要模上数组$a$的长度$m$。 递推公式就变成了$$f \left( i \right) = \left( {f \left( {i-1} \right) + a \left[ {\left( n-i \right) \% m} \right]} \right) \% i$$ 由于$n$最大取到${10}^{7}$,递归来做肯定会暴栈的,因此必须要用循环。 AC代码如下: AcWing 4400. 玩游戏(AcWing杯 - 周赛):https://www.acwing.com/video/3826/ AcWing 82. 圆圈中最后剩下的数字:https://www.acwing.com/video/205/ AcWing 1455. 招聘:https://www.acwing.com/solution/content/18760/输入格式
输出格式
数据范围
输入样例:
1
4 2 3 1
输出样例:
1
样例解释
解题思路
1 #include
参考资料