背景故事：

約瑟夫問題是個(gè)有名的問題：N個(gè)人圍成一圈，從第一個(gè)開始報(bào)數(shù)，第M個(gè)將被殺掉，最后剩下一個(gè)，其余人都將被殺掉。例如N=6，M=5，被殺掉的人的序號為5，4，6，2，3。最后剩下1號。

類似的問題：

一堆猴子都有編號，編號是1，2，3 ...m ,這群猴子（m個(gè)）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第N個(gè)，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。

程序代碼如下：
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; //記錄元素個(gè)數(shù)； public int Count { get {return count ;} } private Node tail; //尾指針； public object Current //指示當(dāng)前節(jié)點(diǎn)中的值； { get {return currentPre.next.item;} } private Node currentPre; //使用前驅(qū)結(jié)點(diǎn)來標(biāo)示當(dāng)前節(jié)點(diǎn)； //在鏈表尾部添加元素； public void Add(object values) { Node newNode=new Node (values); if(tail==null) //如果鏈表為空，則新節(jié)點(diǎn)既是頭指針，又是尾指針； { tail=newNode; tail.next=newNode ; currentPre=newNode; } else { newNode.next=tail.next; tail.next =newNode ; if(currentPre ==tail) { currentPre =newNode; } tail =newNode ; //把尾指針指向新節(jié)點(diǎn)； } count ++; } //刪除當(dāng)前節(jié)點(diǎn)； 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 --; } //讓當(dāng)前節(jié)點(diǎn)向前移動(dòng)指定的步數(shù)； public void Move(int step) { if(step <0) { throw new ArgumentOutOfRangeException("移動(dòng)步數(shù)不能小于0！"); } if(tail ==null ) { throw new NullReferenceException ("集合中沒有任何元素！"); } for(int i=0;i<step; i++) { currentPre=currentPre.next ; } } //打印整個(gè)鏈表；（僅用于測試） 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 ("請輸入總?cè)藬?shù)："); int count=int.Parse (Console.ReadLine()); Console.WriteLine ("請輸入間隔數(shù)字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開始數(shù)數(shù)的人："+clist .Current ); } Console .WriteLine ("/r/n出隊(duì)順序："+s+clist.Current); } }
運(yùn)行結(jié)果：

C#單向循環(huán)列表 解決 約瑟夫問題