Josephus（约瑟夫环）问题

122 阅读 0 评论 81 点赞

我是靠谱客的博主整齐毛衣，这篇文章主要介绍Josephus（约瑟夫环）问题，现在分享给大家，希望可以做个参考。

Josephus问题是说，一群小孩围成一圈，任意假定一个数m，从第一个小孩起，顺时针方向数，每数到第m个小孩时，该小孩便离开。小孩不断离开，圈子不断缩小。最后，剩下的一个小孩便是胜利者。

题目要求：顺序打印离开的小孩及最后的胜利者。

分析：为了解决这个问题，可以定义一个数组a，元素的个数就是小孩的个数。每个数组元素初始赋一个不为0的值作为小孩的序号，当小孩离开时，修改对应的数组元素的值为“0”来标识小孩的离开。另外，因为小孩是围成圈的，在数小孩时，当数到数组尾的时候，下一个数组元素下标值通过“加1求模”运算就可以算得为0，从而回到数组首部。

代码如下（VS2013）

复制代码

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
52
53
54
55
56
57
#include "stdafx.h"
#include <iostream>
#define N 6
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int m;
//每次数到第m个小孩，就让其离开
int a[N];
//小孩数组
int i, j, k;
//数组下标标志、数数计数变量、离开小孩计数变量k
int s;
//游戏进行和结束的标志变量
i = -1;
k = 1;
s = 1;
cout << "请输入每次数到几时，小孩离开：" << endl;
cin >> m;
for (int i = 0; i < N; i++)
//给小孩编号
a[i] = i + 1;
cout << "小孩的编号为：";
for (int i = 0; i < N; i++)
//按顺序打印初始化小孩编号
cout << a[i] << " ";
cout << "nn";
/*开始数数*/
cout << "小孩依次离开的编号:";
while (s)
{
j = 0;
while (j < m)
//数小孩个数不到m,就循环
{
i = (i + 1) % N;
//对下标加1求模
if (a[i] != 0)
j++;
}
if (k == N)
s = 0;
else
{
cout << a[i] << " ";
//打印离开小孩的编号
a[i] = 0;
//标示小孩已经离开
++k;
//处理下一个离开的小孩
}
}
cout << "nn";
cout << "第" << a[i] << "个小孩获胜" << endl;
cout << endl;
return 0;
}