大家看看我写的约瑟夫环(O(N))算法有没有问题

 

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人会被杀死；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到剩下一个人生存。

 

　　n = 9,k = 1,m = 5　　【解答】

　　出局人的顺序为5,1,7,4,3,6,9,2,8。

 

题目引用了 百度百科  http://baike.baidu.com/view/717633.htm

 

当然，我们最关心的是最后的那个输出——不死的位置

 

这个题目我自己先做出了一个O（N^2)的，相信许多人都能直接地想到

 

 

package algorithm;

import java.util.LinkedList;

public class Josephus {
	LinkedList<Integer> list = new LinkedList<Integer>();
	private int n;
	private int k;
	private int m;
	public Josephus(int n, int k, int m){
		this.n = n;
		this.k = k;
		this.m = m;
		for(int i=1;i<=n;i++){
			list.add(i);
		}
	}
	
	//1...n, 从K位置开始数起(K是1),数到M，移除一个
	public void print(){
		while(n>0){
			int pos = getPos(n,k,m);
			System.out.print(list.remove(pos-1));
			n--;
			k = pos;
		}
	}
	//存在数学计算，指定N,K,M可以知道排第几的要被移除
	private static int getPos(int n, int k,int m){
		m = (m%n==0)? n : m%n;
		k = (k%n==0)? n : k%n;
		if(k-1+m<=n){
			return k-1+m;
		}else{
			return (k-1+m)-n;
		}
	}
	public static void main(String[] args){
		new Josephus(9,1,5).print();
	}
}

 

 输出和百度百科的结果一样

 

接下肯定是找O（N）的，当时我觉得自己不可能想得到的了，就直接GOOGLE，结果百度百科的推导根本不是推导，直接抄来的公式F(N) = (F(N-1)+M)%N，而WIKI的推导，看不懂，还看到一种是分奇数和偶数的数学推导，更难看懂，ORZ，于是自己在纸上面画一画，罗列一些情况，看看找不找得到规律

结果真的找到规律了

 

假设N个人编号是从0到N-1,并且考虑没有K的情况，都是从0号的人开始数，数到M的人会被干掉。F（N,M）代表生存下来的那个人的编号。

 

在纸上罗列M=5的情况时候，发现F（N)的问题，在杀掉一个人之后，完全可以转化成F（N-1)的问题——这太像动态规划了！

 

于是产生了以下算法

 

f(n)表示的意思是
0...n-1个人，从0开始数，0号数1，1号数2..数到N的那个人会被杀掉。被杀掉的人之后的人数1，后面的接着数2...这样后面只会剩下一个人，f(n)的返回值就是这个人原来的编号。

g(n)，其实为了适应题意对f(n)的结果做转化,N个人的编号为1到N，并且新增一个参数表示从第K个人开始数，而不一定是第一个人。

我们程序输出的是8，与结果一致，暂时正确！

 

int firstKilledPos =  (m-1)%i

 

推导过程如下

f(n) = ((m-1)%n + 1 + f(n-1))%n = (m%n + f(n-1))%n = (m+f(n-1))%n

正确程序的f(n,m)使用了

f(n) = ((m-1)%n + 1 + f(n-1))%n，

有N个人时，(m-1)%n表示的第一个被杀掉的人的位置，(m-1)%n + 1 + f(n-1)表示，根据N-1时已经计算的存货的位置，以被杀的人位置为原点，得到最后存活的人的位置，((m-1)%n + 1 + f(n-1))%n则表示如果位置大于N则取模。

而f2(m,n)使用了

(m+f(n-1))%n

正确的程序

 

 

package algorithm;

import java.util.LinkedList;

public class FastJosephus {

	public static int f(int n, int m){
		int[] res = new int[n+1];
		res[1] = 0;
		for(int i=2;i<=n;i++){
			int firstKilledPos = (m-1)%i;
			int livePos = res[i-1];
			res[i] = ((firstKilledPos+1)+livePos)%i;
		}
		return res[n];
	}
	public static int f2(int n, int m){
		int[] res = new int[n+1];
		res[1] = 0;
		for(int i=2;i<=n;i++){
			res[i] = (res[i-1]+m)%i;
		}
		return res[n];
	}
	
	public static int g(int n,int k ,int m ){
		return (f(n,m)+(k-1))%n + 1;
	}
	public static int g2(int n,int k ,int m ){
		return (f2(n,m)+(k-1))%n + 1;
	}
	
	public static void main(String[] args){
		System.out.println(g(7,1,4));
		System.out.println(g2(7,1,4));
	}
}