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

约瑟夫问题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 版 第三课 链表存储方式的分类:顺序存储结构和链式...如下图: 循环链表的应用举例:约瑟夫问题。 [问题描述] 有 n 只猴子,按顺...
free_pascal_教程
程序框架: 一个完全的 PASCAL 程序结构框架如下: PROGRAM 程序名(程序参数表)...[i+1]; n:=n-1; END; 约瑟夫问题】 编号为 1,2,...,n 的 n 个人按...
猴子选大王问题
[编辑本段] 约瑟夫问题的另外一个有名的例子: [编辑本段] 猴子选大王 一. ...("猴王的编号是:%d\n",king); return 0; } pascal 程序: var a:array[...
Pascal教材需要掌握的程序段
pascal 程序填空 2页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出...逆时针旋转 90°180° P106 筛选法筛素数 P143 约瑟夫问题 奇数幻方 蛇形方阵...
更多相关标签: