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

约瑟夫问题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_学科竞赛_高中教育_教育专区。约瑟夫问题(有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题。在 计算机编程的算法中,类似问题又称为...
pascal数组解决约瑟夫环问题
pascal数组解决约瑟夫问题_电脑基础知识_IT/计算机_专业资料。pascal 数组解决约瑟夫问题 数据结构: a:array[1..100] of integer; 保存约瑟夫环中所有人的编号...
PASCAL竞赛试题汇编
PASCAL竞赛试题汇编_学科竞赛_小学教育_教育专区。...23、约瑟夫环:有 N 个人围成一圈,每隔 M 个人就...42、爱因斯坦阶梯问题,有一个长阶梯,如果每步跨 2 ...
Pascal数组习题
Pascal数组习题_学科竞赛_高中教育_教育专区。适用于想要参加NOIP的中学阶段学生,...12. 约瑟夫问题:n 个人围成一圈,从第一个人开始报数,数到 k 的人出圈。...
free_pascal_教程
程序框架: 一个完全的 PASCAL 程序结构框架如下: PROGRAM 程序名(程序参数表)...[i+1]; n:=n-1; END; 约瑟夫问题】 编号为 1,2,...,n 的 n 个人按...
pascal山东潍坊市青少年00-07市赛试题
pascal 第3讲 程序的结构 40页 免费如要投诉违规内容,请到百度文库投诉中心;如...15 3.约瑟夫问题:M 个人围成一圈,从第一个人开始报数,数到 N 的人出圈...
pascal morabito (FR-EN-ZH)
pascal morabito (FR-EN-ZH)_设计/艺术_人文社科_专业资料。(French is the ...深沉而持久,堪比“创造性破坏”理论之父——经济学家约瑟夫·熊彼特(Joseph ...
数据结构实验报告(杨辉三角,约瑟夫环)
数据结构实验报告 杨辉三角形(Pascal (Pascal’ 实验...程序所能达到的功能用户由键盘输入约瑟夫环的必要数据...采用 if 语句对 s=1 的情 况单独处理将问题解决...
NOIP算法整理
NOIP算法整理_学科竞赛_高中教育_教育专区。2015NOIP算法总结PASCAL版 ...(b × c) mod p) mod p 约瑟夫问题 递推公式,设有 n 个人( 0,......
英语翻译
其中涉及水静止或运动的物理行为的液压学 问题一直是...This along with Pascal’s law operates at the ...布拉玛约瑟夫后来开发了基于帕斯卡的新闻, 而伯努利...
更多相关标签:
pascal解决约瑟夫问题 | 双向约瑟夫问题pascal | 约瑟夫问题 | 约瑟夫问题 c | 约瑟夫问题c语言 | 约瑟夫问题 java | 约瑟夫问题 循环链表 | 约瑟夫问题公式 |