[算法] 约瑟夫问题

约瑟夫问题描述

约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3,1。

递归思想解决约瑟夫问题

d4shman

初始情况: 0, 1, 2 ……n-2, n-1 (共n个人)
第一个人(编号一定是(m-1)%n,设之为(k-1) ,读者可以分m=n的情况分别试下,就可以得出结论) 出列之后,
剩下的n-1个人组成了一个新的约瑟夫环(以编号为k==m%n的人开始):
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ..., k-3, k-2

现在我们把他们的编号做一下转换:

1
2
3
4
5
6
7
8
x'    --> x
k     --> 0
k+1   --> 1
k+2   --> 2
...
...
k-2   --> n-2
k-1   --> n-1

变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:例如x是最终的胜利者,那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗!

1
2
3
4
5
6
7
x   ->  x'?(这正是从n-1时的结果反过来推n个人时的编号!)
0 -> k
1 -> k+1
2 -> k+2
...
...
n-2 -> k-2

变回去的公式  x’=(x+k)%n

那么,如何知道(n-1)个人报数的问题的解?只要知道(n-2)个人的解就行了。(n-2)个人的解呢?只要知道(n-3)的情况就可以了 —- 这显然就是一个递归问题:
令f[i]表示i个人玩游戏报m退出最后胜利者的编号,最后的结果就是f[n];

递推公式

1
2
f[1] = 0;
f[i] = (f[i-1] + k ) % i = (f[i-1] + m % i) % i = (f[i-1] + m) % i ;  (i>1)

算法实现

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;

int josephus(int n, int m) {
if(n == 1) {
return 0;
}
else {
return (josephus(n-1, m) + m) % n;
}
}
int main() {
int n, m;
while (cin >> n) {
if (!n) {
break;
}
cin >> m;
int result = josephus(n, m);
cou << ( result+1);
}
return 0;
}

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;

int main() {
int n, m, i, result;
while (cin >> n) {
if (!n) {
break;
}
cin >> m;
result = 0;
for (i = 2; i <= n; i++) {
result = (result + m) % i;
}
cou << (result + 1);
}
return 0;
}

约瑟夫问题的变种 - 圆桌问题

描述

圆桌上围坐着2n个人。其中n个人是好人,另外n个人是坏人。如果从第一个人开始数数,数到第m个人,则立即处死该人;然后从被处死的人之后开始数数,再将数到的第m个人处死……依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位,能使得在处死n个人之后,圆桌上围坐的剩余的n个人全是好人。*

输入

多组数据,每组数据输入:好人和坏人的人数n( <= 32767)、步长m( <= 32767);

输出

对于每一组数据,输出2n个大写字母,‘G’表示好人,‘B’表示坏人,50个字母为一行,不允许出现空白字符。相邻数据间留有一空行。

Sample Input

2 3
2 4

Sample Output

GBBG
BGGB

题解思路

  • step1 – 先模拟一遍在这个输入之下可能被杀的位置(用一个vector模拟这个圈–循环淘汰,使用一个int数组存储其位置)
  • step2 – 将坏人放到我们记录好会被杀死的位置

CODE

说明:
int vis[MAX] 用来记录好人坏人属性的数组
vector<int> v 用来模拟位置的内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int M = 32767 + 5;
const int g = 0, b = 1;

int vis[2 * M];


/*题解思路*/
//先模拟一遍在这个输入之下的情况,记录被杀之人的位置
//将坏人放上去

int main()
{
int n, m;
while (cin >> n >> m)
{ //n代表好人坏人给有多少个,m代表报数长度

memset(vis, g, sizeof(vis)); //先假定全是好人,0--好人;1--坏人
vector<int> v(2 * n); //输入n代表好人\坏人数;2n表示安排的位置刚好好人坏人都可以坐下

for (int i = 0; i < 2 * n; i++) //设置统一的下标
v[i] = i;

int no = 0; //该变量用于记录被杀之人的相对位置
for (int i = 0; i < n; i++) //此处循环n,表示杀死n个人
{
no = (no + m - 1) % v.size(); //开始记录被杀的位置编号(修改人员编号数组)
vis[v[no]] = b; //记录被杀的位置
v.erase(v.begin() + no); //杀死这个位置的人,但是不会影响报数
}

for (int i = 0; i < 2 * n; i++) //因为找到了被处决的位置,将坏人放在被处决的位置就可以了
{
if (i % 50 == 0 && i > 0) //分行--数量过多就分行显示
cout << endl;

if (vis[i] == g)
cout << 'G';
else
cout << 'B';
}

cout << endl << endl;
}
return 0;
}