什么是约瑟夫问题，约瑟夫问题是据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到留下一个人都自杀身亡为止。
解决这个问题，有多少种方法。
①最常用的方法是使用循环链表的解决。首先， 将这39 个犹太人构成一个循环链表，每个犹太人等同与一个结点，这个结点有后继结点相连，最后的结点与第一个结点相连。我实现的思路如下所示：
结点
翻译成源代码如下：
public class Node
{
private Node preNode;
private Node nextNode;
private int id;
private uint password;
public Node PreNode
{
get {
return preNode;
}
set {
preNode = value;
}
}
public Node NextNode {
get {
return nextNode;
}
set {
nextNode = value;
}
}
public int ID
{
get {
return id;
}
set {
id = value;
}
}
public uint Password
{
get {
return password;
}
set {
password = value;
}
}
}循环链表
翻译成源代码如下：
private Node firstNode = null;
private Node lastNode=null;
private Node nextNode = null;
private int count = 0;
public int Count
{
get {
return count;
}
set {
count = value;
}
}
public Circle()
{
}
public void Add(int id,uint password)
{
count++;
Node node = new Node();
node.ID = id;
node.Password = password;
this.Add(node);
}
public void Add(int id)
{
count++;
Node node = new Node();
node.ID = id;
this.Add(node);
}
private void Add(Node node)
{
if (firstNode == null)
{
firstNode = node;
lastNode = firstNode;
lastNode.NextNode = firstNode;
lastNode.PreNode = firstNode;
firstNode.NextNode = lastNode;
firstNode.PreNode = lastNode;
}
else
{
lastNode.NextNode = node;
node.PreNode = lastNode;
node.NextNode = firstNode;
firstNode.PreNode = node;
lastNode = node;
}
}
public Node NextNode()
{
Node node=new Node();
if (nextNode == null)
{
node = firstNode;
nextNode = firstNode.NextNode;
}
else
{
node = nextNode;
nextNode = node.NextNode;
}
return node;
}
public void RemoveNode(Node node)
{
count--;
Node _preNode = node.PreNode;
Node _nextNode = node.NextNode;
_preNode.NextNode = _nextNode;
_nextNode.PreNode = _preNode;
}把每个循环链表初始化，相应的源代码如下：
List<Node> outList = new List<Node>();
int index = 0;
int n = 7;
uint m = 20;
List<Node> nodeList = new List<Node>();
Node nd = new Node();
nd.ID = 1;
nd.Password = 3;
nodeList.Add(nd);
nd = new Circle.Node();
nd.ID = 2;
nd.Password = 1;
nodeList.Add(nd);
nd = new Circle.Node();
nd.ID = 3;
nd.Password = 7;
nodeList.Add(nd);
nd = new Circle.Node();
nd.ID = 4;
nd.Password = 2;
nodeList.Add(nd);
nd = new Circle.Node();
nd.ID = 5;
nd.Password = 4;
nodeList.Add(nd);
nd = new Circle.Node();
nd.ID = 6;
nd.Password = 8;
nodeList.Add(nd);
nd = new Circle.Node();
nd.ID = 7;
nd.Password = 4;
nodeList.Add(nd);
Circle c = new Circle();
foreach (Node node in nodeList)
{
c.Add(node.ID, node.Password);
}这是把所有的数据添加到泛型数组中。
在进行点名，出列。相应的源代码如下：
while (c.Count > 0)
{
index++;
nd = c.NextNode();
if (index == m)
{
c.RemoveNode(nd);
outList.Add(nd);
index = 0;
m = nd.Password;
}
}也是放入新的泛型数组中去。
把所显示的结果最终显示的源代码：
foreach (Circle.Node node in outList)
{
Console.WriteLine(node.ID);
}
最终运行的结果如下：
②基于位图算法的思想，
这里做法是建立一个数组来存储相应的数据，建立一个布尔变量来编辑是不是是不是进行了出列的标志，没出列一次，把相应的布尔的变量就置为假，一次循环操作，直到满足题意。这就基本思路，相应的流程图如下：
那实现的源代码就非常简单了，①对数据进行赋值的数组，一个布尔变量标记的数组。②判断布尔变量只有一个为真的方法。③依次报数，当报到相应的数字就进行了出列。④相应的索引大于数列的总长度又归零，直到布尔数组中一个为真的方法。源代码如下：
public static bool CheckArray(bool[] array)
{
int temp = 0;
for (int i = 0; i < array.Length; i++)
{
if (array[i])
{
temp++;
}
}
return temp == 1;
}
int[] array = new int[M];
;
bool[] blarray = new bool[M];
for (int i = 0; i < M; i++)
{
array[i] = (i + 1);
blarray[i] = true;
}
int count = 0;
int index = 0;
while (!CheckArray(blarray))
{
if (blarray[index])
{
count++;
}
if (count == N)
{
Console.WriteLine("数字" + array[index] + "出列");
count = 0;
blarray[index] = false;
}
index++;
if (index == M)
{
index = 0;
}
}运行结果如下：
两种方法互有千秋。比较如下：
2
这就是我对约瑟夫环问题的一点点心得，请大家多多指教。
协后感，不要看这个算法，我以前在做一个callcenter的项目时候，也是完全依据这个算法解决的问题，在做一个操作系统调度的时候，也是这个思想.所以，他的实用价值蛮大，所以像腾讯,华为,度娘面试的时候也经常考这个试题或者基于这个试题的变种。
