猴子选大王（约瑟夫环问题）的OO解法

问题的描述如下：

有M个猴子围成一圈，每个有一个编号，编号从1到M。打算从中选出一个大王。经过协商，决定选大王的规则如下：从第S个猴子开始，每隔N个，数到的猴子出圈，最后剩下来的就是大王。

要求：从键盘输入M，N，S,编程计算哪一个编号的猴子成为大王。

C#源程序如下：

/*

* User: dylan ren

* Date: 2007-6-12

* Time: 17:57

* 本程序未进行输入异常的捕获处理

*

*/

using System;

using System.Collections;

namespace Monkey

{

//上帝创造了一群猴子，设定选举规则，并命令他们选大王

public class God

{

private static int MonkeyNumbers,UperLimit,StartMonkey;

public static void Main()

{

System.Console.WriteLine("请指定猴子的数量");

string s=System.Console.ReadLine();

MonkeyNumbers=int.Parse(s);

SetRules();

MonkeyContainer mc=new MonkeyContainer(MonkeyNumbers);

mc.SelectKing(StartMonkey,UperLimit);

System.Console.ReadKey();

}

public static void SetRules(){

System.Console.WriteLine("请指定循环报数的上限");

string s=System.Console.ReadLine();

UperLimit=int.Parse(s);

System.Console.WriteLine("请指定从第几只猴子开始报数");

s=System.Console.ReadLine();

StartMonkey=int.Parse(s);

StartMonkey=StartMonkey%MonkeyNumbers;

if (StartMonkey==0) StartMonkey=MonkeyNumbers-1; //讨厌的边界处理！

else StartMonkey--;

}

}

/*

猴子们排成一圈

依次报数

被筛掉一只后，重新排队

*/

public class MonkeyContainer{

public Monkey[] MonkeyArray;

public MonkeyContainer(int MonkeyNumbers)

{

MonkeyArray=new Monkey[MonkeyNumbers];

int i=0;

while (i)>

MonkeyArray =new Monkey(i+1);

i++;

}

System.Console.WriteLine("一共有 {0} 只猴子参选!",MonkeyArray.Length);

}

public void Cycle(){

int i;

int MonkeyNumbers=MonkeyArray.Length;

for(i=0;i;i++){

int j=0;

int LivesMonkey=MonkeyArray.Length;

Monkey CurMonkey=MonkeyArray[StartMonkey];

while (LivesMonkey>1) {

j=CurMonkey.call(j); //报数

if (j==UperLimit) {

System.Console.WriteLine(" 倒霉，第{0}号猴子被放弃了!",CurMonkey.Id);

DeleteAMonkey(CurMonkey);

j=0;

LivesMonkey--;

}

CurMonkey=CurMonkey.NextMonkey;//该下一只猴子报数了

}

CurMonkey.SelectedKing();

}

public void DeleteAMonkey(Monkey CurMonkey){

CurMonkey.Unbind();

}

public void SelectKing(int StartMonkey,int UperLimit){

Cycle();

Call(StartMonkey,UperLimit);

}

}

/*

每只猴子报数

和自己的左右邻居建立连接

当邻居被筛掉后，更新邻居

被选中后，欢呼自己成为大王

*/

public class Monkey{

public int Id;

private string IsKing;

public Monkey NextMonkey;

public Monkey PriorMonkey;

public Monkey(int MonkeyId){

this.Id=MonkeyId;

this.IsKing="我还不是猴王";

}

public int call (int j){

j++;

return j;

}

public void Bind(Monkey next_monkey){

this.NextMonkey=next_monkey;

next_monkey.PriorMonkey=this;

}

public void Unbind(){

this.NextMonkey.PriorMonkey=this.PriorMonkey;

this.PriorMonkey.NextMonkey=this.NextMonkey;

}

public void SelectedKing()

{

this.IsKing="我成为猴王了，哈哈!";

System.Console.WriteLine("{0} 我的序号是 {1}",this.IsKing,this.Id);

}

}

}