链表相关问题

给一个用链表找皇的程序，就是有N个人一圈循环报数，报着3的出去，剩下的那个就是皇。

这是一个Josephus问题，以前写过一个类似的代码，如下：

Josephus问题是古代一个著名的数学难题，有一个故事说Josephus是一群被罗马人

抓获的犹太人中的一个，为了不被奴役，他们选择了自杀，他们派成一个圆圈，从

某个人开始，沿着圈报数，每报第N个人就离开圆圈去自杀，Josephus不想死，所

以他制定了规则，以使成为最后一个离开圆圈的人。如果是N个人，他在第M个位置

，他应该让他们用什么数来进行报数呢？

现在简单一下问题，如果是20个人，报数5的话，谁在最后呢？如果实现了该功能

，那么N个人，在第M个位置，需要报什么书可以成为最后一个人的问题也就等于OK

了。

下面是代码实现（如果是20个人，报数5的话，谁在最后呢？）

队列请参照 http://hnlzpsh128.itpub.net/post/18675/244715

using System;
using System.Collections.Generic;
using System.Text;

namespace StructTest
{
/// <summary>
///
/// AoiUmi的Josehpus问题DEMO
///
/// Create 20061226
///
/// personCount个人围成一个圈，从一个人开始报数(1,2,3.....)，
/// 报到personNo的人出线，剩下的人组成新圈，
/// 从出线的这个人的下个人再开始报数(1,2,3.....)
/// 继续。直到圈剩下1个人为止
/// </summary>
class Josehpus
{
//总共有personCount人
private int personCount = 7;
//报数personNo的人出线
private int personNo = 4;
private Queue q = new Queue();

public Josehpus(int count,int no)
{
personCount = count;
personNo = no;
}
public void CreateQueen()
{
for (int i = 0; i < personCount; i++)
q.InsertNode(new Node(null, null, i,"No" + (i+1).ToString()));

q.QueenClose();
//下面语句测试用
//q.ViewQueenName();
//Console.Read();
}
//开始，出线的人，按顺序输入
public void DoJosehpus()
{
//终止重复操作
//条件是队列中只剩下1个人
if (q.Root.PreNode.NextNode.Equals(q.Root.PreNode))
{
Console.WriteLine("最后留下来的人名字：" + q.Root.PreNode.Name);
return;
}
//结点中记录报数的NodeValue 需要清空
//为了不影响下轮报数
ClearQueenData();

int j = 1;//从1开始报数
for (Node i = q.Root.PreNode; true; i = i.NextNode)
{
i.NodeValue = j++;
//处理报了no数的人
if (i.NodeValue.Equals(personNo))
{
//出线
q.DeleteNode(i.NodeValue);
//ViewQueenData();
//下次从他的下个人开始报数
InitRoot(i.NextNode);
//显示出线的人的姓名
Console.WriteLine(" " + i.Name + " ");

//重复
DoJosehpus();
}
}
}
public void ClearQueenData()
{
for (Node i = q.Root.PreNode; i != q.Root.PreNode.PreNode; i = i.NextNode)
{
i.NodeValue = "";
}
}
//设置出线的下个人下次开始报数
public void InitRoot(Node n)
{
q.Root.PreNode = n;
q.Root.NextNode = q.Root.PreNode.PreNode;
}
}
}