约瑟夫问题用面向对象思想来解决的方法

上一篇文章说到了约瑟夫问题,现在再用面向对象的思想来解决。

先建立两个类:Child类和Circle类,分别保存小屁孩儿的信息和圆圈的信息。

约瑟夫问题的面向对象思想解决方法

约瑟夫问题的面向对象思想解决方法

代码如下:

Child类:

/**
 * 用于描述小孩儿的信息,最关键的是该小孩儿前后的两个小孩
 * @author Bigworld
 */
class Child {
	static int count = 1; // 用于生成小孩的编号,每次实例化一个小孩会加1
	
	Child prev, next; // 表示该小孩前后2个小孩
	int id;			// 表示小孩的编号

	public Child() {
		id = count ++; // 给小孩加编号
	}
}

继续阅读

Java修道之路:我也来讲讲约瑟夫问题

“约瑟夫”名字听起来挺B格的,可是不要以为是什么很高深的玩意儿。

举个例子:

有30个小屁孩儿,手拉手的围成一个圈,然后从第一个小屁孩儿开始报数,1,2,3,当报到3时,报3的那个小屁孩儿就退出圈,然后从该报4的那个小 屁孩儿重新开始报1,当又报到3时,报3的那个小屁孩儿退出,这样反复循环,当只剩下最后一个小屁孩儿的时候,问该小屁儿是这个圈中的第几个小屁孩儿。

问题就是这么简单,怎么做呢?

首先想到的就是使用数组模拟这个圈,方法可以,但是程序写起来比较繁琐。

那么面向对象思想呢?也可以,定义一个小孩儿类和一个圈类,然后构建一个双向循环链表,也可以搞定。但是代码量也挺大,而且构建链表的时候会犯晕……

其实,我想说的是一个代码量很少而且也很好理解的算法,就是使用Java提供的“队列(Queue)”,就可以轻松搞定。但是,在这之前必须转换一下思维。 继续阅读