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); } }
运行结果：

C#单向循环列表 解决 约瑟夫问题