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

约瑟夫问题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 语言练习一_IT/计算机_专业资料。pascal 语言 基础编程练习 基础编程练习...12.约瑟夫问题:n 个人围成一圈,从第一个人开始报数,数到 k 的人出圈.再...
Pascal数组习题
Pascal数组习题_学科竞赛_高中教育_教育专区。适用于想要参加NOIP的中学阶段学生,...12. 约瑟夫问题:n 个人围成一圈,从第一个人开始报数,数到 k 的人出圈。...
pascal基础
pascal基础编程 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题...[i+1]; n:=n-1; END; 【约瑟夫问题】 编号为 1,2,...,n 的 n 个...
Pascal语言编程基础程序
约瑟夫 1 var a:array[1..100] of 0..1; n,m,left,count,wei,i:...Pascal语言1-3(Tp与Fp的... 暂无评价 72页 免费 问题1 认识用Pascal语言.....
pascal morabito (FR-EN-ZH)
pascal morabito (FR-EN-ZH)_设计/艺术_人文社科_专业资料。(French is the ...深沉而持久,堪比“创造性破坏”理论之父——经济学家约瑟夫·熊彼特(Joseph ...
信息学奥赛数据结构教程pascal版
信息学奥赛数据结构教程 PASCAL 版 第三课 链表存储方式的分类:顺序存储结构和链式...如下图: 循环链表的应用举例:约瑟夫问题。 [问题描述] 有 n 只猴子,按顺...
数据结构复习题(附答案)
3、约瑟夫问题(Josephus 问题)是指编号为 1、2、…,n的 n(n>0)个人按...(2) .请用 C 或 PASCAL 编写一个函数 BIPARTITE 判断一个连通无向图 G ...
数据结构习题
() 3. 在高级语言(如 C 或 PASCAL)中,指针类型是原子类型。()三、计算...2. 约瑟夫环问题。 约瑟夫问题的一种描述是:编号为 1,2,?,n 的 n 个人按...
猴子选大王问题
[编辑本段] 约瑟夫问题的另外一个有名的例子: [编辑本段] 猴子选大王 一. ...("猴王的编号是:%d\n",king); return 0; } pascal 程序: var a:array[...
NOIP算法整理_图文
NOIP算法整理_学科竞赛_高中教育_教育专区。2015NOIP算法总结PASCAL版 ...(b × c) mod p) mod p 约瑟夫问题 递推公式,设有 n 个人( 0,......
更多相关标签:
约瑟夫问题 | 约瑟夫问题 循环链表 | 约瑟夫问题c | 约瑟夫问题c语言 | 约瑟夫问题 java | 约瑟夫问题数学解法 | 约瑟夫问题c语言详解 | 顺序表实现约瑟夫问题 |