精华帖 (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)表示的意思是 )
正确的程序 (程序说明 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; 这一句错了。。。应该是int firstKilledPos = (m-1)%i。审过代码之后才发现的。不知道当时为什么会犯这样的错。
声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2012-09-17
http://xlaohe1.iteye.com/blog/1637748
|
|
返回顶楼 | |
发表时间:2012-09-17
这个道理很简单.F(N) = (F(N-1)+M)%N 公式这么写.实现起来就是递归..更麻烦..你可以自己写写.这个公式应该不难推倒出来的
|
|
返回顶楼 | |
发表时间:2012-09-17
xlaohe1 写道 http://xlaohe1.iteye.com/blog/1637748
我大致理解你的算法了,自己写个链表就从头到尾按着游戏规则删除节点可以了。。。我的O(N^2)的那个算法偷懒用了LinkedList,导致remove的时候消耗了O(n^2)的时间! 呵呵,不错的方法! |
|
返回顶楼 | |
发表时间:2012-09-17
最后修改:2012-09-17
ansjsun 写道 这个道理很简单.F(N) = (F(N-1)+M)%N 公式这么写.实现起来就是递归..更麻烦..你可以自己写写.这个公式应该不难推倒出来的
你帮我解释一下怎么推导把,我真的看不懂这个公式怎么来的。 PS:如果这公式证明了,也没有必要递归。动态规划。 |
|
返回顶楼 | |
发表时间:2012-09-17
lazy_ 写道 xlaohe1 写道 http://xlaohe1.iteye.com/blog/1637748
我大致理解你的算法了,自己写个链表就从头到尾按着游戏规则删除节点可以了。。。我的O(N^2)的那个算法偷懒用了LinkedList,导致remove的时候消耗了O(n^2)的时间! 呵呵,不错的方法! 用linkedlist没错..但是应该是迭代删除..就是iterator这样删除.省时间 |
|
返回顶楼 | |
发表时间:2012-09-17
ansjsun 写道 lazy_ 写道 xlaohe1 写道 http://xlaohe1.iteye.com/blog/1637748
我大致理解你的算法了,自己写个链表就从头到尾按着游戏规则删除节点可以了。。。我的O(N^2)的那个算法偷懒用了LinkedList,导致remove的时候消耗了O(n^2)的时间! 呵呵,不错的方法! 用linkedlist没错..但是应该是迭代删除..就是iterator这样删除.省时间 嗯,因为用iterator遍历,已经拥有了当前节点的引用,不用再从0开始搜到目标节点在删除 |
|
返回顶楼 | |
发表时间:2012-09-17
lazy_ 写道 ansjsun 写道 这个道理很简单.F(N) = (F(N-1)+M)%N 公式这么写.实现起来就是递归..更麻烦..你可以自己写写.这个公式应该不难推倒出来的
你帮我解释一下怎么推导把,我真的看不懂这个公式怎么来的。 PS:如果这公式证明了,也没有必要递归。动态规划。 那条公式不要去管了,是错的! 得不出正确的结果! |
|
返回顶楼 | |
发表时间: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: } |
|
返回顶楼 | |
发表时间: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)); } } |
|
返回顶楼 | |