约瑟夫环是一个数学的应用问题:已知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)); } }
相关推荐
c# 约瑟夫环问题算法 的实现。
文档里有约瑟夫环问题的算法设计报告,还有C++程序。
约瑟夫环算法描述 //从第s人开始计数,以m为单位循环记数出列,总人数为n public int Josephas (int n, int m, int s) { int i, j, k = 0; //count数组存储按出列顺序的数据,以当结果返回 int[] count =...
【语音加密】基于matlab约瑟夫环混沌加密算法语音加密【含Matlab源码 3105期】
本程序是实现约瑟夫环的算法,引用了一些节省效率的算法。相比较于其他的算法,本算法更简单而有效率。
数据结构(C#)约瑟夫算法描述和程序实现
约瑟夫环的C++程序和算法设计报告,还附带图文。
算法设计中,约瑟夫环的问题,可以练习一下你的逻辑思维能力,以及你的分析能力。
约瑟夫环 算法 代码 数据结构 VS2008编写
约瑟夫环万体的算法实现,供大家参考实现,希望帮助大家
约瑟夫环c++的正确算法,可以输入总人数,但统一密码
详细描述了约瑟夫环实现的集中算法,具体请下载查看
c语言约瑟夫环模拟算法c语言约瑟夫环模拟算法c语言约瑟夫环模拟算法
单链表解决约瑟夫环问题
约瑟夫(Josephus)环问题:编号为1,2,3,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m的人...
程序员面试中经常遇到约瑟夫环生成问题,可以用链表方式生成约瑟夫环。
文档中对约瑟夫环最高效数学解法进行了详细解释,并给出了C++源码的实现
约瑟夫环的算法的实现,可以直接运行,经过测试了的,详细情况可以自己下载后查看。
约瑟夫环问题 C语言问题约瑟夫环问题 C语言问题
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律...