论坛首页 综合技术论坛

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

浏览 5132 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2012-09-17   最后修改:2012-09-18

 

约瑟夫环是一个数学的应用问题:已知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。审过代码之后才发现的。不知道当时为什么会犯这样的错。

 

 

   发表时间:2012-09-17  
http://xlaohe1.iteye.com/blog/1637748
0 请登录后投票
   发表时间:2012-09-17  
这个道理很简单.F(N) = (F(N-1)+M)%N 公式这么写.实现起来就是递归..更麻烦..你可以自己写写.这个公式应该不难推倒出来的
0 请登录后投票
   发表时间:2012-09-17  
xlaohe1 写道
http://xlaohe1.iteye.com/blog/1637748

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

呵呵,不错的方法!
0 请登录后投票
   发表时间:2012-09-17   最后修改:2012-09-17
ansjsun 写道
这个道理很简单.F(N) = (F(N-1)+M)%N 公式这么写.实现起来就是递归..更麻烦..你可以自己写写.这个公式应该不难推倒出来的

你帮我解释一下怎么推导把,我真的看不懂这个公式怎么来的。
PS:如果这公式证明了,也没有必要递归。动态规划。
0 请登录后投票
   发表时间:2012-09-17  
lazy_ 写道
xlaohe1 写道
http://xlaohe1.iteye.com/blog/1637748

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

呵呵,不错的方法!

用linkedlist没错..但是应该是迭代删除..就是iterator这样删除.省时间
0 请登录后投票
   发表时间:2012-09-17  
ansjsun 写道
lazy_ 写道
xlaohe1 写道
http://xlaohe1.iteye.com/blog/1637748

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

呵呵,不错的方法!

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

嗯,因为用iterator遍历,已经拥有了当前节点的引用,不用再从0开始搜到目标节点在删除
0 请登录后投票
   发表时间:2012-09-17  
lazy_ 写道
ansjsun 写道
这个道理很简单.F(N) = (F(N-1)+M)%N 公式这么写.实现起来就是递归..更麻烦..你可以自己写写.这个公式应该不难推倒出来的

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

那条公式不要去管了,是错的! 得不出正确的结果!
0 请登录后投票
   发表时间:2012-09-17  
我也百度了下..这个公式是这样的(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: }
0 请登录后投票
   发表时间:2012-09-17   最后修改:2012-09-17
公式是对的,我的代码有错误。修正后的代码经过数学的转换其实就变成了公式
f(n) = ((m-1)%n+1+f(n-1))%n = (m%n + f(n-1))%n = (m+f(n-1))%n

ansjsun 写道
我也百度了下..这个公式是这样的(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: }

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));
	}
}


0 请登录后投票
论坛首页 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics