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

约瑟夫问题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语言编程基础程序
约瑟夫 1 var a:array[1..100] of 0..1; n,m,left,count,wei,i:...Pascal语言1-3(Tp与Fp的... 暂无评价 72页 免费 问题1 认识用Pascal语言.....
信息学道简单题
33. 约瑟夫问题,max 人围成一圈,每数到 jump,则该人出圈,直至所有人全部...(详见 Turbo Pascal 的 Page 146-17) 46. 打印由 1——N*N 组成的 N*N...
pascal morabito (FR-EN-ZH)
pascal morabito (FR-EN-ZH)_设计/艺术_人文社科_专业资料。(French is the ...深沉而持久,堪比“创造性破坏”理论之父——经济学家约瑟夫·熊彼特(Joseph ...
toj题目
TOJ1012 约瑟夫问题 Time Limit:1s Memory Limit:1000k Problem 将编号为 1,...=7 Output 输出一段 pascal 的代码 Sample Input 3 2 Sample Output var a,...
2013湖北省分析数据库的考试题目高级
“%c”,ptr->info); } 7、约瑟夫问题(Josephus 问题)是指编号为 1、2...(2) . 请用 C 或 PASCAL 编写一个函数 BIPARTITE 判断一个连通无向图 G ...
数据结构作业答案
)( 2. 算法就是程序。 )( 3. 在高级语言(如 C 或 PASCAL)中,指针类型...(); } 9、约瑟夫问题 设有 N 个人围坐在圆桌周围,现从某个位置 M(1<=M...
2015云南省分析数据库的考试题目高级
(2) . 请用 C 或 PASCAL 编写一个函数 BIPARTITE 判断一个连通无向图 G ...8、约瑟夫问题(Josephus 问题)是指编号为 1、2、?,n 的 n(n>0)个人按...
2013湖北省分析数据库的考试题目深入
(注:双向起泡排序即相邻两趟排序向相反方向起泡) 3、约瑟夫问题(Josephus ...(2) . 请用 C 或 PASCAL 编写一个函数 BIPARTITE 判断一个连通无向图 G ...
实验报告B
请到百度文库投诉中心;如要提出功能问题或意见建议,...数组类型声明部分的扩充 依据 PASCAL 语法进行扩充,...(文件名:YUESE.pl0 )约瑟夫环的数组结构实现程序。...
更多相关标签:
约瑟夫问题 | 约瑟夫问题c语言 | 约瑟夫问题 c | 约瑟夫问题 java | 约瑟夫问题 循环链表 | 约瑟夫问题公式 | 约瑟夫问题实验报告 | 约瑟夫问题数学解法 |