当前位置:首页 >> 学科竞赛 >>

约瑟夫问题pascal


约瑟夫问题(有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题。在 计算机编程的算法中,类似问题又称为约瑟夫环。又称“丢手绢问题”) 据说著名犹太历史学家 Josephus 有过以下的故事:在罗马人占领乔塔帕特后,39 个 犹太人与 Josephus 及他的朋友躲到一个洞中,39 个犹太人决定宁愿死也不要被敌人抓到, 于是决定了一个自杀方式,41 个人排成一个圆圈,由第

1 个人开始报数,每报数到第 3 人 该人就必须自杀, 然后再由下一个重新报数, 直到所有人都自杀身亡为止。 然而 Josephus 和 他的朋友并不想遵从。首先从一个人开始,越过 k-2 个人(因为第一个人已经被越过),并 杀掉第 k 个人。接着,再越过 k-1 个人,并杀掉第 k 个人。这个过程沿着圆圈一直进行,直 到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么 地方才能避免被处决?Josephus 要他的朋友先假装遵从,他将朋友与自己安排在第 16 个 与第 31 个位置,于是逃过了这场死亡游戏。//详情请见百度百科。

[题目描述] Josephus 问题是建立在历史学家 Josephus 的一个报告的基础之上, 该报告 讲述了他和 40 个士兵在公元 67 年被罗马军队包围期间签定的一个自杀协定, Josephus 建议每个人杀死他的邻居,他很聪明的使自己成为这些人中的最后一 个,因此获得生还。 21 世纪的今天,我们将 Josephus 问题稍作扩展:设 N 个人围成一圈,依次 从 1 到 N 编号,从第 S 号开始报数,报到 K 的人出列,求第 T 个出列的人的编 号。显然,Josephus 面对的是 N = 40, K = 2, S= 1, T = 40 的退化情况。 [数据范围] 30%的数据,K = 2 100%的数据,1 <= N <= 1000000, 1<= K <= 2147483647, 1 <= S <= N, 1 <= T <=
N

最简单的推导方法应该是模拟。 用模拟的链表或是数组, 而这样求解复杂度 为 O(n*m),无法承受。
为了讨论方便,先把问题稍微改变一下,并不影响原意: 首先,设 n 个人的编号为 0..n-1,数到 k 的人出列。//此处便于 mod n 循环的处理。 假如我们知道 n-1 个人的解,那么很容易可以推导出 n 个人。 即 x[n]:=(x[n-1]+k)mod n; 有了这样的递推公式,我们就可以求的最后一个出列人的解。而事实上,本题需要求 解的结果为第 t 个出列的人,我们只需要一个巧妙的转化:我们还原 n-t+1 个人的队列,求 n-t+1 个人第一个出列的人, 即第数到 k-1 的人。 那么 n-t+2 个人的解就变成了(f[n-t+1]+k)mod n,以此类推。那么第 t 个人的解,也就是 f[n]显然可以推导出,代码如下 x:=(k-1)mod (n-t+1); //n-t+1 个人解。 for i:=n-t+2 to n do x:=(x+k)mod n; //递推结果。 x:=(x+s-1)mod n+1;//由于是从第 s 个人开始,平移答案。末尾加一,还原编号。 代码巨短,再次为(数学与算法的巧妙神奇)鞠躬。


相关文章:
Pascal数组习题
Pascal数组习题_学科竞赛_高中教育_教育专区。适用于想要参加NOIP的中学阶段学生,...12. 约瑟夫问题:n 个人围成一圈,从第一个人开始报数,数到 k 的人出圈。...
pascal语言
初识PASCAL 一个完全的 PASCAL 程序结构框架如下: PROGRAM 程序名(程序参数表)...[i+1]; n:=n-1; END; 【约瑟夫问题】 编号为 1,2,...,n 的 n 个人...
PASCAL竞赛试题汇编
PASCAL竞赛试题汇编_工学_高等教育_教育专区。PASCAL...23、约瑟夫环:有 N 个人围成一圈,每隔 M 个人就...42、爱因斯坦阶梯问题,有一个长阶梯,如果每步跨 2 ...
Pascal语言编程基础程序
约瑟夫 1 var a:array[1..100] of 0..1; n,m,left,count,wei,i:...Pascal语言1-3(Tp与Fp的... 暂无评价 72页 免费 问题1 认识用Pascal语言.....
free_pascal_教程
程序框架: 一个完全的 PASCAL 程序结构框架如下: PROGRAM 程序名(程序参数表)...[i+1]; n:=n-1; END; 约瑟夫问题】 编号为 1,2,...,n 的 n 个人按...
初识PASCAL
初识PASCAL 一个完全的 PASCAL 程序结构框架如下: PROGRAM 程序名(程序参数表)...[i+1]; n:=n-1; END; 约瑟夫问题】 编号为 1,2,...,n 的 n 个人按...
PASCAL教学
P A S C A L 教学 http://www.zjtg.cn/itjs/pascaljx/default.asp 初识...[i+1]; n:=n-1; END; 约瑟夫问题约瑟夫问题】 编号为 1,2,...,n ...
toj题目
TOJ1012 约瑟夫问题 Time Limit:1s Memory Limit:1000k Problem 将编号为 1,...=7 Output 输出一段 pascal 的代码 Sample Input 3 2 Sample Output var a,...
初赛复习提纲
7、局部变量和全局变量的使用范围 重点掌握:Pascal 语言的基本数据类型(字符、...处理问题: 6、 约瑟夫问题(或猴子选大王问题、密码问题) : 7、 回文数问题:...
猴子选大王问题
[编辑本段] 约瑟夫问题的另外一个有名的例子: [编辑本段] 猴子选大王 一. ...("猴王的编号是:%d\n",king); return 0; } pascal 程序: var a:array[...
更多相关标签: