有一段时间没学习算法了，最近在学习一些常见的算法，约瑟夫问题是这样的：
15个教徒与15个非教徒在深海遇险，必须将一半的人投入大海，其余的人才能幸免于难，于是想到一个方法，30个人围成一圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环直到余15个人为止，问怎么样排法，才能使每次投入大海的都是非教徒？
//链表类
class CircleLinkedList
{
//元素个数
private int count;
//尾指针
private Node tail;
//当前节点的前节点
private Node CurrPrev;
//增加元素
public void Add(object value)
{
Node newNode = new Node(value);
if (tail == null)
{//链表为空
tail = newNode;
tail.next = newNode;
CurrPrev = newNode;
}
else
{//链表不为空，把元素增加到链表结尾
newNode.next = tail.next;
tail.next = newNode;
if (CurrPrev == tail)
{
CurrPrev = newNode;
}
tail = newNode;
}
count++;
}
//删除当前元素
public void RemoveCurrNode()
{
//为null代表为空表
if (tail == null)
{
throw new NullReferenceException("集合中没有任何元素！");
}
else if (count == 1)
{
tail = null;
CurrPrev = null;
}
else
{
if (CurrPrev.next == tail)
{
tail = CurrPrev;
}
CurrPrev.next = CurrPrev.next.next;
}
count--;
}
//当前节点移动步数
public void Move(int step)
{
if (step < 0)
{
throw new ArgumentOutOfRangeException("step", "移动步数不可为负数！");
}
if (tail == null)
{
throw new NullReferenceException("链表为空！");
}
for (int i = 0; i < step; i++)
{
CurrPrev = CurrPrev.next;
}
}
//获得当前节点
public object Current
{
get { return CurrPrev.next.item; }
}
public override string ToString()
{
if (tail == null)
{
return string.Empty;
}
string s = "";
Node temp = tail.next;
for (int i = 0; i < count; i++)
{
s += temp.ToString() + " ";
temp = temp.next;
}
return s;
}
public int Count
{
get { return count; }
}
private class Node
{
public Node(object value)
{
item = value;
}
//放置数据
public object item;
public CircleLinkedList.Node next;
public override string ToString()
{
return item.ToString();
}
}
}
//调用方法
private void testCircleLinkedList()
{
CircleLinkedList lst = new CircleLinkedList();
string s = string.Empty;
//Console.Write("请输入总数：");
//int count = Convert.ToInt32(Console.ReadLine());
int count = 30;
//Console.WriteLine("请输入每次要报到几!");
//int m = Convert.ToInt32(Console.ReadLine());
int m = 9;
Console.WriteLine("报数开始~");
for (int i = 1; i <= count; i++)
{//构建循环列表
lst.Add(i);
}
Console.WriteLine(lst.ToString());
while (lst.Count > 15)
{
lst.Move(m-1);
s += lst.Current.ToString() + " ";
lst.RemoveCurrNode();//把报数的人扔入大海
// Console.WriteLine("剩余的人为： "+lst.ToString());
Console.WriteLine(lst.Current + "开始报数！");
}
Console.WriteLine("被扔入大海的人为：" + s);
Console.ReadLine();
}
运行结果：
算法代码取自网络。