用 Java 的 TreeSet 实现约瑟夫问题

今天在JavaEye论坛热点推荐看了篇帖子《杰哥私房题──约瑟夫问题》

自己试着写了下，用 Java 的 TreeSet 实现的。

package com.javaeye.conanca.joseph;

import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

/**
 * @author Conanca
 *
 */
public class Joseph {

	/**
	 * 问题描述
	 * 约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号
	 * 开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1 开始报数。就这样，
	 * 直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。
	 * 输入数据
	 * 每行是用空格分开的两个整数,第一个是 n ,第二个是 m ( 0 < m, n < 300),最后一行是：0 0 
	 * 输出要求
	 * 对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号
	 * 输入样例：
	 * 6 2
	 * 12 4
	 * 8 3
	 * 0 0
	 * 输出样例：
	 * 5
	 * 1
	 * 7
	 */
	public static void main(String[] args) {

		Scanner in =new Scanner(System.in); 
		System.out.print("有几只猴子选大王?"); 
		int amount = in.nextInt();
		System.out.print("喊几的退出圈子?"); 
		int num = in.nextInt();

		// 定义"猴子圈"
		Set<Integer> monkeys = new TreeSet<Integer>();
		// 初始化"猴子圈",确定每只猴子的编号。
		for (int i = 1; i <= amount; i++) {
			monkeys.add(i);
		}
		
		// 初始化报的数为1
		int i = 1;
		// 开始报数! 每一轮报数,都接着上次报的数i进行,"猴子圈"只剩1只猴子了就停止报数
		while (monkeys.size() > 1) {
			// 定义猴子编号数组,用于迭代"猴子圈"
			Integer[] monkeyNums = monkeys.toArray(new Integer[0]);
			// 迭代"猴子圈",作为一轮报数
			for (int monkeyNum : monkeyNums) {
				if (i < num) {
					// 下只猴子要报的数
					i++;
				} else {
					// 如果这只猴子报的数是num,就把它移出"猴子圈"
					monkeys.remove(monkeyNum);
					// 下只猴子报数从1开始
					i = 1;
				}
			}
		}
		
		// "猴子圈"的最后一只猴子做大王。
		int king = 0;
		for (int monkeyNum : monkeys) {
			king = monkeyNum;
		}
		
		System.out.println("大王是" + king + "号猴子");
	}

}

写完后，上论坛看到这楼牛人的回帖，大为汗颜

int findMonkey(int n, int m) 
{ 
    int r = 0; 
    for (int i = 2; i <= n; i++) 
        r = (r + m) % i; 
    return r+1; 
}

自从把Java当吃饭的家伙之后，脑子越来越笨了。

我解决问题的方式常常是模拟实际流程跑一遍，然后得出结果，根本不去考虑算法。

接下来准备买本数据结构和算法的书啃啃。

评论

1 楼 coolbaby1984514 2010-05-07  

int findMonkey(int n, int m)
{
    int r = 0;
    for (int i = 2; i <= n; i++)
        r = (r + m) % i;
    return r+1;
}

没明白什么意思 哎！！