奥林匹克竞赛论文-从圆桌问题谈数据结构的综合运用mine1最终.doc

从圆桌问题谈数据结构的综合运用 PAGE PAGE IV 从圆桌问题谈数据结构的综合运用 例．圆桌问题(99年安徽省赛题) 题目：圆桌上围坐着个人。其中个人是好人，另外个人是坏人。如果从第一个人开始数数，数到第个人，则立即处死该人；然后从被处死的人之后开始数数，再将数到的第个人处死……依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位，能使得在处死个人之后，圆桌上围坐的剩余的个人全是好人。 输入：文件中的每一行都有两个数，依次为和，表示一个问题的描述信息，，。 输出：依次输出每一个问题的解。每一个问题的解可以用连续的若干行字符来表示，每行的字符数量不超过50。但是在一个问题的解中不允许出现空白字符和空行，相邻的两个问题的解之间用空行隔开。用大写字母G表示好人，大写字母B表示坏人。 解法： 思想：模拟实际过程，寻找前n个被“处死”的人的位置（注：此处插入图示1） 普通解法——线性表“查找”法 用顺序存储结构实现 用数组记录当前所有未被处死的人在原来的位置，初始值为1..2n。可根据前一个被处死的人在数组中的位置（即下标）直接定位，找到下一个应该被处死的人在数组中的位置，然后删去，并将它后面的元素全部前移一次。（注：此处插入图示2，并分析优缺点） 如果我们将找下一个该被处死的人的操作简称为“找点”，将删除一个人后要进行的操作称为“去点”，可以看出：顺序存储结构的优点是“找点”时，可以由现在被处死的人的位置直接计算并在数组中精确定位；而缺点也很明显，就是“去点”时，都需要把它后面所有的元素整体移动一次，时间复杂度为O(n)。所以应用顺序存储结构，程序的整体时间复杂度是O(n2)。 用链式存储结构实现 用链表记录当前所有未被处死的人在原来的位置，初始值为1..2n。每处死一个人后，只要将这个结点直接从链表中删去即可，然后指针后移(m-1)次，找到下一个应该被处死的人。（注：此处插入图示3，并分析优缺点） 链式存储结构的优点是“去点”时只要修改应该被删除结点的父结点指针指向就可以了；缺点是“找点”时，需要移动(m-1)次定位指针，所以应用链式存储结构，程序的整体时间复杂度是O(nm)。 从哲学角度分析，“找点”和“去点”是存在于程序和数据结构中的一对矛盾。应用顺序存储结构时，“找点”效率高而“去点”效率低；应用链式存储结构时，“去点”效率高而“找点”效率低，这都是由数据结构本身决定的，不会随人的主观意志存在或消失。这就表明“找点”和“去点”的时间复杂度不会同时降为O(1)。我们希望有这样一种数据结构，在实现“找点”和“去点”时，使复杂度降到尽量低，在综合考虑顺序存储结构和链式存储结构的特点之后，我们设想出这样一种数据结构模型（注：插入图示4“思想模型”）， 总体思想就是在较好地实现“直接定位”的基础上，尽量避免大量元素移动。因为小规模的数据移动和指针移动，时间都可以接受，所以从总体上来说，这种数据结构的时间复杂度不会太高。实现时，我们将上面的数据结构模型做了一些小小的变动，并提出改进解法，即“优化直接定位”法。 改进解法——“优化直接定位”法 设计出的存储结构如图所示：其中group表示将原来的数据分为几段存储；每一段的开头记下的amount值表示此段中现有元素的个数。随程序的运行，amount值是不断减小的。（注：先显示图示4“实际模型”；然后手工删除，伴随讲解） “优化直接定位”法较好的体现出“直接定位”的思想，而且由于将所有的结点分为若干段之后，每次删除一个结点后，需要移动的结点数相对而言不是很多，这样就使程序效率大大提高，且m越大，这种效果越明显。 这种分段式数组可以看作是链式存储结构和顺序存储结构的结合产物，它兼具这两种存储结构的优点。 请注意，我们这里提到“结合产物”借用生物学中的部分思想——子代因为遗传作用而具有亲代的某些特征，同时又因为变异作用而与亲代存在差别（当然，我们希望这种变异总是向着好的方向的）。我们设计出的综合的数据结构应该继承了其“亲代”（即本来的未经变化数据结构）的优点，而摒弃它们的缺点。 运用了这种存储结构后，程序效率显著提高，可参见改进前后程序效率比较的表格。（注：插入表格） 引申 （注：插入“引申”） 横向延伸——约瑟夫环类的问题 如：《翻牌游戏》、《猴子选大王》 纵向延伸——数据结构的综合运用 在解决一些数据规模较大的题目时有很好的应用。如《隐藏的码字》（IOI’99）。在解决这道题目时，如果能建立起链式和顺序相结合的数据结构，程序效率就比较高。 链式和顺序相结合的数据结构实现简单，效果显著，应用比较广泛。当然还有其它的结合方式，比如二叉堆