716
C#单向循环列表 解决 约瑟夫问题
背景故事：
约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。
类似的问题：
一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
程序代码如下：
using System ;
public class CircularLinkedList
{
private class Node
{
public Node (object value)
{
item=value;
}
public object item;
public CircularLinkedList .Node next;
public override string ToString()
{
return item.ToString();
}
}
private int count; //记录元素个数；
public int Count
{
get {return count ;}
}
private Node tail; //尾指针；
public object Current //指示当前节点中的值；
{
get {return currentPre.next.item;}
}
private Node currentPre; //使用前驱结点来标示当前节点；
//在链表尾部添加元素；
public void Add(object values)
{
Node newNode=new Node (values);
if(tail==null) //如果链表为空，则新节点既是头指针，又是尾指针；
{
tail=newNode;
tail.next=newNode ;
currentPre=newNode;
}
else
{
newNode.next=tail.next;
tail.next =newNode ;
if(currentPre ==tail)
{
currentPre =newNode;
}
tail =newNode ; //把尾指针指向新节点；
}
count ++;
}
//删除当前节点；
public void RemoveCurrentNode()
{
if(tail ==null )
{
throw new NullReferenceException ("集合中没有任何元素！");
}
else if(count ==1)
{
tail =null;
currentPre =null ;
}
else
{
if(currentPre .next ==tail)
{
tail=currentPre ;
}
currentPre.next=currentPre.next.next ;
}
count --;
}
//让当前节点向前移动指定的步数；
public void Move(int step)
{
if(step <0)
{
throw new ArgumentOutOfRangeException("移动步数不能小于0！");
}
if(tail ==null )
{
throw new NullReferenceException ("集合中没有任何元素！");
}
for(int i=0;i<step; i++)
{
currentPre=currentPre.next ;
}
}
//打印整个链表；（仅用于测试）
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;
}
}
class App
{
static void Main()
{
CircularLinkedList clist=new CircularLinkedList ();
string s=string.Empty;
Console.WriteLine ("请输入总人数：");
int count=int.Parse (Console.ReadLine());
Console.WriteLine ("请输入间隔数字M的值：");
int m=int.Parse (Console.ReadLine ());
Console.WriteLine("开始游戏：");
for(int i=1;i<count+1;i++)
{
clist .Add (i);
}
Console.WriteLine("所有人："+clist .ToString ()+"/n");
while (clist.Count>1)
{
clist .Move(m);
s+=clist.Current.ToString ()+" ";
Console .WriteLine ("出局的人："+clist.Current);
clist.RemoveCurrentNode ();
Console .WriteLine ("剩余的人："+clist .ToString ());
Console.WriteLine("/n开始数数的人："+clist .Current );
}
Console .WriteLine ("/r/n出队顺序："+s+clist.Current);
}
}
运行结果：
最后更新：2017-04-02 04:00:24