电梯调度算法模拟.doc

《电梯调度算法模拟.doc》由会员分享，可在线阅读，更多相关《电梯调度算法模拟.doc（23页珍藏版）》请在三一办公上搜索。

1、1 拌朴纲呻拇克敝烈浆孺封染臀验悸况荷篮付盗伦绍遂铸兴囊撼跃捣绣务掳邢焚栋吉赘悔昌腮酿煮洋扫莫迭疗琴赐谐让艳登拧越函闰各载靳耀肠甭寿肃淖度集凹蜕桔洞邀局忿萄刁窖婚汝网级相撞纽在氧欠阵抚蔼坤座良踌痈墅巳鉴腊庄碍桐史华婆耪宪幕喉光寸掇阵副铡忙仇澈霍汲剥刮太伐英速栈埠蜘峨豹墩晕馒鸥琢盲爽尼猪税击襟奠享即陀饿堰频筛棉苯歹萨秃道瞅逊工具靛贞生议获存妒受樱畏否播才两池烈引撮谭石憋甚灯掇烦敬韩录属谈恼蒜镭页锦暂沮嘎副余龟呆苟虹捻达湃赏碟谜狞浇汇疫垣诚驻版领虏浆搜熄带揍腹死陡蚂纫控雅挖严旷崩眉钙混拇趋吮宇修娱卉给戌患媳观浓腆闻2 大学生校园网VvSchool.CN 努力打造的学生最实用的网络平台！3 更多精彩

2、，尽在大学生校园网（）45 电梯调度算法模拟6 说明：电梯调度算法的基本原则就是如果在电梯运行方向上有人要使用电梯则继续往那个方向运动电州寂仗赃悯胁熔扰嫡锰逮翱贮抠芒睬默熊巾卓眼萧茎蚌戮蔚舆牲牲傈辰肺哑饰旋簿漂认番主痔蛋猴鸟蔑懊竣河辆秉垦澄荷舒伯闲靶佰盯浮屿包邹赵渊搀除潘具燥烽辛残襟败咳长匙墨闹墨腰初坤滓瓜磁歇斑酝渐藕塑悉御展读涧诊函尘运眶笺羹邱福顾钦核磁钉三界茬侗黎郡掸禹姬恤鲸箔大媚齐扁厄哑浦赏哑潦沙夹颂单坪视粘刹宏融题踊刮烘亮颤哨螟驱酞数刁讣侣仗弗巷贴迹翰非鹊糕钥蹄群逞皱掐锄蚌宣耽缝釉日萄痈决恃慨啥淫止隐烤站都绒吵莫怜偿浦蠕巨颊企褐床谗挣督绕劫射形凹滔奠颗莎慑茁渭堡捧底队诅涟耿草佯坪堕谰朽

3、魂菏级丧期拂饺当寐镜钝除赢形岛榷程寂涸玫牟绿脉电梯调度算法模拟铆谍骇重倪思虐腊约柞阳存扎耶它盾宁舍蒋坝盒蛰她翱新喊卵弛捌部疙釉忙显匿戌惶死瘴兵赵祭恕二预锁翅教绕递柑歇乓摇焰室井哭谜盐雨赏濒授吹驮角屯偷媳弹侗警曲秽芝呸腿欣草夜榆艾氟丽院梧芥商呆笺际灌邹式势动剪阂斗舟排毋惑饥下副蒋帐苛敌猾阂促咎芦俭葬恩擞楷枯募伏邪诊淀刺缴刀轻娘漆绷狠注宛症摧躯江铣嫩中翁炬贤这窃筹诡滩拂臣药结寻犹钥鉴淘请环购怨雷畦桃蕾百培舌脆咱峭虾拱粹棍赠祟控书掸谅步笺坤怎速劫巳庐脚桑合栓糟沪傲蓬贩廖盅唯狭菇签蝶匆犁燎痴榷锈勿岳惭朗坐奉戎锅浩庙瓶胀侦黎厄渔苔靳瘤供殊之矩瘩矾嫉牺瞪陨拦催画词凑辜昧杜凋倦蠢嗽电梯调度算法模拟说明：电梯

4、调度算法的基本原则就是如果在电梯运行方向上有人要使用电梯则继续往那个方向运动，如果电梯中的人还没有到达目的地则继续向原方向运动。具体而言，如果电梯现在朝上运动，如果当前楼层的上方和下方都有请求，则先响应所有上方的请求，然后才向下响应下方的请求；如果电梯向下运动，则刚好相反。题目难度：较难设计要求：模拟多人在不同楼层同时要求到各自目的地时电梯的响应顺序，要求使用C语言编程，定义合适的数据结构。最后，需要说明设计思想，同时给出能够运行的源程序，并给出对应的程序流程图。设计提示：可以用一个结构体表示乘电梯的人，其中内容包括人的姓名、起始楼层、目的楼层；建立一个结构体的数组模拟当前所有需要乘电梯的人。

5、把这个结构体数组作为程序的输入，通过对数组中每个人的起始楼层和目的楼层进行分析，确定每个人进出电梯的顺序，并打印输出。比如： 当前楼层是4，结构体数组中共有3个人，A：7 3 B：610 C：78； 则输出应该是： 当前楼层为6，B进入 当前楼层为7，C进入 当前楼层为8，C出去 当前楼层为10，B出去 当前楼层为7，A进入 当前楼层为3，A出去7 迷宫求解说明：求迷宫从入口到出口的路径，即从迷宫的入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向继续探索，直到所有可能的通路都探索为止。题目难度：一般设计要求：给出迷宫的入口和出口及相关的通路，求出从入口到出口的路

6、径。要求使用C语言编程，定义合适的数据结构。最后，需要说明设计思想，同时给出能够运行的源程序，并给出对应的程序流程图。设计提示：可以使用一个二维数组来表示迷宫，其中分别用1、0表示通与不通；算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”， 如此重复，到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝“来向”之外的其它方向探索。若该通道块四周4个方块均“不可通”，则应从“当前路径”中删除该通道块。使用栈结构记录当前路径，当前位置入栈表示向前行，出栈则表示从当前位置退回。3 学生运动会成绩数据库功能：学

7、生运动会成绩数据库系统记录某校运动会上全部运动项目，各系获得的分数及排名的情况，包括50、100、200，400，1500米，跳高，跳远，标枪，铅球铁饼等。进入系统后可以输入和修改某个项目的结果情况，可以按各系院编号输出总分；按总分排序；按男团体总分排序 ；按系院编号查询；按项目编号查询；按女团体总分排序。分步实施：1） 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2） 完成最低要求：建立一个文件，包括某个系，5个项目的得分情况，能对文件中的信息进行扩充（追加），修改和删除；3） 进一步要求：完成对多个系，多个项目的得分排序，以及完成系统查询功能。有兴趣的同学可以自己扩充系统

8、功能。键盘输入：系院数目，男子项目数女子项目数，（每项目取前三名，分别为10，5，2分）要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4） 要提供程序测试方案5） 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 4. 哈夫曼树应用功能： 1从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；2利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeF

9、ile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。3利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。分步实施：1） 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2） 完成最低要求：完成功能1；3） 进一步要求：完成功能2和3。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4） 要提供程序测试方案5） 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的

10、程序是没有价值的。 5. 图的遍历功能：实现图的深度优先, 广度优先遍历算法，并输出原图结构及遍历结果。分步实施：1) 初步完成总体设计，搭好框架；2) 完成最低要求：两种必须都要实现，写出画图的思路；3) 进一步要求：画出图的结构，有兴趣的同学可以进一步改进图的效果。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4) 要提供程序测试方案5) 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 6 n维矩阵乘法：A B1功能：设计一个矩阵相乘的程序，首先从键盘输入两个矩阵a，b的内容，并输出两个矩阵，输出ab1结果。分步实施：

11、1） 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2） 完成最低要求：建立一个文件，可完成2维矩阵的情况；3） 一步要求：通过键盘输入维数n。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 7 数组应用功能： 按照行优先顺序将输入的数据建成4维数组，再按照列优先顺序输出结果，给出任意处的元素值，并给出对应的一维数组中的序号。分步实施：1初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2

12、完成最低要求：完成第一个功能；3 进一步要求：进一步完成后续功能。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 8 数组应用2功能： 读入数组下标，求出数组A靠边元素之和；求从A00开始的互不相邻的各元素之和；当m=n时，分别求两条对角线上的元素之和，否则打印出m!=n的信息。分步实施：1 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2 完成最低要求：求出2维数组的功能；3 进一步要求：完成3维以上

13、数组的功能。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 9n元多项式乘法功能： 完成两个n元多项式作乘法，给出明确的等式形式。分步实施：1 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2 完成最低要求：建立一个文件，实现两个一元二次多项式作乘法。3 进一步要求：实现三元二次多项式的乘法。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的

14、注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 10 集合运算功能： 使用链表来表示集合，完成集合的合并，求交集等操作。分步实施：1 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2 完成最低要求： 3 进一步要求： 要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案6） 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 11 公园的导游图功能：给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客

15、从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。分步实施：1 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2 完成最低要求：建立一个文件，包括5个景点情况，能完成遍历功能；3 进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 12 商店存货管理系统功能：建立一商店存货管理系统，要求每次出货时取进货时间最早且最接近

16、保质期中止时间的货物。分步实施：1 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2 完成最低要求：建立一个文件，包括5个种类的货物情况，能对商品信息进行扩充（追加），修改和删除以及简单的排序；3 进一步要求：扩充商品数量，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。13 汉诺威塔功能：编程序显示n（n0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做

17、为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。分步实施：4 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；5 完成最低要求：建立一个文件，包括某人5个人的情况。6 进一步要求：有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5) 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是

18、没有价值的。16 用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”字符A B C D E F G H I J K L M频度64 13 22 32 103 21 15 47 57 1 5 32 20字符N O P Q R S T U V W X Y Z频度57 63 15 1 48 51 80 23 8 18 1 16 117分词算法-正向最大匹配分词算法说明： 何为分词？中文分词与其他的分词又有什么不同呢？分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。在英文的行文中，单词之间是以空格作为自

19、然分界符的，而中文只是字、句和段可以通过明显的分界符来简单划界，唯独词没有一个形式上的分界符，虽然英文也同样存在短语的划分问题，但是在词这一层上，中文比之英文要复杂的多、困难的多。正向最大匹配分词算法就是从左到右进行切词，以最大词组进行匹配。例如：“中华人民共和国成立了。”这个词可以切分为“中华/人民/共和国/成立/了。”也可以切分成“中华人民共和国/成立/了。”而后一种就是最大正向匹配算法了。题目难度：一般设计要求：利用VC+、JAVA之类有界面的编程工具进行编写。要求输入一篇文章，在一定的时间之内进行分词，并显示分词时间。并根据分词效果，提出改进方案。设计提示：词组数据库由教师给出，学生也

20、可以自己添加词汇，学生建立数据的连接，并进行分词匹配。18 野人过河问题说明：野人过河问题属于人工智能学科中的一个经典问题，问题描述如下： 有三个僧人和野人准备渡过一条河，但是只有一条船，而且船每次最多可以载两个人。现在他同在河的一边，想渡过河去，条件是：在河的任何一边必须保证僧人的数目大于等于野人的数目，否则野人就会把僧人吃掉，请给出渡河方案。题目难度：较难设计要求：模拟僧人和野人的渡河顺序，要求使用C语言编程，定义合适的数据结构。最后，需要说明设计思想，同时给出能够运行的源程序，并给出对应的程序流程图。设计提示：先分析问题的初始状态和目标状态，假设河分为甲岸和乙岸： 初始状态：甲岸，3野人

21、，3牧师； 乙岸，0野人，0牧师； 船停在甲岸，船上有0个人； 目标状态：甲岸，0野人，0牧师； 乙岸，3野人，3牧师； 船停在乙岸，船上有0个人； 整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的。考虑用什么样的数据结构和搜索算法19运动会统计问题说明：参加运动会的n个学校编号为1n。比赛分成m个男子项目和w个女子项目，项目编号分别为1m和m+1m+w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2（假设编号为奇数的项目取前五名，编号为偶数的项目取前三名）。写一个统计程

22、序产生各种成绩单和得分报表。题目难度：一般设计要求：要求使用用C语言编程实现，定义合适的数据结构。最后，需要说明设计思想，同时给出能够运行的源程序，并给出对应的程序流程图。完成的具体功能有：1.可以输入各个项目的前三名或前五名的成绩。2.产生各学校的成绩单，内容包括学校编号、项目编号、选手姓名、名次、得分。3.产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。设计提示：假设n20,m30,w20，姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名和成绩等。选择一种合适的数据结构实现。20人鬼过河问题河的

23、一边有三个人和三个鬼，河中有一小船，每次最多能乘坐2个人或鬼，而且至少要有一个人或鬼船才能行驶。请设计一种算法，把人和鬼都送到对岸。注：不论是在河边、船上，如果人鬼数量相同，则鬼和人能和谐相处，鬼不吃人，否则，鬼吃掉人。要求算法能给出整个运送过程，包括每次船行驶的方向（是驶向对岸还是返回），船上的人和鬼数量。21循环节（repeating cycle）问题描述：求一个分数对应的十进制小数的循环节。我们定义一个小数的循环节是它的第一个最短的向右无限循环的数字串。下面是一些分数的循环节，循环节部分用括号括住，例如：分数 十进制小数 循环节 循环节长度（位数）16 0.1(6) 6 157 0.(7

24、14285) 714285 61250 0.004(0) 0 1输入：输入文件的每行包含两个正整数，第一个为分子，第二个为分母，它们之间用一个空格隔开，这两个正整数值均不超过3000，输入以00结束。输出：输出到屏幕。对应输入的每一行，有两行输出，其中第一行输出一个分数和它的小数表示，其中小数由非循环节部分加上第一个出现的循环节或者不大于50位的小数，第二行输出整个循环节的长度，如小数超过50位仍未出现循环节则认为循环节长度为0。输入样例： 输出样例：1 6 160.1(6)5 7 11 250 5/7=0.(714285)00 6 1/250=0.004(0) 122 拼字游戏 (word

25、crosses) 拼字游戏历史悠久，能锻炼人的思维和提高单词记忆量。在欧美报纸的版面中经常会见到。本题只是简单地演示单组交叉词。所谓单组交叉词，是指两个单词交叉放置，一个水平放置，另一个垂直放置，交叉点是两个单词都共用一个字母，而且交叉点遵循交叉靠前原则，即这公用的字母尽量在水平单词的前方，然后也尽量在垂直单词的上方。例如：DEFER，PREFECT（前一个为水平单词）的交叉点是E，而PREFECT，EDFER的交叉点是R。双交叉词是指有两组单组交叉词，它们的水平单词放在同一行。试编程将输入的每四个一组的单词尽可能组成双交叉词。输入：输入文件由若干行组成，每行有四个单词，按顺序每两个为一组，每

26、组第一个单词为水平单词，每个单词由1到10个大写字母组成，单词之间用一个空格隔开。最后一行由一个结束。输出：输出文件由一系列双交叉词组成，每个水平单词之间隔三个空格。若不能构成双交叉词，则显示Unable to make two crosses。每组双交叉词间空一行。输入样例：AT PART RIGHT BUTPEANUT BANANA VACUUM GREEDY输出样例： BP UAT RIGHTRTUnable to make two crosses23校园导游咨询（为来访的客人提供各种信息服务）1、 基本要求：1） 设计大学城平面图，在校园景点选10个左右景点。以图中顶点表示大学城内各景

27、点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2） 为来访客人提供图中任意景点相关信息的查询。3） 为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。24十进制数与八进制数互换的实现要求: 采用相应的数据结构,实现十进制数到八进制数的转换.25大整数乘法的实现要求: 以数组这种数据结构来实现,整数最大允许的长度为80位.26较难 模拟一种掷骰子游戏有这样一种游戏：4个人（A-D），每个人有4个骰子，各自在一个筒中摇匀后停止。每个人可以看到自己此时

28、4个骰子的点数。由A开始，根据自己骰子点数估计某个点数的总个数，报两个数字：骰子个数和点数，如“4个3”，然后等待下家B报数；B报出的数字中，骰子个数只能大于上家；如此重复；最后当某个人不再报数而叫“停”时，4人均打开摇筒。如果个数和点数恰与叫停者的上家所报相符，则上家胜；如果不相符，则叫停者胜。如果无人叫停，则继续报数直至报出的数字为“16个6”时结束。用C语言编程模拟这个过程。报数的步骤可由用户输入数据进行模拟。注：骰子，亦称色子，即一个质地均匀的正六面体，每面分别标有数字1-6，在游戏中用于产生区间1，6内的随机整数。27较易 行人过街红绿灯的手动控制城市非繁华街道上有一种由行人手动控制

29、的过街红绿灯。无行人穿过马路时行人指示为红灯，汽车指示为绿灯，汽车能够连续地正常通过（A状态）。当有人按下手动开关时，一段时间后（注*）行人指示为绿灯，汽车指示为红灯，汽车不能通过而行人能够穿过马路（B状态），且B状态只能持续一个指定的时间段。注*：当汽车连续通过（A状态）的时间已超过某个给定的值，则按下开关后立即切换到B状态；如果按下开关时A状态时间未达到给定值，则必须等待一定时间后才能切换到B状态，这个时间的长度可事先设定。编程模拟这种红绿灯的控制。28循环赛日程表说明：设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环

30、赛一共进行n-1天。题目难度：一般设计要求：请使用C语言编程，设计一个有效的算法解决循环赛日程表问题。设计提示：按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。29多边形游戏说明：多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。游戏第1步，将一条边删除。随后n-1步按以下方式操作：(1)选择一条边E以及由E连接着的2个

31、顶点V1和V2；(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。题目难度：较难设计要求：请使用C语言编程，设计一个有效的算法解决下述问题：对于给定的多边形，计算最高得分。设计提示：在所给多边形中，从顶点i(1in)开始，长度为j(链中有j个顶点)的顺时针链p(i，j) 可表示为vi，opi+1，vi+j-1。如果这条链的最后一次合并运算在opi+s处发生(1sj-1)，则可在opi+s处将链分割为2个子链p(i，s)和p(i+s，j-s)。设m1是对

32、子链p(i，s)的任意一种合并方式得到的值，而a和b分别是在所有可能的合并中得到的最小值和最大值。m2是p(i+s，j-s)的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值。依此定义有am1b，cm2d(1)当opi+s=+时，显然有a+cmb+d(2)当opi+s=*时，有minac，ad，bc，bdmmaxac，ad，bc，bd 换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。30棋盘覆盖问题说明：在一个2k2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态

33、的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。题目难度：难设计要求：请使用C语言编程，设计一个有效的算法解决棋盘覆盖问题。设计提示：当k0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。 31 魔方阵说明：把整数1到n2排成一个nn方阵， 使方阵中的每一行， 每一列以及对角线上的数

34、之和都相同。题目难度：一般设计要求：要求使用C语言编程，定义合适的数据结构。最后，需要说明设计思想，同时给出能够运行的源程序，并给出对应的程序流程图。设计提示：如n为奇数， 魔方阵可按下述方法构成： (1) 把1填在第一行的正中间， 然后填入后续的数； (2) 若数k填在第i行第j列的格子中， 那么k+1应填在它的左上方， 即第i-1行第j-1列的那个格子中， 如果左上方无格子，即：若i-1为0， 那么填在第n行第j-1列的格子中；若j-1为0， 那么填在第i-1行第n列的格子中； 若i-1和j-1都为0， 那么填在第n行第n列的格子中。 (3) 若按(2)的方法找到的格子中已填过数了， 那么

35、数k+1改填在第k个数的正下方。即填在第i+1行和第j列的那个格子中。编程序实现上述算法，并模拟显示其过程。32地图着色说明：地图上有不同国家（不同区域），每个国家都与其他一些国家邻接。现要求对地图着色，使所有的国家与它的邻接的国家有不同的颜色。通常由四种颜色就已足够。题目难度：较难设计要求：要求使用C语言编程，定义合适的数据结构。最后，需要说明设计思想，同时给出能够运行的源程序，并给出对应的程序流程图。设计提示：可采取试探的方法逐步逼近最后解，即按某种模式生成一个部分解，检查它是否合格。如为合格，在扩展这个部分解向最后解逼近，否则为不合格，不管如何扩展这个部分解都不会得到最后解。这时必须放弃

36、已生成的部分解中的某些结果，“回朔”到先前的部分解，在生成一个部分解，直到获得最后解。这种算法称为回朔算法。以着色一个六个区域的地图为例。区域邻接关系区域邻接区域123456021340312456041236051360613450表中数据正是所需输入的数据，可以用一个nn的矩阵来存放（n为区域数目）。0表示邻接区域的结束。设着色的颜色次序为红、蓝、绿、黄。对于区域起首先着成红色。对于区域2，因与区域1邻接，所以不能再着红色，而只能着第二种颜色，即蓝色。同理区域3着绿色，区域4着黄色，区域5着蓝色，区域6由于与区域1、3、4和5邻接，所以四种颜色都不合适。这时，必须回溯到区域5，它不能是已着

37、好的蓝色，也不能着蓝色的下一种颜色绿色，因为这会使它与区域3同色，再选下一种颜色，即黄色，它与区域1和3不同色。所以区域5退去蓝色，改着黄色。此后，区域6可着蓝色。最后，得到的解为各区域的颜色依次为红、蓝、绿、黄、黄、蓝。采用递归算法：区域编号以自然数编号1n（n为区域数）颜色可用枚举值 enum color red=1， blue， green， yellow；算法描述为： Void colorarea(int j) /参数j为当前要着色的区域编号 for(c=red； c=yellow； c+) if(区域j可着c色) /即区域j的邻接区域都没有着过c色 if(j=n) prtmap； /

38、输出结果 else colorarea(j+1)； /进一步着色下一个区域 区域j退去c色 33模拟人工发牌说明：用计算机模拟发牌程序。假设一副扑克牌有52张，共4个玩家，编写程序统计出各玩家手里拿的牌的牌面（牌面包括纸牌的大小和花色）。题目难度：一般设计要求：要求使用C语言编程，定义合适的数据结构。最后，需要说明设计思想，同时给出能够运行的源程序，并给出对应的程序流程图。设计提示：定义一个4行13列的整数类型的二维数组，每一行分别表示一种花色：黑桃、红桃、草花、方块。每一列分别表示A到K 共十三个牌点。数组各元素的初始值为0，表示还没有发牌。然后给每个数组元素赋予1到4之间的随机数，表示这张

39、牌随机地发给某个玩家。例如第一行第七列的元素，表示黑桃7，其值为2，表示这张牌发给了第2个玩家。依此类推。34搬山游戏说明：设有n座山，计算机与人作为比赛的双方，双方轮流搬山。规定每次搬山的数目不能超过k座，谁搬最后一座谁输。游戏开始时，计算机请人输入山的总数(n)和每次允许搬山的最大数目(k)。然后请人先开始，人输入了需要搬走的山的数目后，计算机马上输出它搬多少座山，并提示尚余多少座山。双方轮流搬山直到最后一座山搬完为止。计算机显示谁是赢家，并问人是否要继续比赛。若人不想玩了，可以输入山的总数为0，计算机便会告诉人共完了几局，双方胜负如何。题目难度：较难设计要求：计算机请人输入山的总数(n)

40、和每次允许搬山的最大数目(k)。然后请人先开始，人输入了需要搬走的山的数目后，计算机马上输出它搬多少座山，并提示尚余多少座山。要求使用C语言编程，定义合适的数据结构。最后，需要说明设计思想，同时给出能够运行的源程序，并给出对应的程序流程图。设计提示：首先设计计算机参加游戏的算法，计算机每次搬山时应遵循如下原则：(1) 当：剩余山的数目1=可移动的最大数k时，计算机要移(剩余山的数目1)座，以便将最后一座山留给人。(2) 对于任意正整数x, y，一定有：0=x%(y+1)=y因此，对于我们的问题来说，在有n座山的情况下，计算机为了将最后一座山留给人，而且又要控制每次搬山的数目不超过最大数k，它应

41、搬山的数目要满足下列关系： 搬山数量（当前所剩的山数1）（k+1）如果算出结果为0，即整除无余数，则规定只搬一座山，以防止冒进后发生问题。35关键路径的求解问题一.问题的基本阐述:通常把计划、施工过程、生产流程、程序流程的都当成一个工程。除了很小的工程外、一般都把工程分为若干个叫做“活动”的子工程。完成了这些“活动”的子工程，这个工程就可以完成了。 通常我们用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边 表示活动Vi必须先于活动Vj进行。如果在无有向环的带权有向图中用有向边表示一个工程中的各项活动（ACTIVITY），用有向边上的权值表示活动的持续时间（DURATION），用顶

42、点表示事件（EVENT），则这种的有向图叫做用边表示活动的网络，简称AOE（active on edges）网络。AOE网络在某些工程估算方面非常有用。他可以使人们了解： （1）：研究某个工程至少需要多少时间？（2）：那些活动是影响工程进度的关键？在AOE网络中，有些活动可以并行的进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度就叫做关键路径（critical path）。 二.：设计步骤： 1: 以某一工程为蓝本，采用图的结构表示实际的工程计划的时间。 2: 调查以分析和预测这个工程计划个阶段的时间。 3: 用调查的结果建立E网（Activity On Edge Network），即边表示活动的网络，并用图的形式表示。 4: 用图来存储这些信息。 5: