大家看看我写的约瑟夫环(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编号的N个人，从0开始数，0号数1，1号数2..数到M的那个人会被杀掉, 被杀掉的人之后的人数1，后面的接着数2...这样后面只会剩下一个人，f(n)的返回值就是这唯一活着的人的编号。

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

)

 

 

正确的程序

(程序说明

f(n,m)是我写的方法，f(n) =( (m-1)%n+1+f(n-1))%n，计算0到n-1编号的n个人，从0号人开始数1...m，最后存活人的序号，为什么这么算看程序注释

f2(n,m)是根据网上的公式F(N) = (F(N-1)+M)%N写的方法

实际上f(n,m)和f2(n,m)等价的。

f(n) =( (m-1)%n+1+f(n-1))%n = (m%n + f(n-1))%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;//计算有N个人，从第一个开始数，第一个会被杀掉的人的序号(序号从0开始)
			int livePos = res[i-1];//livePos是N-1个人的时候存活人的序号。对于N的情况，只要从被杀死的第一个人序号之后往后数livePos，就可以得到存活人的序号
			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));
	}
}

 

 

后记：这是原来错误的程序，正确的程序在前面

 

package algorithm;

import java.util.LinkedList;

public class FastJosephus {

	public static int f(int n, int m){
		int[] res = new int[n];
		res[0] = 0;
		for(int i=1;i<n;i++){
			int firstKilledPos = i%m;//计算有N个人，从第一个开始数，第一个会被杀掉的人//这一句错了。。。应该是int firstKilledPos =  (m-1)%i。后面审过代码之后才发现。当时估计懵了，不知道为什么会犯这样的错。
			int livePos = res[i-1];
			res[i] = ((firstKilledPos+1)+livePos)%i;
		}
		return res[n-1];
	}
	
	public static int g(int n,int k ,int m ){
		return (f(n,m)+(k-1))%n + 1;
	}
	
	public static void main(String[] args){
		System.out.println(g(9,1,5));
	}
}

 

 

int firstKilledPos = i%m;

这一句错了。。。应该是int firstKilledPos =  (m-1)%i。审过代码之后才发现的。不知道当时为什么会犯这样的错。

 

 

http://xlaohe1.iteye.com/blog/1637748

这个道理很简单.F(N) = (F(N-1)+M)%N 公式这么写.实现起来就是递归..更麻烦..你可以自己写写.这个公式应该不难推倒出来的

我大致理解你的算法了，自己写个链表就从头到尾按着游戏规则删除节点可以了。。。我的O（N^2)的那个算法偷懒用了LinkedList，导致remove的时候消耗了O(n^2)的时间！

呵呵，不错的方法！

你帮我解释一下怎么推导把，我真的看不懂这个公式怎么来的。
PS：如果这公式证明了，也没有必要递归。动态规划。

用linkedlist没错..但是应该是迭代删除..就是iterator这样删除.省时间

嗯，因为用iterator遍历，已经拥有了当前节点的引用，不用再从0开始搜到目标节点在删除

那条公式不要去管了，是错的！ 得不出正确的结果！

我也百度了下..这个公式是这样的(n,m) = ( f(n-1,m)+m )%n

你试试这段代码


  1: int findTheLast(int n, int m) 
  2: {
  3:     int last=0;
  4:     for (int i=2; i<=n; i++) 
  5:     {
  6:         last = (last+m)%i; 
  7:     }
  8:     return last;
  9: }

公式是对的，我的代码有错误。修正后的代码经过数学的转换其实就变成了公式
f(n) = ((m-1)%n+1+f(n-1))%n = (m%n + f(n-1))%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));
	}
}