《算法分析与设计》实验指导书.doc

《《算法分析与设计》实验指导书.doc》由会员分享，可在线阅读，更多相关《《算法分析与设计》实验指导书.doc（21页珍藏版）》请在三一文库上搜索。

1、算法分析与设计实验指导书重庆邮电大学应用技术学院二八年四月算法分析与设计实验目的与要求一、实验目的算法分析与设计是信息与计算科学专业中一门重要的专业课程。当用计算机来解决实际问题时，就要涉及到对实际问题进行抽象模拟，也就是数学建模的过程，然后再设计相应的解决算法来解决实际问题，还要验证所设计的算法能够在可忍受或可达到的时间和空间内完成任务，因此算法的分析与设计就成了非常重要的环节。通过理论课的学习，我们知道要想设计一个算法必须从算法设计-算法确认-算法分析-编码-检查-调试-计时，七大步骤严格执行，所以读者可严格按照以上步骤进行，为以后进行算法研究的工作打下坚实的基础。二、实验要求1准备好上机

2、所需要的程序，并经人工检查后才能上机，以提高上机效率。对程序中自己有疑问的地方应作记号，以便在上机时给予注意。不得抄别人所编的程序。 2上机输入并调试所编的程序。 3上机结束后，提交实验报告，实验报告应包括以下内容：（1）题目；（2）算法的基本思想描述；（3）算法分析；（4）主要数据结构描述；（5）程序流程图； （6）程序清单；（7）运行的结果；（8）对运行情况所作的分析以及本次调试程序所取的经验。如果程序未通过，应分析其原因。三、实验步骤1问题分析和任务的定义明确问题要求做什么，限制做什么（本步强调做什么，而不是怎么做）。对问题的描述应避开算法和所涉及的数据类型，而是所完成的任务做出明确的回

3、答。如输入数据的类型、值的范围以及输入的形式；输出数据的类型、值得范围及输出的形式；这异步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据。2 数据类型和系统设计在设计这一步骤中分为逻辑设计和详细设计两步实现。逻辑设计指的是，为问题的描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统的功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据的封装，基本操作的规格说明尽可能的明确和具体。作为逻辑设计的结果。应写出每个

4、抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明），各个主要模块的算法，并画出模块之间的调用关系图。详细设计的结果是对数据结构和基本操作的规格说明做出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类C语言写出函数形式的算法框架。3 编码实现和静态检查4 上机准备和上机调试5 总结和整理实习报告四、实验总结对实验中发现的问题，调试中的问题分析、解决方法，对算法的改进意见、建议、收获、体会等。实验报告参考规范：实验题目班级 姓名 学号 日期一、 需求分析1 程序的功能；2 输入输出的要求；3 测试数据。二、 概要设计1 本程序所用的抽象数据类型的定义；2 主程序的流程及

5、各程序模块之间的层次关系。三、 详细设计1 采用c语言定义相关的数据类型；2 写出各模块的伪码算法；3 画出函数的调用关系图。四、 调试分析1 调试中遇到的问题及对问题的解决方法；（编译错误与运行错误）2 算法的时间复杂度和空间复杂度。五、 运行结果1、 程序的使用说明2、 运行结果六、 实验完成后的思考1、 通过实验学到了什么、理解了什么2、 程序还有哪些不足或还有哪些需要完善的地方七、 源程序（带注释）实验一斐波那契数列实验目的1 掌握递归算法及其编程方法；实验课时总课时：2学时/1次实验内容1 利用递归方法或非递归方法实现求斐波那契数列第n项的值斐波那契数列描述如下：F(n)=f(n-1

6、)+f(n-2)F(1)=1F(2)=12 根据算法编制代码（C/C+语言编写，环境可选TC2或VC6）3 调试代码直至得出正确结果实验要求一、 输入一个值n，能够得出第n项的斐波那契数列值，当n值不是一个合法值时，给出提示（越详细越好）二、 程序能够循环输入值n三、 程序有退出键四、 下课前提交word文档，内容包括程序代码、运行结果截图（正确的和错误的n值）实验二实验目的1、 掌握基础算法分析和编程方法；实验课时总课时：2学时/1次实验内容1完成下列程序* *.*. *.*.*. *.*.*.*. *.*.*.*.*. *.*.*.*.*.*. *.*.*.*.*.*.*. *.*.*.*

7、.*.*.*.*.实验要求一、 下课前提交word文档，内容包括程序代码、运行结果截图实验三排序实验目的1.、掌握排序算法分析和编程方法；实验课时总课时：2学时/1次实验内容1完成下列程序，实现对数组的降序排序 #include void sort( ); int main() int array=45，56，76，234，1，34，23，2，3； /数字任意给出 sort( ); return 0; void sort( ) 实验要求一、方法不限，下课前提交word文档，内容包括程序代码、运行结果截图实验四螺旋数列实验目的1.、掌握算法分析和编程方法；实验课时总课时：2学时/1次实验内容如图

8、： 7 8 9 10 6 1 2 11 5 4 3 12 16 15 14 13 设“1”的坐标为（0，0） “7”的坐标为（1，1） 编写一个小程序，使程序做到输入坐标（X,Y）之后显示出相应的数字。 实验要求一、方法不限，下课前提交word文档，内容包括程序代码、运行结果截图实验五六七八实验目的1.、掌握算法分析和编程方法；实验课时总课时：2学时/1次，共8学时实验内容在下面的题目中任选40分的题作为实验五六七八的实验内容。1、（15分）要求：随机产生一个字符串，每次产生的字符串内容，长度都不同2、（15分）将整数转换成字符串：char* itoa(int); 例如itoa(-123)则返

9、回“-123”;3、（15分）设计函数 int atoi(char *s)。atoi()会扫描参数s字符串，跳过前面的空格字符，直到遇上数字或正负符号才开始做转换，而再 遇到非数字或字符串结束时()才结束转换，并将结果返回。返回值 返回转换后的整型数。4、（15分）并编写一个函数实现一个整数到二进制数的转换，如输入6，输出110。5、（15分）写函数将一个字符串反转. 函数原型如下:char *reverse(char *str);6、（15分）写一个函数将一个链表逆序. 比如一个链表是这样的: 1-2-3-4-5 通过反转后成为5-4-3-2-17、（25分）题目描述：一个正整数有可能可以被

10、表示为 n 个连续正整数之和，如： 15=1+2+3+4+5 15=4+5+6 15=7+8 请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。 输入数据：一个正整数，以命令行参数的形式提供给程序。 输出数据：在标准输出上打印出符合题目描述的全部正整数序列，每行一个序列，每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列，按各序列的最小正整数的大小从小到大打印各序列。此外，序列不允许重复，序列内的整数用一个空格分隔。如果没有符合要求的序列，输出 “NONE” 。 例如，对于 15 ，其输出结果是： 1 2 3 4 5 4 5 6 7 8 对于

11、 16 ，其输出结果是： NONE 8、（25分）题目描述 为了在紧张的上班时间让员工们轻松些，百度休息室里放置着按摩椅、 CD 、高尔夫套装和 Wii 游戏机等休闲用品。其中最受欢迎的当然是游戏机。 wii 游戏机每个手柄需要使用两节电池（这两个电池可以是不同的品牌）。工程师们在玩游戏时。如果手柄没有电，他们都是将其中没电的电池拿走，并换上一个全新的电池，有电的必须继续使用。 例如，已知三种电池的使用时间分别为 3 小时、 5 小时和 8 小时。一开始，工程师使用 3 小时和 5 小时的电池。 3 小时后，换上一个 8 小时的，再过 2 小时后，手柄再次没电时，已经没有电池可用了。但如果一开

12、始就使用那个 8 小时电量的电池，可以玩满 8 个小时。 告诉你每个品牌电池的使用时间以及该品牌电池的个数，请计算工程师们玩游戏时间的最小值和最大值。输入格式输入第一行为一个正整数 n ，表示电池的种数。接下来 n 行，每行两个整数 L 和 F ，表示使用时间为 L 的电池有 F 个。输出格式输出仅一行，包含两个整数，分别表示工程师们的最短游戏时间和最长游戏时间（短的时间在前）。两个整数之间以空格隔开。 输入样例 3 3 2 5 2 8 2 输出样例 5 8 9、（25分）题目描述 “ 叉烧鸡翅膀，我呀最爱吃！ ” 百度 spider 组的 “ 黑龙潭之行 ” 在烤着鸡翅，唱着星爷的经典时达到

13、高潮。大家在篝火旁围成一圈，开始玩 “ 数 7 ” 加强版游戏，规则如下： 规则 1 ： 遇 7 的倍数或含 7 的数时 pass 。 规则 2 ： 遇有包含相同数字的数时 pass 。注意相同数字不必相邻。例如 121 。 数错的惩罚很残酷 吞食烤全羊。为避免惩罚，百度工程师们需要你 史上最强程序员的帮助。百度工程师想知道： req1 x ：符合规则 1 的第 x 个数是什么？ req2 y ：符合规则 2 的第 y 个数是什么？ req12 z ：同时符合规则 1 、 2 的第 z 个数是什么？ query n ：数 n 是规则 1 中的第几个数，是规则 2 中的第几个数？ 输入格式 输入

14、的每一行为一个查询，由一个查询词和一个无符号整型数组成。共有四种查询，查询词分别为 req1 、 req2 、 req12 、 query （区分大小写）。 输出格式 前三种查询输出一个无符号整型的解。对于 “ query n ” 的查询，若 n 是规则中的数则输出相应的解，否则输出 -1 。 输入样例 req1 10 req2 10 req12 10 query 14 输出样例 11 10 12 -1 13 补充说明 输入数据共分五组，前四组中： 1=x=10000000,1=y1000000,1=z250000, 1=n24000000. ；第五组中的 y 可能达到 5000000 10、

15、（40分）饭团的烦恼“午餐饭团“是百度内部参与人数最多的民间组织。 同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。 参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。 但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。 饭团点菜的需求如下： 1 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助

16、，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。 2 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。 3 请紧记，百度饭团在各大餐馆享受 8 折优惠。 输入数据描述如下： 第一行包含三个整数 N ， M ， K （ 0N=16 ， 0M=N ， 0K=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。 紧接着 N 行，每行的格式如下： 菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否） 例： 水煮鱼 30

17、 1 1 紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。 输出数据： 对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。 说明： 1 结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。 2 每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。 输入样例 3 2 2 水煮鱼 30 1 1 口水鸡 18 1 1 清炖豆腐 12

18、0 0 1 1 1 1 输出样例 口水鸡 清炖豆腐 12.00 11、（40分）题目名称：蝈蝈式的记分 内容描述： 蝈蝈小朋友刚刚学会了 0-9 这十个数字 , 也跟爸爸妈妈来参加百度每周进行的羽毛球活动。但是他还没有球拍高，于是大人们叫他记录分数。聪明的蝈蝈发现只要记录连续得分的情况就可以了，比如用“ 3 2 4 ” 可以表示一方在这一局中连得三分后，输了两分，接着又连得到四分。可是，后来大人们发现蝈蝈只会用 0-9 这十个数字，所以当比赛选手得分超过 9 的时候，他会用一个 X 来表示 10 完成记分。但问题是，当记录为“ X 3 5 ” 的时候，蝈蝈自己也记不起来是一方连续得到十三分后，

19、再输五分；还是先赢十分输三分再赢五分。 因为百度内部就要开始进行羽毛球联赛了，要先摸清大家的实力才好分组比赛呢于是，大人们想知道以前每局的比分是怎样的，以及谁获得了胜利。要是遇到了根据比赛记录无法确认比赛进程的情况，也要输出相应的提示哦。 需要帮蝈蝈进一步说明的是，比赛是五局三胜的，每局先获得二十一分的为胜，但是胜方必须领先对手两分或以上，否则必须继续比赛直到一方超出对手两分为止，比分多的一方获胜。任何一方先获得三局的胜利后就获得胜利，比赛也相应的结束。而且蝈蝈保证是完整的无多余信息的记录了比赛。 输入数据： 以 point.in 为输入文件，文件中首行只有一个整数 M ，表示蝈蝈记录了多少场

20、比赛的分数。每场比赛用两行记录，第一行是一个整数 N(N=1000) 表示当前这个记录中有多少个字符，第二行就是具体的 N 个字符表示记录的分数。 输出数据： 相应的内容将输出到 point.out 文件中，对应每一个分数记录，输出相应的每局分数，每局分数都使用两个整数表示，表示两个选手的得分，中间用 : 分隔开；每组分数记录间使用一个空行分隔开。如果相应的比赛结果无法预测的时候，以” Unknown “一个单词独占一行表示。 ?输入和输出结果数据样例： Sample Input ： 3 23 9 7 3 6 2 4 7 8 3 2 7 9 X 2 2 1 2 1 X 1 X 1 1 25 9

21、 3 8 5 4 8 3 9 8 4 X X X X 2 X X X X 2 8 4 9 2 4 43 7 7 7 7 7 3 4 5 6 7 6 5 4 2 1 3 5 7 9 7 5 3 1 3 0 9 9 3 9 3 2 1 1 1 5 1 5 1 5 1 5 5 1 Sample Output ： 21:17 24:22 21:3 Unknown 21:14 20:22 21:23 21:16 21:9 12、（40分）变态的比赛规则 为了促进各部门员工的交流，百度 (baidu) 举办了一场全公司范围内的 拳皇友谊赛 ，负责组织这场比赛的是百度的超级 拳皇 迷 W.Z. W.Z 不想

22、用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。 由于一些员工（比如同部门或者相临部门员工）平时接触的机会比较多，为了促进不同部门之间的交流， W.Z 希望员工自己组成不同组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人则之间不会打任何比赛。 比如 4 个人，编号为 1-4, 如果分为两个组并且 1,2 一个组， 3 ， 4 一个组，那么一共需要打四场比赛： 1 vs 3,1 vs 4,2 vs 3,2 vs 4. 而如果是 1,2,3 一组， 4 单独一组，那么一共需要打三场比赛 : 1 vs 4,2 vs 4,3 vs 4. 很快 W.Z 意识到，这样的比赛规则可能会让

23、比赛的场数非常多。 W.Z 想知道如果有 N 个人 , 通过上面这种比赛规则，总比赛场数有可能为 K 场吗？比如 3 个人，如果只分到一组则不需要比赛，如果分到两组则需要 2 场比赛 , 如果分为三组则需要 3 场比赛。但是无论怎么分都不可能只需要 1 场比赛。 相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助 W.Z 吧。 输入 每行为一组数据，包含两个数字 N, K 。 (0N=0) 输出 对输入的 N,K 如果 N 个员工通过一定的分组方式可能会一共需要 K 场比赛，则输出 YES, 否则输出 NO, 每组数据占一行。 所有的输入输出均为标准输入输出。 例子 输入文

24、件 : 2 0 2 1 3 1 3 2 输出 : YES YES NO YES 13、（40分）剪刀石头布 N 个小孩正在和你玩一种剪刀石头布游戏。 N 个小孩中有一个是裁判，其余小孩分成三组（不排除某些组没有任何成员的可能性），但是你不知道谁是裁判，也不知道小孩们的分组情况。然后，小孩们开始玩剪刀石头布游戏，一共玩 M 次，每次任意选择两个小孩进行一轮，你会被告知结果，即两个小孩的胜负情况，然而你不会得知小孩具体出的是剪刀、石头还是布。已知各组的小孩分别只会出一种手势（因而同一组的两个小孩总会是和局），而裁判则每次都会随便选择出一种手势，因此没有人会知道裁判到底会出什么。请你在 M 次剪刀石

25、头布游戏结束后，猜猜谁是裁判。如果你能猜出谁是裁判，请说明最早在第几次游戏结束后你就能够确定谁是裁判。 输入格式： 输入文件包含多组测试数据。每组测试数据第一行为两个整数 N 和 M （ 1 N 500 ， 0 M 2000 ），分别为小孩的个数和剪刀石头布游戏进行的次数。接下来 M 行，每行两个整数且中间以一个符号隔开。两个整数分别为进行游戏的两个小孩各自的编号，为小于 N 的非负整数。符号的可能值为“ = ”、“ ”和“ ”，分别表示和局、第一个小孩胜和第二个小孩胜三种情况。 输出格式： 每组测试数据输出一行，若能猜出谁是裁判，则输出身为裁判的小孩的编号，并输出在第几次游戏结束后就能够确定

26、谁是裁判。如果无法确定谁是裁判，或者发现剪刀石头布游戏的胜负情况不合理（即无论谁是裁判都会出现矛盾），则输出相应的信息。具体输出格式请参考输出样例。 输入样例： 3 3 01 12 20 3 5 01 12 02 4 4 01 23 1 0 输出样例： Can not determine Player 1 can be determined to be the judge after 4 lines Impossible Player 0 can be determined to be the judge after 0 lines 说明： 共有 5 个测试数据集，每个测试数据集为一个输入文件

27、，包含多组测试数据。每个测试数据集从易到难分别为 5 、 10 、 15 、 30 和 40 分，对每个测试数据集分别执行一次程序，每次必须在运行时限 3 秒内结束程序并输出正确的答案才能得分。 所有数据均从标准输入设备（ stdin/cin ）读入，并写出到标准输出设备 （ stdout/cout ）中。 五个测试数据集中输入 N 分别不大于 20 、 50 、 100 、 200 和 500 ，各有 10 组测试数据。 14、（40分）座位调整 题目描述： 百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决

28、定进行一次员工座位的大调整。 调整的方法如下： 1 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。 2 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。 3 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。 数据输入： 第一行包含两个整数 N ， M ，（ 1=N ， M=300 ）。分别表示 N 个区域和 M 个员工。 第二行是 N 个整数构成的数列 a ，其中 ai 表示第 i 个区域可以容纳的员工数， (

29、1=ai=M ， a1+a2+.+aN=M) 。 紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。 答案输出： 对于每个测试数据，输出可以达到的最大的喜好程度。 输入样例： 3 3 1 1 1 100 50 25 100 50 25 100 50 25 输出样例： 175 数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175 15、（40分）百度语言翻译机 时限 1s 百度的工程师们是非常注重效率的，在长期的开发与测试过程中，他们逐渐创造了一套他们独特的缩率语。他们在平时的交谈，会议

30、，甚至在各中技术文档中都会大量运用。 为了让新员工可以更快地适应百度的文化，更好地阅读公司的技术文档，人力资源部决定开发一套专用的翻译系统，把相关文档中的缩率语和专有名词翻译成日常语言。 输入数据： 输入数据包含三部分 1. 第一行包含一个整数 N （ N=10000 ），表示总共有多少个缩率语的词条。 2. 紧接着有 N 行的输入，每行包含两个字符串，以空格隔开。第一个字符串为缩率语（仅包含大写英文字符，长度不超过 10 ），第二个字符串为日常语言（不包含空格，长度不超过 255 ） . 3. 从第 N+2 开始到输入结束为包含缩略语的相关文档。（总长度不超过 1000000 个字符） 输出

31、数据： 输出将缩率语转换成日常语言的文档。（将缩率语转换成日常语言，其他字符保留原样） 输入例子： 6 PS 门户搜索部 NLP 自然语言处理 PM 产品市场部 HR 人力资源部 PMD 产品推广部 MD 市场发展部 百度的部门包括 PS ， PM ， HR ， PMD ， MD 等等，其中 PS 还包括 NLP 小组。 输出例子： 百度的部门包括门户搜索部，产品市场部，人力资源部，产品推广部，市场发展部等等，其中门户搜索部还包括自然语言处理小组。 注意： 1 输入数据中是中英文混合的，中文采用 GBK 编码。 2 为保证答案的唯一性，缩率语的转换采用正向最大匹配（从左到右为正方向）的原则。请

32、注意输入例子中 PMD 的翻译。 16、（40分）百度的高级搜索方法 题面描述： 你尝试过在百度上使用 site inurl 语法查询吗 ? 如果还没有的话可以试一下 :) 如输入 site: inurl:news 则会搜出所有在 站点上的包含 news 子串的 url 。 现在我们有两份数据，一份是 site_inurl.txt 一份是 url.txt site_inurl.txt 中每行是一个 site inurl 语法组成的查询串， url.txt 中保存的是 url 列表。 你能否在 url 列表中找出所有能被 site_inurl.txt 中的查询串检索到的 url? 如 site

33、_inurl.txt 内容如下： site: inurl:/more site: inurl:/browse/ site: inurl:www20041223am url.txt 内容如下： http:/ http:/ http:/ http:/ http:/ http:/ http:/ 则你的程序运行完输出的结果应该为： http:/ http:/ http:/ 程序以命令行形式传入这两个文件名，第一个参数为 site_inurl 文件对应的文件名，第二个参数为 url 列表对应的文件名，程序的输出请输出到标准输出。17、（40分）实习生小胖的百度网页过滤器 题目描述 百度网页采集器 (Ba

34、iduspider) 每天从互联网收录数亿网页，互联网的网页质量参差不齐。百度的工程师们每天都在改进方法来判断一个网页质量的好坏，使质量差的网页出现在检索结果中较后的位置。现在实习生小胖想到一个很简单的方法来判断一个网页内容的好坏，方法如下： 1. 利用数据挖掘技术在互联网语料库中挖掘出一批有特点的词汇，分为好词和坏词两种，好词标上正的权重，坏词标上负的权重； 2. 通过好词和坏词词典对每个网页计算网页总权重：从第一个字开始匹配，找到一个好词则加上相应的权重，找到一个坏词则减去相应的权重，下一次匹配将从找到的词末尾的下一个位置开始。 3. 坏词采用正向最短匹配：从当前匹配位置开始的若干连续汉字

35、，如果形成多个坏词，则只计算最短的那个坏词的权重，下一次匹配将从这个最短坏词末尾的下一个位置开始。 4. 好词采取正向最长匹配：从当前匹配位置开始的若干连续汉字，如果形成多个 “ 有效 ” 好词，则只计算最长 “ 有效 ” 好词的权重，下一次匹配从这个最长 “ 有效 ” 好词末尾的下一个位置开始。 5. “ 无效 ” 好词的定义：好词的一部分本身是一个坏词；或者好词的一部分与后续相邻的若干字组成一个坏词。 现在小胖已经做好了第 1 步的工作，有一个好词和坏词的列表（词典），但是由于没有对中文文本处理的程序经验，他想请未来的百度之星们帮他完成这个程序。 输入格式 输入第一行为一个字符串（网页正文

36、）。从第二行开始为词典，格式为 “ 词 空格 词的权重 ” 。权重为一个带符号 32 位整数。如果权重为正，则为好词，反之则为坏词；不存在重复的词，不存在权重为 0 的词。 测试数据中的词全部为 1-5 个字的中文，但作为 “ 网页 ” 的字符串中同时包含中文和 ASCII 字符，每个汉字占 2 个字节。并非 “ 网页 ” 中的所有字都在词典中。 样例输入 小胖之喷火龙骑士 ! 小胖 6 喷火 -1 喷火龙 -1 火龙 -1 龙 4 龙骑 3 龙骑士 2 骑士 -2 士 3 输出格式 输出仅一行，为网页总权重（答案保证不超过带符号 32 位整数的范围）。 样例输出 7 样例解释 从 “ 网页

37、” 中找到的好词为 “ 小胖 ” 和 “ 龙 ” ，坏词为 “ 喷火 ” 和 “ 骑士 ” 。特别要说明一下 “ 龙 ” 被识别为好词的原因 “ 喷火 ” 和 “ 喷火龙 ” 均为坏词，按正向最短匹配得到 “ 喷火 ” ，接着往下匹配到好词 “ 龙 ” 、 “ 龙骑 ” 和 “ 龙骑士 ” ，但是由于 “ 骑士 ” 是坏词，所以 “ 龙骑 ” 、 “ 龙骑士 ” 无效而 “ 龙 ” 是最长的有效好词。注意题目描述中的匹配规则，好词的 “ 有效 ” 和 “ 无效 ” 只考虑该好词的一部分与后续字是否能够组成坏词，而不考虑和前面的字是否能够组成坏词 样例中的 “ 龙 ” 虽然可以与前面的字组成坏词

38、 “ 喷火龙 ” 和 “ 火龙 ” ，但由于这两个词都是未能匹配成功的坏词，因此对好词 “ 龙 ” 的词性没有影响，可以累积 “ 龙 ” 的权重。18、（40分）百度时间（ 2007 年初赛） 题目描述 Baidu 的服务器上使用的不是北京时间，而是 Baidu 时间。 Baidu 时间的时分秒与北京时间相同，但是日期与北京时间不同，是用一个正整数表示从 2000 年 1 月 1 日 起的第几天。 现在就请大家设计一个程序将北京时间转换为百度时间。 输入格式 输入数据的每一行为一个待转化的北京时间，格式包括两种： 一种为： YYYY-MM-DD ，（ YYYY 表示四位数年份， MM 为两位月

39、份， DD 为两位日期）； 另一种为： MM/DD/YYYY ，（ YYYY 表示四位数年份， MM 为两位月份， DD 为两位日期）； 不符合任何一种格式的输入视为非法输入。 输出格式 每个数据输出一行。如果格式正确，输出一个正整数，否则输出 Error 。 输入样例 2006-03-21 AStar2007 04/22/2007 输出样例 2149 Error 2463 19、（40分）繁忙的会议室预定问题题目描述 百度由最开始的 7 人团队迅速发展为几千人的大团队，而工程师们经常需要在一起进行 “ 头脑风暴 ” ，这样会议室就成了紧缺资源。为了有效利用资源，大家决定制定规则， 自动安排会

40、议室的使用。 为了公平起见，应按照申请时间从早到晚依次考虑，先到先得，且申请一旦被接受就不能取消。注意同一时间开的不同会议必须在不同的会议室，而同一个人不能同时参加两个会议。 输入格式 输入第一行为会议室总数 n 和请求总数 m ；第二行是 n 个整数，表示会议室能够容量的人数。以下 m 行每行是一个请求，按请求时间先后顺序排列（即应优先满足在输入中更早出现的请求）。 每个请求中第一个是整数，表示会议需要的时间长度（单位：小时）；之后为与会人名单。人名由不超过四个汉字组成，用半角逗号分隔（每人名字固定且唯一，有重名的也在登记时区分开）。名单后的数字表示可以安排会议的时间，也以半角逗号分隔，如

41、10,11,14,15 表示第 10, 11, 14, 15 个小时可以开会（会议时间为 9 到 19 之间的正整数）。 输出格式 输出 m 个数，依次表示每个请求是否被接受。 1 表示接受， 0 表示不接受。 输入样例： 4 20 2 3 张三 , 李四 , 王五 10,11,12,14,15 1 张三 12 4 王六 , 王七 , 王八 , 王九 , 王十 9,10,11,12,13,14,15 2 张三 14,15 输出样例： 1 0 0 1 20、（40分）水果开会时段题目描述； 每个百度工程师团队都有一笔还算丰裕的食品经费，足够每天购置多种水果。水果往往下午送达公司前台。前台的姐姐们

42、只要看到同时出现五种或以上的水果，就称之为 “ 水果开会 ” 。 从搜索引擎切词的语法角度，只要两种水果的名字中有一个字相同就属于同样的类别。例如 “ 小雪梨 ” 和 “ 大雪梨 ” 是同一种水果，而 “ 核桃 ” 和 “ 水蜜桃 ” 也被认为是同一种水果。尤其要指出的是，如果有三种水果 x, y, z 同时在前台出现，且 x 和 y 是同一种水果， y 和 z 也是同一种水果的时候， x 和 z 也被认为是同一种水果。现在前台的姐姐们想知道，今天是否有 “ 水果开会 ” 五种或更多的水果同时在前台出现。 输入格式 输入的第一行只有一个整数 n ，表示购置水果的组数。接下来的 n 行表示水果的

43、到达时间、取走时间（时间用 1200 到 1900 之间的正整数表示，保证取走时间大于到达时间）。剩下的字符串以空格分割每一种水果。如 “ 1400 1600 雪梨 水蜜桃 ” ，表示下午两点到四点（包含两点和四点这两个时间点），雪梨和水蜜桃会在前台等待开会。每种水果名称由不超过十个汉字组成。 输出格式 输出仅一行，包含一个字符串 Yes 或 No ，分别表示今天水果开会与否。 输入样例 1 3 1200 1400 雪梨 柠檬 1300 1400 西瓜 苹果 1400 1800 花生 水蜜桃 输出样例 1 Yes 输入样例 2 3 1200 1400 雪梨 柠檬 1400 1500 哦 大梨 呀 1500 1800 咦 大梨 输出样例 2 No实验要求一、在上面的题中任选至少40分题。二、独立完成，如果两人或多人提交报告相同，则除了本题分数为0外，再扣本题分数一次作为惩罚。此成绩计入实验总成绩。三、方法不限，可以在最后一次实验课时一次性提交word文档，也可以随时提交，内容包括程序