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

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

举个例子:

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

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

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

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

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

我们之前想的是,当数到3就取出一个,那么能不能这样想呢?

这不是一个圈,而是一条队伍,就是说两头的小屁孩儿没有手拉手,然后我们把前3个小屁孩儿依次从队伍的一头取出,并去掉取出的3个小屁儿中最后那个小屁孩儿,然后把剩下的2个小屁孩儿又依次从队伍的另一头放回去,这样反复操作,直到剩下最后一个小屁儿,而这个小屁孩儿就是我们要的那个了!

用队列解决约瑟夫问题

用队列解决约瑟夫问题

是不是感觉算法挺不错的啊!

当然,这里需要解释一下“队列”,队列是一种先进先出的存储数据的形式(应该这么形容吧),简单说就像一根管子,东西只能从一头进去,然后从另一头出来,如果要看到中间的内容,必须把前面的内容都拿出来才可以办到!!也就是说要遍历队列,需要把队列中的所有元素取出来才能办到!

Java中提供的队列接口为java.util.Queue,底层是由LinkedList实现的。Queue提供了2个重要方法,即 offer 和 poll,前者作用是从队列尾部添加元素,后者作用是从队列头部取出元素。

实现我这个算法就要用到这两个方法,下面就是代码了:

import java.util.LinkedList;
import java.util.Queue;

public class Child3Out1Queue {

	public static void main(String[] args) {

		// 初始化参数
		int num = 30; 	// 小屁孩儿数
		int whenGo = 3; // 数到3退1个
		int whenStop = 1; // 剩余1个小孩停止

		// 创建队列,并放入小屁孩儿
		Queue<Integer> circle = new LinkedList<Integer>(); // 创建一个队列
		for (int i = 0; i < num; i ++) {
			circle.offer(i + 1);  // 放入编号为1~30的小屁孩儿,其实就是位置号
		}

		// 开始循环操作
		while (circle.size() != whenStop) { 	// 剩下1个的时候停止循环
			for (int i = 0; i < whenGo; i ++) { // 依次取出3个小屁孩儿
				int temp = circle.poll(); 	// 依次取出的小屁孩儿
				if (i != whenGo - 1) { 	// 当小屁孩儿不是喊的3的时候
					circle.offer(temp); // 就从队列另一头放回去
				}
			}
		}

		System.out.println(circle); // 打印队列中的元素,也就是小屁孩儿的位置号
	}
}

这样就完成了!是不是很简单的代码呢。

说道这里,小伙伴们可以想想,如果要遍历队列,又不能丢失数据,该怎么办呢?方法就是边取边放回去!!!是不是很有意思啊~

其实,约瑟夫问题还有很多变种,下面这个就是一例,也是一道面试题:

15个教徒和15个非教徒在海上遇险,必须将一半的人投入海中,其余的人才能幸免于难,于是想了一个办法,30个人围成一个圆圈,从第一个人开始报数,每数到第九个人,就将他扔入大海,如此循环进行,直到剩余15人为止。问怎样排法,才能使每次投入大海的都是非教徒。

(17世纪法国数学家加斯帕在《数目的游戏问题》中的一个故事)

这道题其实和小屁孩儿问题差不错,不过显得更严肃一些……其实将上述代码的3个参数改一下就可以得到结果,即:

int num = 30; 	// 船上的人数
int whenGo = 9; // 数到9退1个
int whenStop = 15; // 剩余15个人停止

结果打印出来的数字就是教徒应该站的位置号。

那么,约瑟夫问题就到这里,后面有时间我再把另外两种算法贴上来~

本文《Java修道之路:我也来讲讲约瑟夫问题》来自 www.juwends.com ,欢迎转载或CV操作,但请注明出处,谢谢!