算法与数据结构课程设计指导2011秋(信息).doc

信息科学与技术学院数 据 结 构（分册） 盐城师范学院信息科学与技术学院算法与数据结构课程组编2011.9数据结构课程设计一、概 述（一）课程设计的性质、目的与作用数据结构是计算机及其相关专业一门重要的核心课程，是学习计算机软件设计的重要基础课程。从实际工作需要来看，仅靠教学计划安排的课内实践时间是难以满足要求的，为了帮助同学扎实的掌握数据结构内容，提高运用数据结构的方法解决实际问题的能力，有计划、有目的、有系统地进行必要的实践训练，编写了数据结构课程设计这部分内容。课内的实验是侧重于对某一方面知识的学习，在解决实际问题时，可能涉及并运用多个方面的知识，具有较强的综合性，这就需要进行一些综合性的设计练习，来提高分析和解决实际应用问题的能力。数据结构课程设计的目的是利用本课程内的以及到目前为止所学到的有关知识和技术解决一些不算太复杂却具有综合性的问题。通过课程设计，在建立问题模型、构造求解算法、设计数据结构、编写程序代码及上机调试等方面得到全面的锻炼，从而能更深刻地理解数据结构的精髓，为后续软件课程的学习及软件设计能力的提高奠定良好的基础。包括，1 熟练掌握数据结构的一些常用算法和经典算法；2 熟练的运用常用的算法和经典算法解决具有一定规模和复杂程度的实际问题；3 熟练掌握分析问题和解决问题的方法，合理选择数据结构，学会分析算法的优劣，分析算法的复杂度。（二）课程设计的要求在课程设计时，对要解决的问题，要注意以下几个方面：1 正确性：设计的算法要严谨、正确，能正确解决实际问题，符合指定的要求；2 高效：有效的建立数学模型，合理的选择数据结构，编写高效的程序代码；3 清晰：算法和程序的结构要清晰，算法要用流程图来表示，程序代码要加注解；4 设计报告：每一个问题解决后，要按统一的纸张及格式，完整、整洁地写出设计报告，打印程序清单，拷贝所做设计的电子版文档和程序。（三）设计报告格式 在将综合设计作为教学的一个环节时，设计报告一般包括以下几个方面的内容：1 设计任务、要求和所用的软件环境和技术；2 设计思想及其简要说明；3 设计的算法，以及算法可能由几个模块组成，算法用流程图表示出来；4 使用说明，包括使用前提，所用软件环境，文件清单；5 验收时间，验收情况说明等；6 通过课程设计的收获以及对所用方法的分析和综合；7 打印的程序清单以及结果，结果以贴图的方式附在报告后。二、预备知识1、 线性表的顺序和链式表示和实现2、 栈和队列的表示和实现以及应用3、 递归和非递归的转化4、 串的表示和实现5、 数组的应用6、 树及其二叉树的表示、实现、遍历和应用7、 图的表示方法及其遍历和应用8、 各种查找方法的实现和分析及应用9、 各种排序方法的实现和分析和应用三、数据结构课程设计课题说明：1、不限定开发语言，Java、Jsp、Asp、C、C#、C+等都行。重在答辩。2、相同情况下，选择提高题、综合题与运用题的学生，我们给予10分鼓励分，优先给这三类学生评优。3、要突出数据结构与算法设计思路步骤，代码中的文档注释量不能低于代码量。重在业务分析、模块接口设计、数据结构设计与操作算法步骤设计。重在对分析问题、解决问题能力的培养与评定。4、课程设计报告请严格规定安格式书写电子稿，并打印，没有依格式写的课程设计报告检查后要重新打印，并扣态度分，打印前请认真检查。可供选择的数据结构课程设计题：基础题：以下选题为每题限选2人。【课题1】用贪婪法求解“货郎担问题”。所谓“货郎担问题”是指，给定一个无向图，并已知各边的权，在这样的图中，找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和为最小。【课题 2】背包问题。从N件不同价值、不同重量的物品中选取一部分物品，在不超过规定重量的情况下，使这部分物品的总价值最大。【课题 3】用十字链表表示稀疏矩阵，并实现稀疏矩阵加法。【课题 4】马的遍历问题。设计程序完成如下要求：在中国象棋棋盘上，对任一位置上放置的一个“马”均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。程序输出88方阵，用164表示走过每个位置的次序，起始点标为1。【课题 5】编写程序，初始从键盘输入二叉树的结点数据创建二叉树，并将该二叉树的数据以某种方式存储到文件btree.dat中，以便程序此后运行时从文件中读取数据构建该二叉树；要求能根据指定结点求出其在二叉树中所在的层数。【课题 6】若某算术表达式采用后置法表示（即逆波兰表达式），请编程计算该表达式的值。如：表达式(a+b*c)/d-e用后置法表示为abc*+d/e-。【课题7】最短路径问题。用有向图表示道路网，有向边上的权表示两地间的距离，要对如下图求出从c1到各点的最短路径（程序应通用）。【课题 8】若已知一棵二叉树的先序序列和中序序列（如从键盘输入），设计算法及程序实现构造其对应的二叉树。【课题9】利用二叉排序树可以实现集合的插入、删除和查找操作。编写程序统计一份英文文献中单词使用的频度。【课题 10】设计程序完成如下功能：对给定的图结构和起点，产生其所有的深度优先搜索遍历序列（深度优先搜索序列不唯一）。【课题11】设计程序完成如下功能：对给定的有向图，用Kruskal算法的基本思想求解出所有的最小生成树。【课题 12】设计程序完成如下功能：对给定的AOV网，求出该AOV网所有的拓扑序列。【课题13】设计程序以实现构造哈夫曼树的哈夫曼算法，并计算出所构造的哈夫曼树的带权路径长度。【课题14】设计一个模拟计算器的程序，要求能对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解。【课题15】选择合适的存储结构表示图，在此基础上实现求解最短路径的Dijkstra算法。【课题16】若二叉树采用二叉链表存储，利用栈实现中序线索化二叉树的非递归算法。【课题17】 设计一个简单的文本编辑器，使其具有通常编辑器（如Notepad）具备的功能。【课题18】苏州园林导游程序设计。用无向网表示苏州园林的平面图，图中顶点表示著名园林，存放园林的编号、名称、特色简介等信息，图中的边表示园林间的通路，存放路径长度等信息。要求实现以下功能：（1）根据园林名称或编号查询各园林的相关信息；（2）查询图中任意两个园林间的最短路径；（3）查询图中任意两个园林间的所有路径。【课题19】散列法的实验研究。散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。给出程序及实验数据对比、分析研究。【课题20】“吃金子”游戏在地下某处藏有金子（g），有一个精灵（）寻找并获取金子。游戏者通过输入四个方向键指挥精灵沿该方向移动去吃金子（每输入一次方向键只移动一步）；金子是随机地、每隔一段时间出现在不同的位置，游戏者需在金子消失前到达才能获取它。游戏者的成绩是看其在一定时间内获取的金子数量计算。如下图示。所需知识：数组、随机数、键盘输入码的识别-g-g-g-g-（提示：需要使用一些库函数，如：原型 int bioskey(int cmd)所属头文件 bios.h功能 返回键盘读取一个按键的ASCII值，两字节。Cmd参数说明：参数cmd确定实际的操作，cmd取值为0 返回下一个键盘输入的字符，如果低8位非0，则为ASCII码；如果低8位为0，则高8位为扩展键盘代码查PC ASCII表。1 测试是否有可读的输入键，如果返回0，则表示没有；否则返回下一个输入键。键还保存，供下次参数cmd为0的bioskey调用返回。2 请求当前移位(Shift)状态原型 void gotoxy(int x,y)所属头文件 conio.h功能 将光标移动到(x,y)坐标处。屏幕的坐标系左上角为(0,0)。）【课题21】五子棋游戏游戏者A、B对奕五子棋（规则略），百子用W、黑子用B表示，在一个n*n的棋盘上对奕，棋盘屏幕布局如下图示例。所需知识：二维数组。 123456789ABCDEFGHIJKLMNO 2 WBW 3 BWWB4 WBB Player A:X- Y- Player B:X- Y-【课题22】有若干生产者和消费者，生产者负责生产商品、每生产处一个商品就放入一个环形缓冲区中的空闲缓冲区中供消费者取商品消费，并检查是否有消费者等待取商品，若有就唤醒他；如果没有空闲的缓冲区则排入等待队列等待消费者取走商品后空出缓冲区。同样，消费者到环形缓冲区中找一个存有商品的缓冲区取商品，如果所有缓冲区均空（无商品可供消费）则排入消费者队列等待，如果有商品可取、取出商品后查看生产者队列是否有等待的生产者并唤醒他。环形缓冲区如下图所示。所需知识：环形队列、链队列。【课题23】在网吧管理中，需要在每个客户用时（下机）到达前5分钟提醒客户。由于当前上机的用户数目不确定、每个用户的下机时间不同，所以需要采用链表结构的间隔时钟进行管理。链表钟头节点中记录的时间值是相对于当前时间还需经过的时间、而后继节点中记录的时间值是相对于其前趋节点的终止时间还需经过的时间。系统设置一个时钟中断，时钟中断处理程序总是从头节点开始检查需要发布提醒信息的用户（节点）并提醒之，并修改剩余节点中的间隔时间值（减去头节点中的值）。所需知识：链表。【课题24】老鼠走迷宫。有一个n*n格的迷宫，有些格子是墙不能通过、而另一些是通道可以通行。整个迷宫有一个入口和一个出口，四周也是墙。老鼠从入口进入顺可以通行的通道前进，当遇到无法通行的墙时就需要尝试另一方向前进、直到所有方向（除了进入得方向）尝试完还不能前行，就得后退再寻找出路。所需知识：数组、回溯程序设计。提示：用数组Mazenn表示迷宫，标志数组mark用来记录已走过的位置，还要能对下一步前进方向计算出下已位置等。见下图示。入口-0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 11 0 1 1 0 0 1 1 0 0 0 1 0 1 0 11 0 0 0 1 0 0 0 0 1 0 1 0 1 0 11 0 0 0 0 0 1 1 0 0 0 1 0 1 0 11 0 0 0 0 0 1 1 1 1 0 1 0 1 0 11 0 0 0 0 0 1 1 0 0 0 1 0 1 0 11 0 0 0 0 0 1 1 0 0 1 1 0 1 0 11 0 0 0 0 0 1 1 0 0 0 0 0 1 0 11 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1【课题25】设有一算术表达式，参与运算的数据均为1位数字、并且只使用加、减、乘、除四则运算和圆括号，编程实现该表达式求值计算。所用知识：栈和字符串。提示：教材上有该题的算法，需具体实现。也可以参考其他方法。【课题26】将n个名字（每个名字步超过10个字符-可英文单词表示）建立成一个单链表，节点中包含名字、原（输入时的）序号、指向下一个节点的指针。然后将这些名字按字典顺序排序。要求：（1） 将原名单按行输出：名字、序号（2） 按排序后的名单顺序输出，包括：名字、原序号。所用知识：链表。思考：你所用的排序算法对于链表来说，性能如何？你认为哪个算法更适合链表排序？【课题27】电脑摇奖。电视台常从成千上万的电话号码中摇出获奖者，设计一种存放这些电话号码的数据结构，并设计两种或两种以上的算法对其摇奖，要求摇奖算法做到公平，比如，每次被选出的号码与号码存放的位置无关、分布均匀、每个号码的获奖机会均等。所需知识：表、查找或许还用到散列。【课题28】设计一个程序，完成以下功能：1）建立学生信息管理的数据文件stud.dat;文件中至少包含30个学生的信息；每个学生至少包括：学号、姓名、年龄、课程成绩等5项内容（另2项自定），当程序运行后发现数据文件不存在（如初始运行）、应从键盘输入学生信息数据并创建数据文件；若数据文件已经存在则从该文件中读取数据；2）可以添加（插入、追加）学生信息；3）可以修改某个学生的某项信息；4）能统计并显示某门课程不及格学生的信息。【课题29】设计一个程序，完成如下功能：从一个C语言源程序文件中，统计出该C程序中使用的关键字及其频率。统计结果表格保存到文件keyword.txt中。【课题30】偶交换排序如下所述：第一趟对所有奇数i，将ai与ai+1进行比较；第二趟对所有偶数i，将ai与ai+1进行比较，若aiai+1则进行交换；依此类推，继续对奇数i和偶数i进行上述比较和交换，直到整个序列有序为止。要求：程序在初始时从键盘输入数据，将这些数据用偶交换排序，将排序后的数据存储到文件even_sort.dat中，然后根据用户输入的关键字，将数据读入内存采用二分查找算法进行查找，若存在则输出其排序后的序号，否则显示相关信息。【课题31】拼写检查。问题描述微软的Word有一个拼写检查功能，如果你拼写错了单词，它会用红线标出以示提醒，然后给出可能正确的单词。现在要你编程实现类似的一个系统：给定一个词表以及一个待检查的单词，判断这个单词是否在词表中，如果不在词表中，程序应该给出一个相似的单词。 在寻找相似的单词时，你只需要考虑如下几个简单的情况： 1、漏写了一个字母，如把abacus误拼写为abacs 2、多写了一个字母，如把abacus误拼写为abaacus 3、将某处的一个字母写成了另一个字母，如abacus误拼写为abacup 编程实现这个系统。 输入格式输入数据的第一行是一个由小写字母组成的字符串，表示要进行拼写检查的单词 第二行是一个数N（1=N=100）,表示词表中词的数目 接下来有N行，每行都是一个由小写字母组成的字符串，代表词表中的每一个单词 所有字符串的长度在2到20之间 输出格式仅输出一个字符串： 1、如果要检查的单词在词表中出现，则原样输出该单词 2、如果要检查的单词在词表中未出现，但在词表中找到相似的单词，则输出在词表中和它相似的那个单词。如果在此表中找到多个相似单词，仅输出在输入文件中最靠前的一个。 3、如果要检查的单词在词表中未出现，并且在词表中找不到与它相似的单词，输出NOANSWER 样例输入abstaine4abacusabstractabstainabstainer样例输出Abstain【课题32】做明智的消费者。问题描述盐师里面有很多超市，但是有的商品在这个超市里便宜些，有的商品在另一个超市里便宜些。周末大购物的时候，超超想从1号超市逛到n号超市，然后把该买的东西(从1到m编号)都用最便宜的价格买到，你的任务是帮帮他决定在哪个超市应该买什么商品。输入格式输入数据第一行是两个数n m，表示有n个超市和m个该买的商品。(1=n=50 1=m=100) 接下来是nXm的矩阵Aij，其中第i行第j列表示i号超市中j商品的价格（小于100的非负整数），Aij=0则表示j商品无法在i超市找到。输入数据不能保证能买到所有商品。 输出格式输出仅一行，包括m个数B1,B2 . .Bm，依次表示第i号商品该在Bi号超市中购买。如果买不到的话Bi为0。 当然啦，如果一个商品在i号超市与j号超市购买一样便宜，超超更乐意大号超市了。嘻嘻，有兴趣的话猜猜为什么。 样例输入3 65 3 0 2 3 5 8 9 0 2 0 23 4 0 2 1 3样例输出3 1 0 3 3 2【课题33】捉羊计划。问题描述在经历了上千次失败后，灰太狼终于研制出了性能完备的捉羊机器人。灰太狼希望能利用它们抓住羊村里所有的羊，所以现在需要制定一个完美的计划。灰太狼已经获取了羊村的地图。他发现羊村由N个交叉路口和N-1条双向街道构成，而且无论从哪个交叉路口出发沿着街道走都能到达其它的任何一个交叉路口。每条街道上都有房子，每个房子中都住着羊。为了保证计划万无一失，灰太狼选择在半夜行动，因为这时所有的羊都会在自己的房子中睡觉。灰太狼计划将他制造出的K个机器人放在某个交叉路口处，机器人会沿着街道行走，并且可以在任何一个交叉路口停下，不同的机器人可以停在不同的位置。因为捉羊机器人的性能非常优秀，所以每条街道只要被一个机器人走过一次，这条街道上住着的所有羊就都会被捉住。当所有的羊都被抓住后，灰太狼的计划就成功了。机器人在街道上移动需要耗费非常多的能量。为了节约能源，灰太狼迫切想要知道所有机器人的移动路线长度之和的最小值。 输入格式输入文件包含N行。第1行包含两个正整数N、K，分别表示交叉路口的总数和机器人的个数。交叉路口的序号为1到N。第2行到第N行，每行包含三个用空格隔开的正整数A、B、C，表示有一条连接交叉路口A和交叉路口B的街道，且该街道的长度为C。输出格式输出文件包含N行，每行一个正整数，其中第i行的整数表示如果所有的机器人从序号为i的交叉路口出发，那么移动路线的长度之和最小是多少。输入样例5 31 2 72 3 53 4 143 5 8输出样例4239344242 样例说明若所有的机器人从1号路口出发，那么最优路线为： 1号机器人：123534，长度为42。2号机器人：停留在出发点。3号机器人：停留在出发点。总长度为42。若所有的机器人从2号路口出发，那么最优路线为：1号机器人：21，长度为7。2号机器人：234，长度为19。3号机器人：235，长度为13。总长度为39。若所有的机器人从3号路口出发，那么最优路线为：1号机器人：321，长度为12。2号机器人：34，长度为14。3号机器人：35，长度为8。总长度为34。数据范围对于10%的数据，N10，K2。对于20%的数据，N100，K6。对于35%的数据，N200，K12。对于50%的数据，N500，K18。对于65%的数据，N8000，K25。对于另外20%的数据，N15000，K2。对于全部的数据，N15000，K30。每条街道的长度都不超过100。【课题34】陶陶玩红警。问题描述陶陶最近开始玩红警了，他玩的是自己MOD的一个红警版本。这个版本是这样的：你只能造两样东西，战车工厂和坦克。最初你有一个战车工厂，然后在接下来的每一秒内你可以有两种选择(假设当前有k个战车工厂)：1，建造一个战车工厂；2，建造k辆坦克。注意，战车工厂和坦克是不能同时建造的。陶陶在玩了一个月红警后，认为自己红警水平很厉害了。于是他向curimit发了一份挑战书，他还嚣张地说他会对curimit发动N次攻击。第i次攻击在第timei秒末，陶陶会使用numi辆坦克来进攻，消灭掉curimit家里同等数量的坦克。如果此时curimit家里没有这么多的坦克的话，那么curimit就死翘翘了。curimit接到战书后看到看到陶陶如此强大的攻势，被吓得不轻。他想请你帮帮忙，帮他制定一份作战计划（什么时候造战车工厂，什么时候造坦克）：curimit希望在抵挡了陶陶的N轮进攻之后，在第final秒末发动最终的总攻击，一举歼灭陶陶的老家。他希望你的作战计划能够在第final秒末造出最多数量的坦克。输入格式第1行为两个整数N，final，含义如题目中所述。接下来N行，第i行有两个数timei和numi，含义如题目中所述。输出格式输出仅包含一行，如果curimit无法抵挡陶陶的进攻，那么输出“No Answer!”；否则输出第final秒末curimit最多能拥有多少辆坦克。输入样例3 105 37 139 4输出样例8样例解释第1秒：造战车工厂。第2秒：造战车工厂。第3秒：造战车工厂。第4秒：造坦克，当前坦克数：4。第5秒：造坦克，当前坦克数：8。第5秒：陶陶带了3辆坦克冲了进来，当前坦克数：5。第6秒：造坦克，当前坦克数：9。第7秒：造坦克，当前坦克数：13。第7秒：陶陶带了13辆坦克冲了进来，当前坦克数：0。第8秒：造坦克，当前坦克数：4。第9秒：造坦克，当前坦克数：8。第9秒：陶陶带了4辆坦克冲了进来，当前坦克数：4。第10秒：造坦克，当前坦克数：8。在第10秒末，curimit家里最多有8辆坦克。数据范围10%的数据中N5，final10；30%的数据中N1000，final1000；100%的数据中N100000，final109，0numi1018；100%的数据中1time1【课题35】光棱坦克。问题描述一个平面直角坐标系上，有N个点，标号为1到N，其中第i个点的坐标为(xi, yi)。求满足以下两个条件的点列pi的数目（假设pi的长度为M）：1) 对任意1 = i j ypj；2) 对任意3 = i = M，必有xpi-1 xpi xpi-2或者xpi-2 xpi xpi-1。求满足条件的非空序列pi的数目，结果对一个整数Q取模。 输入格式第1行是两个由空格隔开的整数：N和Q。第2行到第N+1行，每行有两个整数。其中的第i行的两个整数分别是xi和yi。 输出格式输出文件只有一行，包含一个整数，表示序列pi的数目对Q取模的结果。 输入样例4 1002 23 11 44 3 输出样例14样例说明一共4个点，位置如下：如果M=4, 那么只有1种序列符合要求,如下图所示：如果M = 3，那么有3种序列符合要求，如下图：如果M = 2，那么有6种序列符合要求，如下图：如果M = 1，也就是点列只包含一个点的情况。那么有4种序列。明显都符合要求。所以一共就有1 + 3 + 6 + 4一共14种序列符合要求。数据范围对于25%的数据，N = 50；对于40%的数据，N = 700；对于60%的数据，N = 2000；对于70%的数据，N = 4000；对于100%的数据，1 = N = 7000。对于100%的数据，有1 = Q = 1000000000。对于50%的数据，保证对任何的i，xi和yi是1到N之间的整数；对于100%的数据，保证对任何的i，xi和yi都是1到2000000000之间的整数。对于100%的数据，保证有当i != j时，有xi!= xj且yi!= yj。【课题36】Ekaterinburg城到Sverdlovsk城有直线形的铁路线。两城之间还有其他一些停靠站,总站数为N。各站按照离Ekaterinburg城的距离编号。Ekaterinburg城编号为1，Sverdlovsk城编号为N。给定起点站和终点站，求出要从起点到终点最少要花多少钱。某两站之间车票价格由这两站的距离X决定. 当0X=L1时，票价为C1元. 当L1X=L2时，票价为C2元. 当L2X=L3时，票价为C3元.当两站距离大于L3时没有直达票，所以有时候要买几次票做几次车才行。比如，在上面的例图中，2-6没有直达票，有几种买票方法可以从2-6，其中一种是买C2元的2-3车票，再买C3元的3-6车票。【课题37】单词争霸。问题描述农夫约翰(Farmer John)的奶牛们平时喜好一起学习英文单词。奶牛Bessie是其中最聪明的牛，她发明了一个游戏，叫做单词争霸。这个游戏是由两个人来玩，两人轮流进行。轮到每个人时，他要说出一个正确的单词（即字典中的单词），要求这个单词在之前没有被他或他的对手说过，并且这个单词不是之前他或他的对手说过的某个单词的前缀。如果轮到一个人，他无法说出这样的单词，那么他被判败。显然，拥有词汇量较多的奶牛玩起这个游戏来更有优势，因为他有更多的单词可以说。这样，奶牛们天天玩这个游戏，他们的词汇量越来越大直到有一天，Bessie发现他们已经把世界上所有的英文单词学会了，因此她再也无法依赖自己较大的词汇量取胜了。她是记忆单词的天才，但并不是游戏好手，所以她来请教聪明的你。她告诉你，这个世界上一共有N个英文单词，每个单词的长度不超过maxLen。她将这些单词按字典序排列，并输入。她想知道如果她是先手，那么她是否能取得胜利。你需要做的是，判断在给定字典的情况下，先手是否有必胜策略。如果没有，那么告诉Bessie:“Cant win at all!”，否则，你需要确定先手在第一回合可以说出哪些单词，为了让Bessie多一些思考的乐趣，你决定不把这些单词一一列举。你把这些单词按某个排列连接起来，组成一个大的字符串，当然，不同的排列可能得到不同的串，你要告诉Bessie那个字典序最先的串，记作answerString。为了使输出更加美观，如果那个串的长度大于50,你要分行输出，除了最后一行以外，其他行每行50个字符，最后一行不多于50个字符。 输入格式输入的第一行包含两个整数,N和maxLen,用一个空格隔开。接下来的N行，每行为一个长度不大于maxLen的字符串。 输出格式按题目描述中的要求输出：可能为一行,“Cant win at all!”(不包含引号)或者多行，除了最后一行之外每行50个字符，最后一行不超过50个字符，将所有行的字符连接起来是answerString。样例输入12 9wordwordcraft样例输出1wordcraft样例1解释先手说出单词“wordcraft”之后,后手没有单词可说，因为单词“word”是单词“wordcraft”的子串。样例输入25 9accarcarecarefulcarefully样例输出2careful样例2解释先手说“careful”之后，后手只能说“ac”或者“carefully”。如果他说了前者，那么先手说后者；反之，如果他说了后者，那先手说前者。之后，后手都将无单词可说。样例输入32 100noonecansolvethisproblemthisproblemisverydifficult样例输出3Cant win at all!样例输入49 8 thewordathewordbthewordctheworddthewordethewordfthewordgthewordhthewordi 样例输出4thewordathewordbthewordctheworddthewordethewordfthewordgthewordhthewordi 数据范围输入数据中的所有单词均由小写字母构成。输入数据保证所有单词按字典序排列。输入数据保证所有单词互不相同。10%的数据中N20,maxLen20；30%的数据中N500,maxLen50；50%的数据中N2000,maxLen50；70%的数据中N5000,maxLen100；100%的数据中N100000,maxLen100。【课题38】As the new term comes, the Ignatius Train Station is very busy nowadays. A lot of student want to get back to school by train(because the trains in the Ignatius Train Station is the fastest all over the world). But here comes a problem, there is only one railway where all the trains stop. So all the trains come in from one side and get out from the other side. For this problem, if train A gets into the railway first, and then train B gets into the railway before train A leaves, train A cant leave until train B leaves. The pictures below figure out the problem. Now the problem for you is, there are at most 9 trains in the station, all the trains has an ID(numbered from 1 to n), the trains get into the railway in an order O1, your task is to determine whether the trains can get out in an order O2. InputThe input contains several test cases. Each test case consists of an integer, the number of trains, and two strings, the order of the trains come in:O1, and the order of the trains leave:O2. The input is terminated by the end of file. More details in the Sample Input.OutputThe output contains a string No. if you cant exchange O2 to O1, or you should output a line contains Yes., and then output your way in exchanging the order(you should output in for a train getting into the railway, and out for a train getting out of the railway). Print a line contains FINISH after each test case. More details in the Sample Output.Sample Input3 123 3213 123 312 Sample OutputYes.inininoutoutoutFINISHNo.FINISH【课题39】Starting from a positive interger n(1=n=2001). On the left of the integer n, you can place another integer m to form a new integer mn, where m must be less than or equal to half to half of the integer n. If there is an integr k less than or equal to half of m, you can place k on the left of mn to form a new integerkmn,，and so on. For example, you can place 12 on the left of 30 to form an integer 1230, and you can place 6 to the left of 1230 to form an integer 61230,，and so on.For example, start from n=8.You can place integers 1, 2,3 and 4 to the left of 8 to get integers 18, 28, 38, 48.For number 18, you can form a new integer using the procedure described as above.For number 28 and 38, you can form new integrers 128 and 138.For number 48, you can place 1 and 2 on the left of 48 to get new intergers 148 and 248.For number 248, you can place 1 on the left of it to get a new integer 1248.In total, you can have the following 10 integers(including the integer you start with):8182838481281381482481248Given an integer n, find the number of integers you can get using the procedure described above.Input: An integer nOutput: An integer which represents the number of integers you can get.Sample Input:8Sample Output:10【课题40】求01矩阵中最大的全零矩形 给定一个M*N的 01矩阵，求其中全部由0组成的面积最大的矩形（输出面积即可）。【课题41】营业额统计 给定N（1N32767）天的营业额a1,a2,a3,an. 定义最小波动值：该天的最小波动值=min|该天以前某一天的营业额-该天营业额|. 特别地，第一天的最小波动值即为a1.试求N天的最小波动值之和。【课题42】瑰丽华尔兹 给定一个N行M列的矩阵，矩阵中的某些方格上有障碍物。有一个人从矩阵中的某个方格开始滑行。每次滑行都是向一个方向最多连续前进c格（也可以原地不动）（两次滑行的c值不一定相同）。但是这个人在滑行中不能碰到障碍物。现按顺序给出K次滑行的方向（东、南、西、北中的一个）以及对应的c，试求这个人能够滑行的最长距离（即格子数）。数据范围：1N,M200，K200， 40000 提高题：以下选题为每题限选2人。【课题1】对给定文档，依据下面的思想设计聚类算法，并实现，输出聚类结果。无向加权图G=V，E，W，V=d1，d2，dn；其表示形式为一对称矩阵：wijnn，其中W=w1，w2，wm是边权重代表两个文本间相似度。计算文档的词频以及文档间的相似度，将文档粗化的聚成无关或是相关度极小的c个文档子类。首先除去在所有文档中出现的高频词；然后提取剩下词汇的短语存入词根表中。收集这些短语形成一个索引短语集T。短语t在文档di中权重为：tfit定义为短语t在文档中di出现的频率；dft定义为含有短语t的文档数量；L定义为文档di中包含的索引短语的数量；N定义为文档的数量。p_term_documen（tt，di）的值代表着短语t在文档di中的重要性，取值范围是0，1。计算出短语的权重，可以将短语表示成向量：di=（wi1，wi2，wis），其中0wij1，s代表索引短语表中词的数量。则两个文档di与dj的相似度可定义为： 由Wij=sim（di，dj），建立模糊相似矩阵WRnn，其中当i=j时，令Wii=0。由相似矩阵求得传递闭包t(W)，选取一个合适的值得到一个截集，得到的将是一个0，1矩阵，记为t(R)。由此矩阵可以分成c个文档类，即A=A1，A2，Ac，满足了文档类间的相似性极小，将c个文本集看成c个子图。判断各个文档子类中如果存在只有一个文档的类，将其并入其他与其相似度最高的子类中，变成c*个子图。输入c*个子图，用基于谱图分割简单的谱聚类算法对每个子图G的顶点集Vk=（v1，v2，vn）进行聚类，得到每个子图的聚类结果及其对应的类别数ki，其中i1，c*。计算出ki的和即为总的聚类数K。输入一个数据集X=x1，x2，xk，输出由以上的数据集分割出来的k个子集。计算每个子图的亲密矩阵S，当ij时，Sij=exp（-d（xi-x）j/22），Sii=0。构造Laplacian矩阵L，L=D-1/2SD-1/2，其中D为对角阵。计算L的前k个特征值特征向量1，2，k（重复特征值取其互相正交的特征向量），按照大小顺序将相应的特征向量排列构成矩阵U=1，2，kRnk，初始化聚类数m=2。令ki=m。取U的前ki个列向量构成矩阵Y，即Y=U（：，1：k），归一化Y为矩阵V，其中在ki维空间里，每个坐标轴的正负方向分别标记一个聚类。把V的行向量看作是ki维空间的点，将其标记为距离最近的坐标轴所标记的聚类。这样最多可以产生2ki个聚类。除去空聚类和只有少数点的聚类，可以得到此时的聚类数m2k。比较m和ki，如果两者不等，重复上面过程。如果m=ki，则所得到的m就是确定的聚类数，同时得到相应聚类数下V的行向量聚类。当且仅当V的第i行为聚类j时，则原始数据点xi为第j类。计算ki的和得到总的聚类数k，和聚类结果。【课题2】依据给定值，求解下面方程x的近似计算解。a iai，m为a0-an的平均值。( a im) a92=74,72,69,62,64,61,74,70,64,74,46,82,60,86,70,67,70,68,60,65,62,73,60,60,80,71,68,60,81,60,74,70,55,76,88,51,82,68,80,63,65,47,72,62,60,68,81,43,60,69,76,72,72,68,68,60,75,40,60,78,82,75,67,60,60,95,69,65,64,60,60,64,62,72,66,42,74,71,81,70,77,63,69,41,65,69,73,60,69,80,81,75。【课题3】设计一套CUP与内存使用率实时监控与利用软件，能依据计算机CUP与内存使用率实时调整对给定数据处理算法的采样率，保证最大限度地充分利用CUP与内存进行对给定数据的实时处理（即数据处理速度不变，如1000条数据/秒）。【课题4】对给定数据，依据下面的思想设计两数据集相似性算法，并实现，输出相似度。设给定数据集用期望Ex、熵En和超熵He来表征，期望Ex反映给定数据集的确定性，代表给定数据集的最典型抽象样本；熵En反映给定数据集的不确定性，代表给定数据集的可被接受的取值范围（集中性），也即给定数据集的离散程度；超熵He给定数据集的取值范围的稳定性，也即给定数据集的取值范围的凝聚性。分析以下两数据集的确定性、集中性和稳定性，进而由此分析该两数据集的相似度。设样本点xi，如给定数据集所示。1、根据xi计算样本的平均值，一阶样本绝对中心矩，样本方差；2、Ex=；3、En=；4、He=a92=74,72,69,62,64,61,74,70,64,74,46,82,60,86,70,67,70,68,60,65,62,73,60,60,80,71,68,60,81,60,74,70,55,76,88,51,82,68,80,63,65,47,72,62,60,68,81,43,60,69,76,72,72,68,68,60,75,40,60,78,82,75,67,60,60,95,69,65,64,60,60,64,62,72,66,42,74,71,81,70,77,63,69,41,65,69,73,60,69,80,81,75a92=64,62,69,62,64,61,84,70,64,74,46,82,60,86,70,67,77,68,60,65,62,73,60,60