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

从圆桌问题谈数据结构的综合运用 - I -group=4131232345633789amount链式存链式存 储结构储结构顺序存顺序存 储结构储结构4110图 1从圆桌问题谈数据结构的综合运用从圆桌问题谈数据结构的综合运用例例圆桌问题圆桌问题(AH99) 题题目目： ：圆桌上围坐着个人。其中个人是好人，另外个人是坏人。如果从第一个人开n2nn 始数数，数到第个人，则立即处死该人；然后从被处死的人之后开始数数，再将m 数到的第个人处死依此方法不断处死围坐在圆桌上的人。试问预先应如何安m 排这些好人与坏人的座位，能使得在处死个人之后，圆桌上围坐的剩余的个人nn 全是好人。 输入：文件中的每一行都有两个数，依次为和，表示一个问题的描述信息。约束条件： nm ，。32767n32767m 输出：依次输出每一个问题的解。每一个问题的解可以用连续的若干行字符表示，每行字 符数量不超过 50。但是在一个问题的解中不允许出现空白字符和空行，相邻的两 个问题的解之间用空行隔开。用大写字母 G 表示好人，大写字母 B 表示坏人。解法解法： ：思想：模拟实际过程，寻找前n个被“处死”的人的位置。1普通解法线性表“查找”法用顺序存储结构实现用数组记录当前所有未被处死的人原来的位置，初始值为 1.2n。可根据 前一个被处死的人在数组中的位置（即下标）直接定位，找到下一个应该被处死 的人在数组中的位置，然后删去，并将它后面的元素全部前移一次。用链式存储结构实现用链表记录当前所有未被处死的人原来的位置，初始值为 1.2n。每处死 一个人后，只要将这个结点直接从链表中删去即可，然后指针后移(m-1)次，找 到下一个应该被处死的人。2改进解法“优化直接定位”法 总体思想就是在较好地实现“直接定位”的基础上，尽量避免大规模的元素移 动。 设计出的数据结构如图 1 所示：其中 group 表示将 原来的数据分为几段存储；每从圆桌问题谈数据结构的综合运用 - II -一段的开头记下的 amount 值表示此段中现有元素的个数。随程序的运行， amount 值是不断减小的。这种结构可以看作是链链式式存储结构和顺顺序序存储结构的结合产物，兼具这两种 存储结构的优点。运用了这种存储结构后，程序效率显著提高。引申引申 横向延伸其它约瑟夫环问题如：翻牌游戏、猴子选大王 纵向延伸数据结构的综合运用在解决一些数据规模较大的题目时有很好的应用。如隐藏的码字（IOI99）。在解 决这道题目时，如果运用链式和顺序相结合的数据结构（如图 2 所示），程序效率就比较 高。链式和顺序相结合的数据结构实现简单，效果显著，应用比较广泛。当然还有其它 的结合方式，比如二叉堆和顺序结构的一一映射（单射），在解决某些问题时有非常好的 效果。小结小结“网络式思维方式的核心是联联系系”。在做题目时，我们应深挖题目所给条件、各种数据结 构以及算法之间的联系，这样才能更好地完成题目，并达到提高自己的目的。这篇论文仅仅是从一类很常见的问题约瑟夫环（也称 Josephus 排列）问题出发， 并由此引申出数据结构的综合运用。对于形式多样的信息学问题来说，数据结构的综合运 用只是解题策略中的一个小方面，但是如果我们对待每个问题、算法、数据结构等，都能深 入发掘它与其它事物的联系，那么我们就可以自然而然地建立起知识网络，在必要的时候 综合运用。而这对于我们的学习、研究将大有帮助。特别需要强调的是：本文提到“数据结构的综合运用”，这里的综合并不单单是指形式 上的，更重要的是指思想（即内涵）的综合。只要在思想上体现出两种或多种数据结构的优 点，在操作时发挥出它们的优点，就已经从根本上达到了综合的目的。CBDADCCBADCA图 2