约瑟夫环问题研究(一)

最近在看C方面的东西，看到了李明老师讲解的约瑟夫环问题，感觉很有意思，于是在看了他的讲解之后，自己又重新按照他的思路进行了编写，整理如下：

问题描述：约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。

代码一：

/**
 * 约瑟夫环问题的研究
 * @author ryn
 * 
 */

public class Josephu {
	
	private static int ALL = 6;		//总共进行游戏的人数
	private static int OUT = 3;		//规定的数字(每数到3就出局)
	private static int[] people = new int[ALL];	//定义游戏的人数组
	
	public static void main(String[] args) {
		init();
		print();
		execute();
	}

	/**
	 * 执行出局操作
	 */
	private static void execute() {
		int left = ALL;		//剩下游戏的人数
		int counter = 0;	//计数器
		int index = 0;		//游戏对应索引值(下标值)
		
		//当还没有人出局,就继续进行出局操作
		while(left > 0) {
			
			//如果对应当前索引的人没有出局,则让计数器加1
			if(people[index] > 0) {
				counter++;
			}
			
			if(counter == OUT) {
				//每次执行了出局操作就将剩下的人数减1
				left--;
				System.out.println("people " + people[index] + " is out!");
				//将出局了的人的对应值置为0
				people[index]  = 0;
				//重置计数器
				counter = 0;
			}
			

<span style="white-space:pre">			</span>//print();
			System.out.println("index: " + index + " counter: " + counter + " left: " + left);
			
			//索引自增,指向下一个人
			index++;
			
			//当索引越界,让其重新值为第一个人
			if(index == ALL) {
				index = 0;
			}
		}
	}

	/**
	 * 进行打印操作
	 */
	private static void print() {
		for(Integer i : people) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	/**
	 * 进行初始化操作
	 */
	private static void init() {
		for(int i = 0; i < ALL; i++) {
			people[i] = i + 1;
		}
	}
}

当我们将打印数组的函数取消注释时，打印的结果是：

我只是截取了其中的一小部分，可以看到，其中每次循环其实都进行了很多无用的比较(也就是每次都要判断数组中对应的值是不是大于0)

那么有没有什么办法能够去除这些无用的比较呢？

那就是设置一个指向下一个有效元素的数组，保存下一个有效元素的索引值，这样，每次比较的值必定是大于0的

代码如下：

/**
 * 约瑟夫环问题的研究
 * @author ryn
 * 
 */

public class Josephu {
	
	private static int ALL = 6;		//总共进行游戏的人数
	private static int OUT = 3;		//规定的数字(每数到3就出局)
	private static int[] people = new int[ALL];	//定义游戏的人数组
	private static int[] next = new int[ALL];	//定义对应的指向下一个人的数组
	
	public static void main(String[] args) {
		init();
		print();
		execute();
	}
	
	/**
	 * 执行出局操作
	 */
	private static void execute() {
		int left = ALL;		//剩下游戏的人数
		int counter = 0;	//计数器
		int index = 0;		//游戏对应索引值(下标值)
		int prev = ALL - 1;	//0号索引值对应的前一位就应该是整个索引表的最后一位
		
		//当还没有人出局,就继续进行出局操作
		while(left > 0) {
			
			//如果对应当前索引的人没有出局,则让计数器加1
			if(people[index] > 0) {
				counter++;
			}
			
			if(counter == OUT) {
				//每次执行了出局操作就将剩下的人数减1
				left--;
				System.out.println("people " + people[index] + " is out!");
				//将下一个未出局的人的索引赋值给上一个未出局人的索引
				next[prev] = next[index];
				//将出局了的人的对应值置为0
				people[index]  = 0;
				//重置计数器
				counter = 0;
			}
			
			//print();
			System.out.println("index: " + index + " counter: " + counter + " left: " + left);
			
			//记录上一个未出局人的索引值
			prev = index;
			//使index的值每次循环都具有意义(不需要比较出局了的人)
			index = next[index];
		}
	}

	/**
	 * 进行打印操作
	 */
	private static void print() {
		for(Integer i : people) {
			System.out.print(i + " ");
		}
		System.out.print("people\n");
		for(Integer i : next) {
			System.out.print(i + " ");
		} 
		System.out.print("next\n");
	}

	/**
	 * 进行初始化操作(包括游戏人和对应链表)
	 */
	private static void init() {
		for(int i = 0; i < ALL; i++) {
			people[i] = i + 1;
		}
		for(int i = 0; i < ALL; i++) {
			next[i] = (i + 1) % ALL;
		}
	}
}

这次打印的结果如下:

这次可以看到，每次的操作都只是进行了上次比较，那么效率就提高了不止一点了

那么细看一下代码，是不是还有什么优化的地方呢？