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