您所在位置：网站首页 > 行业资料 > 其它行业文档国家集训队论文从圆桌问题谈数据结构的综合运用2

国家集训队论文从圆桌问题谈数据结构的综合运用2

2页

卖家[上传人]：飞***

文档编号：40496691

上传时间：2018-05-26

文档格式：DOC

文档大小：47KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 金贝

/ 2 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、从圆桌问题谈数据结构的综合运用 - I -group=4131232345633789amount链式存链式存储结构储结构顺序存顺序存储结构储结构4110图 1从圆桌问题谈数据结构的综合运用从圆桌问题谈数据结构的综合运用例例圆桌问题圆桌问题(AH99) 题题目目：：圆桌上围坐着个人。其中个人是好人，另外个人是坏人。如果从第一个人开n2nn 始数数，数到第个人，则立即处死该人；然后从被处死的人之后开始数数，再将m 数到的第个人处死依此方法不断处死围坐在圆桌上的人。试问预先应如何安m 排这些好人与坏人的座位，能使得在处死个人之后，圆桌上围坐的剩余的个人nn 全是好人。输入：文件中的每一行都有两个数，依次为和，表示一个问题的描述信息。约束条件： nm ，。32767n32767m 输出：依次输出每一个问题的解。每一个问题的解可以用连续的若干行字符表示，每行字符数量不超过 50。但是在一个问题的解中不允许出现空白字符和空行，相邻的两个问题的解之间用空行隔开。用大写字母 G 表示好人，大写字母 B 表示坏人。解法解法：：思想：模拟实际过程，寻找前n个被“处死”的人的位置。1普通解法

2、线性表“查找”法用顺序存储结构实现用数组记录当前所有未被处死的人原来的位置，初始值为 1.2n。可根据前一个被处死的人在数组中的位置（即下标）直接定位，找到下一个应该被处死的人在数组中的位置，然后删去，并将它后面的元素全部前移一次。用链式存储结构实现用链表记录当前所有未被处死的人原来的位置，初始值为 1.2n。每处死一个人后，只要将这个结点直接从链表中删去即可，然后指针后移(m-1)次，找到下一个应该被处死的人。2改进解法“优化直接定位”法总体思想就是在较好地实现“直接定位”的基础上，尽量避免大规模的元素移动。设计出的数据结构如图 1 所示：其中 group 表示将原来的数据分为几段存储；每从圆桌问题谈数据结构的综合运用 - II -一段的开头记下的 amount 值表示此段中现有元素的个数。随程序的运行， amount 值是不断减小的。这种结构可以看作是链链式式存储结构和顺顺序序存储结构的结合产物，兼具这两种存储结构的优点。运用了这种存储结构后，程序效率显著提高。引申引申横向延伸其它约瑟夫环问题如：翻牌游戏、猴子选大王纵向延伸数据结构的综合运用在解决一些数据规模

3、较大的题目时有很好的应用。如隐藏的码字（IOI99）。在解决这道题目时，如果运用链式和顺序相结合的数据结构（如图 2 所示），程序效率就比较高。链式和顺序相结合的数据结构实现简单，效果显著，应用比较广泛。当然还有其它的结合方式，比如二叉堆和顺序结构的一一映射（单射），在解决某些问题时有非常好的效果。小结小结“网络式思维方式的核心是联联系系”。在做题目时，我们应深挖题目所给条件、各种数据结构以及算法之间的联系，这样才能更好地完成题目，并达到提高自己的目的。这篇论文仅仅是从一类很常见的问题约瑟夫环（也称 Josephus 排列）问题出发，并由此引申出数据结构的综合运用。对于形式多样的信息学问题来说，数据结构的综合运用只是解题策略中的一个小方面，但是如果我们对待每个问题、算法、数据结构等，都能深入发掘它与其它事物的联系，那么我们就可以自然而然地建立起知识网络，在必要的时候综合运用。而这对于我们的学习、研究将大有帮助。特别需要强调的是：本文提到“数据结构的综合运用”，这里的综合并不单单是指形式上的，更重要的是指思想（即内涵）的综合。只要在思想上体现出两种或多种数据结构的优点，在操作时发挥出它们的优点，就已经从根本上达到了综合的目的。CBDADCCBADCA图 2

《国家集训队论文从圆桌问题谈数据结构的综合运用2》由会员飞***分享，可在线阅读，更多相关《国家集训队论文从圆桌问题谈数据结构的综合运用2》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源