当前位置: 首页 > >

电梯调度算法模拟

发布时间:

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

1. 电梯调度算法模拟 说明: 电梯调度算法的基本原则就是如果在电梯运行方向上有人要使用电梯则继续往那 个方向运动,如果电梯中的人还没有到达目的地则继续向原方向运动。具体而言,如果电梯 现在朝上运动,如果当前楼层的上方和下方都有请求,则先响应所有上方的请求,然后才向 下响应下方的请求;如果电梯向下运动,则刚好相反。 题目难度:较难 设计要求:模拟多人在不同楼层同时要求到各自目的地时电梯的响应顺序,要求使用 C 语言编程,定义合适的数据结构。最后,需要说明设计思想,同时给出能够运行的源程序, 并给出对应的程序流程图。 设计提示:可以用一个结构体表示乘电梯的人,其中内容包括人的姓名、起始楼层、目 的楼层; 建立一个结构体的数组模拟当前所有需要乘电梯的人。 把这个结构体数组作为程序 的输入, 通过对数组中每个人的起始楼层和目的楼层进行分析, 确定每个人进出电梯的顺序, 并打印输出。 比如: 当前楼层是 4,结构体数组中共有 3 个人,A:7 → 3 B:6→10 C:7→8; 则输出应该是: 当前楼层为 6,B 进入 当前楼层为 7,C 进入 当前楼层为 8,C 出去 当前楼层为 10,B 出去 当前楼层为 7,A 进入 当前楼层为 3,A 出去 2. 迷宫求解 说明:求迷宫从入口到出口的路径,即从迷宫的入口出发,顺某一方向向前探索,若能 走通,则继续往前走;否则沿原路退回,换一个方向继续探索,直到所有可能的通路都探索 为止。 题目难度:一般 设计要求:给出迷宫的入口和出口及相关的通路,求出从入口到出口的路径。要求使用 C 语言编程,定义合适的数据结构。最后,需要说明设计思想,同时给出能够运行的源程序, 并给出对应的程序流程图。 设计提示:可以使用一个二维数组来表示迷宫,其中分别用 1、0 表示通与不通;算法的基 本思想是:若当前位置“可通” ,则纳入“当前路径” ,并继续朝“下一位置”探索,即切换 “下一位置”为“当前位置” 如此重复,到达出口;若当前位置“不可通” , ,则应顺着“来 向”退回到“前一通道块” ,然后朝“来向”之外的其它方向探索。若该通道块四周 4 个方 块均“不可通” ,则应从“当前路径”中删除该通道块。使用栈结构记录当前路径,当前位 置入栈表示向前行,出栈则表示从当前位置退回。

更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

3. 学生运动会成绩数据库 功能: 学生运动会成绩数据库系统记录某校运动会上全部运动项目, 各系获得的分数及排名的 情况,包括 50、100、200,400,1500 米,跳高,跳远,标枪,铅球铁饼等。进入系统后可 以输入和修改某个项目的结果情况,可以按各系院编号输出总分;按总分排序;按男团体总 分排序 ;按系院编号查询;按项目编号查询;按女团体总分排序。 分步实施: 1) 初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数; 2) 完成最低要求:建立一个文件,包括某个系,5 个项目的得分情况,能对文件中 的信息进行扩充(追加) ,修改和删除; 3) 进一步要求:完成对多个系,多个项目的得分排序,以及完成系统查询功能。有 兴趣的同学可以自己扩充系统功能。 键盘输入:系院数目,男子项目数女子项目数, (每项目取前三名,分别为 10,5,2 分) 要求:1)界面友好,函数功能要划分好 2)总体设计应画一流程图 3)程序要加必要的注释 4) 要提供程序测试方案 5) 程序一定要经得起测试,宁可功能少一些,也要能运行起来,不能运行的程序是 没有价值的。

4. 哈夫曼树应用
功能:

1.从终端读入字符集大小 n,以及 n 个字符和 n 个权值,建立哈夫曼树并将它存于文件 hfmTree 中.
将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上; 2.利用已经建好的哈夫曼树(如不在内存,则从文件 htmTree 中读入) ,对文件 ToBeTran 中的正文进 行编码,然后将结果存入文件 CodeFile 中,并输出结果,将文件 CodeFile 以紧凑格式先是在终端上, 每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrint 中。 3.利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码,结果存入文件 TextFile 中,并输出结果。 分步实施: 1) 初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数; 2) 完成最低要求:完成功能 1; 3) 进一步要求:完成功能 2 和 3。有兴趣的同学可以自己扩充系统功能。 要求:1)界面友好,函数功能要划分好 2)总体设计应画一流程图 3)程序要加必要的注释 4) 要提供程序测试方案 5) 程序一定要经得起测试,宁可功能少一些,也要能运行起来,不能运行的程序是 没有价值的。

更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

5. 图的遍历
功能:实现图的深度优先, 广度优先遍历算法,并输出原图结构及遍历结果。 分步实施: 1) 初步完成总体设计,搭好框架; 2) 完成最低要求:两种必须都要实现,写出画图的思路; 3) 进一步要求:画出图的结构,有兴趣的同学可以进一步改进图的效果。 要求:1)界面友好,函数功能要划分好 2)总体设计应画一流程图 3)程序要加必要的注释 4) 要提供程序测试方案 5) 程序一定要经得起测试,宁可功能少一些,也要能运行起来,不能运行的程序是 没有价值的。

6. n 维矩阵乘法:A B-1
功能:设计一个矩阵相乘的程序,首先从键盘输入两个矩阵 a,b 的内容,并输出两个矩阵, -1 输出 ab 结果。 分步实施: 1) 初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数; 2) 完成最低要求:建立一个文件,可完成 2 维矩阵的情况; 3) 一步要求:通过键盘输入维数 n。有兴趣的同学可以自己扩充系统功能。 要求:1)界面友好,函数功能要划分好 2)总体设计应画一流程图 3)程序要加必要的注释 4)要提供程序测试方案 5)程序一定要经得起测试,宁可功能少一些,也要能运行起来,不能运行的程序是 没有价值的。

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

8. 数组应用 2
更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

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

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

10. 集合运算
功能: 使用链表来表示集合,完成集合的合并,求交集等操作。 分步实施: 1. 初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数; 2. 完成最低要求: 3. 进一步要求: 要求:1)界面友好,函数功能要划分好 2)总体设计应画一流程图 3)程序要加必要的注释 4)要提供程序测试方案 6) 程序一定要经得起测试,宁可功能少一些,也要能运行起来,不能运行的程序是 没有价值的。

更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

11. 公园的导游图
功能:给出一张某公园的导游图,游客通过终端询问可知: 从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不 重复地游览各景点,最后回到出口(出口就在入口旁边) 。 分步实施: 1. 初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数; 2. 完成最低要求:建立一个文件,包括 5 个景点情况,能完成遍历功能; 3. 进一步要求: 进一步扩充景点数目, 画出景点图, 有兴趣的同学可以自己扩充系统功能。 要求:1)界面友好,函数功能要划分好 2)总体设计应画一流程图 3)程序要加必要的注释 4)要提供程序测试方案 5)程序一定要经得起测试,宁可功能少一些,也要能运行起来,不能运行的程序是 没有价值的。

12. 商店存货管理系统
功能:建立一商店存货管理系统,要求每次出货时取进货时间最早且最接*保质期中止时间 的货物。 分步实施: 1. 初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数; 2. 完成最低要求:建立一个文件,包括 5 个种类的货物情况,能对商品信息进行扩充(追 加) ,修改和删除以及简单的排序; 3. 进一步要求:扩充商品数量,以及完成系统查询功能。有兴趣的同学可以自己扩充系统 功能。 要求:1)界面友好,函数功能要划分好 2)总体设计应画一流程图 3)程序要加必要的注释 4)要提供程序测试方案 5)程序一定要经得起测试,宁可功能少一些,也要能运行起来,不能运行的程序是 没有价值的。

更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

13. 汉诺威塔
功能:编程序显示 n(n<=9)层汉诺威塔的调整过程。 分步实施: 1. 初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数; 2. 完成最低要求:实现 5 层汉诺威塔的调整过程; 3. 进一步要求:直至实现 n=9 时的情况。有兴趣的同学可以自己扩充系统功能。 要求:1)界面友好,函数功能要划分好 2)总体设计应画一流程图 3)程序要加必要的注释 4)要提供程序测试方案 5)程序一定要经得起测试,宁可功能少一些,也要能运行起来,不能运行的程序是 没有价值的。

14. 个人帐簿管理系统设计
功能: 个人帐簿管理系统记录某人每月的全部收入及各项开支情况,包括食品消费,房租, 子女教育费用,水电费,医疗费,储蓄等。进入系统后可以输入和修改某月的收支情况,可 以对每月的开支从小到大进行排序,可以根据输入的月份查询每月的收支情况。 分步实施: 1. 初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数; 2. 完成最低要求:建立一个文件,包括某人 5 个月的收支情况,能对文件中的信息进行扩 充(追加) ,修改和删除; 3. 进一步要求:完成对每月的开支排序,以及完成系统查询功能。有兴趣的同学可以自己 扩充系统功能。 要求:1)界面友好,函数功能要划分好 2)总体设计应画一流程图 3)程序要加必要的注释 4)要提供程序测试方案 5) 程序一定要经得起测试,宁可功能少一些,也要能运行起来,不能运行的程序是 没有价值的。

更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

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

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 1

更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

17.分词算法----正向最大匹配分词算法 正向最大匹配分词算法 说明: 何为分词?中文分词与其他的分词又有什么不同呢?分词就是将连续的字序列按 照一定的规范重新组合成词序列的过程。 在英文的行文中, 单词之间是以空格作为自然分界 符的,而中文只是字、句和段可以通过明显的分界符来简单划界,唯独词没有一个形式上的 分界符,虽然英文也同样存在短语的划分问题,但是在词这一层上,中文比之英文要复杂的 多、困难的多。 正向最大匹配分词算法就是从左到右进行切词,以最大词组进行匹配。例如: “中华人 民共和国成立了。 ”这个词可以切分为“中华/人民/共和国/成立/了。 ”也可以切分成“中华 人民共和国/成立/了。 ”而后一种就是最大正向匹配算法了。 题目难度:一般 设计要求:利用 VC++、JAVA 之类有界面的编程工具进行编写。要求输入一篇文章, 在一定的时间之内进行分词,并显示分词时间。 并根据分词效果,提出改进方案。 设计提示:词组数据库由教师给出,学生也可以自己添加词汇,学生建立数据的连接, 并进行分词匹配。 18. 野人过河问题 说明:野人过河问题属于人工智能学科中的一个经典问题,问题描述如下: 有三个僧人和野人准备渡过一条河,但是只有一条船,而且船每次最多可以载两个人。 现在他同在河的一边,想渡过河去,条件是:在河的任何一边必须保证僧人的数目大于等于 野人的数目,否则野人就会把僧人吃掉,请给出渡河方案。 题目难度:较难 设计要求:模拟僧人和野人的渡河顺序,要求使用 C 语言编程,定义合适的数据结构。 最后,需要说明设计思想,同时给出能够运行的源程序,并给出对应的程序流程图。 设计提示:先分析问题的初始状态和目标状态,假设河分为甲岸和乙岸: 初始状态:甲岸,3 野人,3 牧师; 乙岸,0 野人,0 牧师; 船停在甲岸,船上有 0 个人; 目标状态:甲岸,0 野人,0 牧师; 乙岸,3 野人,3 牧师; 船停在乙岸,船上有 0 个人; 整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的 改变是通过划船渡河来引发的。考虑用什么样的数据结构和搜索算法

更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

19.运动会统计问题
说明:参加运动会的 n 个学校编号为 1~n。比赛分成 m 个男子项目和 w 个女子项目, 项目编号分别为 1~m 和 m+1~m+w。 由于各项目参加人数差别较大, 有些项目取前五名, 得分顺序为 7,5,3,2,1;还有些项目只取前三名,得分顺序为 5,3,2(假设编号为奇 数的项目取前五名,编号为偶数的项目取前三名) 。写一个统计程序产生各种成绩单和得分 报表。 题目难度:一般 设计要求:要求使用用 C 语言编程实现,定义合适的数据结构。最后,需要说明设计 思想,同时给出能够运行的源程序,并给出对应的程序流程图。完成的具体功能有: 1.可以输入各个项目的前三名或前五名的成绩。 2.产生各学校的成绩单,内容包括学校编号、项目编号、选手姓名、名次、得分。 3.产生团体总分报表,内容包括校号、男子团体总分、女子团体总分和团体总分。 设计提示:假设 n≤20,m≤30,w≤20,姓名长度不超过 20 个字符。每个项目结束时,将 其编号、类型符(区分取前五名还是前三名)输入,并按名次顺序输入运动员姓名、校名和 成绩等。选择一种合适的数据结构实现。

20.人鬼过河问题 河的一边有三个人和三个鬼,河中有一小船,每次最多能乘坐 2 个人或鬼,而且至少要有一 个人或鬼船才能行驶。请设计一种算法,把人和鬼都送到对岸。注:不论是在河边、船上, 如果人鬼数量相同,则鬼和人能和谐相处,鬼不吃人,否则,鬼吃掉人。要求算法能给出整 个运送过程,包括每次船行驶的方向(是驶向对岸还是返回) ,船上的人和鬼数量。

更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

21.循环节(repeating cycle)
问题描述: 求一个分数对应的十进制小数的循环节。我们定义一个小数的循环节是它的第一个最短 的向右无限循环的数字串。 下面是一些分数的循环节,循环节部分用括号括住,例如: 分数 十进制小数 循环节 循环节长度(位数) 1/6 0.1(6) 6 1 5/7 0.(714285) 714285 6 1/250 0.004(0) 0 1 输入:输入文件的每行包含两个正整数,第一个为分子,第二个为分母,它们之间用一 个空格隔开,这两个正整数值均不超过 3000,输入以 00 结束。 输出:输出到屏幕。对应输入的每一行,有两行输出,其中第一行输出一个分数和它的 小数表示,其中小数由非循环节部分加上第一个出现的循环节或者不大于 50 位的小数, 第二行输出整个循环节的长度,如小数超过 50 位仍未出现循环节则认为循环节长度为 0。 输入样例: 1 6 5 7 1 250 00 输出样例: 1/6=0.1(6) 1 5/7=0.(714285) 6 1/250=0.004(0) 1

22. 拼字游戏

(word crosses)

拼字游戏历史悠久,能锻炼人的思维和提高单词记忆量。在欧美报纸的版面中经常会见 到。本题只是简单地演示单组交叉词。所谓单组交叉词,是指两个单词交叉放置,一个 水*放置,另一个垂直放置,交叉点是两个单词都共用一个字母,而且交叉点遵循交叉 靠前原则,即这公用的字母尽量在水*单词的前方,然后也尽量在垂直单词的上方。例 如:DEFER,PREFECT(前一个为水*单词)的交叉点是 E,而 PREFECT,EDFER 的交叉点是 R。双交叉词是指有两组单组交叉词,它们的水*单词放在同一行。 试编程将输入的每四个一组的单词尽可能组成双交叉词。 输入:输入文件由若干行组成,每行有四个单词,按顺序每两个为一组,每组第一个单 词为水*单词,每个单词由 1 到 10 个大写字母组成,单词之间用一个空格隔开。最后一行 由一个"#"结束。 输出:输出文件由一系列双交叉词组成,每个水*单词之间隔三个空格。若不能构成双 交叉词,则显示"Unable to make two crosses"。每组双交叉词间空一行。 输入样例: AT PART RIGHT BUT PEANUT BANANA VACUUM GREEDY # 输出样例: B
更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

P AT R T

U RIGHT

Unable to make two crosses

23.校园导游咨询(为来访的客人提供各种信息服务) .校园导游咨询(为来访的客人提供各种信息服务)
1、基本要求: 1)设计大学城*面图, 在校园景点选 10 个左右景点。 以图中顶点表示大学城内各景点, 存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等有关信息。 2)为来访客人提供图中任意景点相关信息的查询。 3)为来访客人提供任意景点的问路查询,即查询任意两个景点之间的一条最短路径。 实现提示:一般情况下,校园的道路是双向通行的,可设计校园*面图是一个无向网。顶点 和边均含有相关信息。

24.十进制数与八进制数互换的实现 要求: 采用相应的数据结构,实现十进制数到八进制数的转换. 25.大整数乘法的实现 要求: 以数组这种数据结构来实现,整数最大允许的长度为 80 位.

更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

26.较难 . 模拟一种掷骰子游戏 有这样一种游戏:4 个人(A-D) ,每个人有 4 个骰子,各自在一个筒中摇匀后停止。每个人 可以看到自己此时 4 个骰子的点数。由 A 开始,根据自己骰子点数估计某个点数的总个数, 报两个数字:骰子个数和点数,如“4 个 3” ,然后等待下家 B 报数;B 报出的数字中,骰 子个数只能大于上家;如此重复;最后当某个人不再报数而叫“停”时,4 人均打开摇筒。 如果个数和点数恰与叫停者的上家所报相符,则上家胜;如果不相符,则叫停者胜。如果无 人叫停,则继续报数直至报出的数字为“16 个 6”时结束。 用 C 语言编程模拟这个过程。报数的步骤可由用户输入数据进行模拟。 注:骰子,亦称色子,即一个质地均匀的正六面体,每面分别标有数字 1-6,在游戏中用于 产生区间[1,6]内的随机整数。 27.较易 . 行人过街红绿灯的手动控制 城市非繁华街道上有一种由行人手动控制的过街红绿灯。 无行人穿过马路时行人指示为 红灯,汽车指示为绿灯,汽车能够连续地正常通过(A 状态) 。当有人按下手动开关时,一 段时间后(注*)行人指示为绿灯,汽车指示为红灯,汽车不能通过而行人能够穿过马路(B 状态) ,且 B 状态只能持续一个指定的时间段。 注*:当汽车连续通过(A 状态)的时间已超过某个给定的值,则按下开关后立即切换 到 B 状态;如果按下开关时 A 状态时间未达到给定值,则必须等待一定时间后才能切换到 B 状态,这个时间的长度可事先设定。 编程模拟这种红绿灯的控制。 28.循环赛日程表 . 说明:设计一个满足以下要求的比赛日程表: (1)每个选手必须与其他 n-1 个选手各赛一次; (2)每个选手一天只能赛一次; (3)循环赛一共进行 n-1 天。 题目难度:一般 设计要求:请使用 C 语言编程,设计一个有效的算法解决循环赛日程表问题。 设计提示:按分治策略,将所有的选手分为两半,n 个选手的比赛日程表就可以通过为 n/2 个选手设计的比赛日程表来决定。递归地用对选手进行分割,直到只剩下 2 个选手时,比赛 日程表的制定就变得很简单。这时只要让这 2 个选手进行比赛就可以了。 29.多边形游戏 . 说明: 多边形游戏是一个单人玩的游戏, 开始时有一个由 n 个顶点构成的多边形。 每个顶点被 赋予一个整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从 1 到 n 编号。 游戏第 1 步,将一条边删除。随后 n-1 步按以下方式操作: (1)选择一条边 E 以及由 E 连接着的 2 个顶点 V1 和 V2; (2)用一个新的顶点取代边 E 以及由 E 连接着的 2 个顶点 V1 和 V2。 将由顶点 V1 和 V2 的整 数值通过边 E 上的运算得到的结果赋予新顶点。 最后,所有边都被删除,游戏结束。游戏的得分就是所剩顶点上的整数值。 题目难度:较难 设计要求: 请使用 C 语言编程,设计一个有效的算法解决下述问题:对于给定的多边形,计算最高 得分。
更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

设计提示: 在所给多边形中, 从顶点 i(1≤i≤n)开始, 长度为 j(链中有 j 个顶点)的顺时针链 p(i, 可 j) 表示为 v[i],op[i+1],…,v[i+j-1]。 如果这条链的最后一次合并运算在 op[i+s]处发生(1≤s≤j-1), 则可在 op[i+s]处将链分割 为 2 个子链 p(i,s)和 p(i+s,j-s)。 设 m1 是对子链 p(i,s)的任意一种合并方式得到的值,而 a 和 b 分别是在所有可能的合 并中得到的最小值和最大值。m2 是 p(i+s,j-s)的任意一种合并方式得到的值,而 c 和 d 分 别是在所有可能的合并中得到的最小值和最大值。依此定义有 a≤m1≤b,c≤m2≤d (1)当 op[i+s]='+'时,显然有 a+c≤m≤b+d (2)当 op[i+s]='*'时,有 min{ac,ad,bc,bd}≤m≤max{ac,ad,bc,bd} 换句话说,主链的最大值和最小值可由子链的最大值和最小值得到。 30.棋盘覆盖问题 . 说明:在一个 2k×2k 个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一 特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的 4 种不同形态的 L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何 2 个 L 型骨牌不得重叠 覆盖。

题目难度:难 设计要求:请使用 C 语言编程,设计一个有效的算法解决棋盘覆盖问题。 设计提示: 当 k>0 时,将 2k×2k 棋盘分割为 4 个 2k-1×2k-1 子棋盘(a)所示。特殊方格必位于 4 个较小子棋盘之一中, 其余 3 个子棋盘中无特殊方格。 为了将这 3 个无特殊方格的子棋盘转 化为特殊棋盘,可以用一个 L 型骨牌覆盖这 3 个较小棋盘的会合处,如(b)所示,从而将原 问题转化为 4 个较小规模的棋盘覆盖问题。递归地使用这种分割,直至棋盘简化为棋盘 1× 1。

31. . 魔方阵 说明:把整数 1 到 n2 排成一个 n×n 方阵, 使方阵中的每一行, 每一列以及对角线上 的数之和都相同。
更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

题目难度:一般 设计要求:要求使用 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)的方法找到的格子中已填过数了, 那么数 k+1 改填在第 k 个数的正下方。即 填在第 i+1 行和第 j 列的那个格子中。编程序实现上述算法,并模拟显示其过程。 32.地图着色 . 说明:地图上有不同国家(不同区域) ,每个国家都与其他一些国家邻接。现要求对地 图着色,使所有的国家与它的邻接的国家有不同的颜色。通常由四种颜色就已足够。 题目难度:较难 设计要求:要求使用 C 语言编程,定义合适的数据结构。最后,需要说明设计思想, 同时给出能够运行的源程序,并给出对应的程序流程图。 设计提示:可采取试探的方法逐步*詈蠼猓窗茨持帜J缴梢桓霾糠纸猓觳 它是否合格。如为合格,在扩展这个部分解向最后解*裨蛭缓细瘢还苋绾卫┱拐 个部分解都不会得到最后解。这时必须放弃已生成的部分解中的某些结果, “回朔”到先前 的部分解,在生成一个部分解,直到获得最后解。这种算法称为回朔算法。以着色一个六个 区域的地图为例。

区域邻接关系 区域 1 2 3 4 5 6 2 1 1 1 1 1 3 3 2 2 3 3 邻接区域 4 4 4 3 6 4 5 0 5 6 0 5 0 6 0 0 6 0

表中数据正是所需输入的数据, 可以用一个 n×n 的矩阵来存放 为 (n 区域数目) 表示邻接区域的结束。 。0 设着色的颜色次序为红、蓝、绿、黄。 对于区域起首先着成红色。对于区域 2,因与区域 1 邻接,所以不能再着红色,而只能 着第二种颜色,即蓝色。同理区域 3 着绿色,区域 4 着黄色,区域 5 着蓝色,区域 6 由于与 区域 1、3、4 和 5 邻接,所以四种颜色都不合适。这时,必须回溯到区域 5,它不能是已着 好的蓝色, 也不能着蓝色的下一种颜色绿色, 因为这会使它与区域 3 同色, 再选下一种颜色, 即黄色,它与区域 1 和 3 不同色。所以区域 5 退去蓝色, 改着黄色。 此后, 区域 6 可着蓝色。 最后,得到的解为各区域的颜色依次为红、蓝、绿、黄、黄、蓝。
更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

采用递归算法: 区域编号以自然数编号 1…n(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; //输出结果 else colorarea(j+1); //进一步着色下一个区域 区域 j 退去 c 色 } 33.模拟人工发牌 .模拟人工发牌 说明:用计算机模拟发牌程序。假设一副扑克牌有 52 张,共 4 个玩家,编写程序统计 出各玩家手里拿的牌的牌面(牌面包括纸牌的大小和花色)。 题目难度:一般 设计要求:要求使用 C 语言编程,定义合适的数据结构。最后,需要说明设计思想, 同时给出能够运行的源程序,并给出对应的程序流程图。 设计提示: 定义一个 4 行 13 列的整数类型的二维数组,每一行分别表示一种花色:黑桃、红桃、 草花、方块。每一列分别表示 A 到 K 共十三个牌点。数组各元素的初始值为 0,表示还没 有发牌。然后给每个数组元素赋予 1 到 4 之间的随机数,表示这张牌随机地发给某个玩家。 例如第一行第七列的元素,表示黑桃 7,其值为 2,表示这张牌发给了第 2 个玩家。依此类 推。 34.搬山游戏 . 说明:设有 n 座山,计算机与人作为比赛的双方,双方轮流搬山。规定每次搬山的数 目不能超过 k 座,谁搬最后一座谁输。游戏开始时,计算机请人输入山的总数(n)和每次允 许搬山的最大数目(k)。然后请人先开始,人输入了需要搬走的山的数目后,计算机马上输 出它搬多少座山,并提示尚余多少座山。双方轮流搬山直到最后一座山搬完为止。计算机显 示谁是赢家,并问人是否要继续比赛。若人不想玩了,可以输入山的总数为 0,计算机便会 告诉人共完了几局,双方胜负如何。 题目难度:较难 设计要求:计算机请人输入山的总数(n)和每次允许搬山的最大数目(k)。然后请人先开 始, 人输入了需要搬走的山的数目后, 计算机马上输出它搬多少座山, 并提示尚余多少座山。 要求使用 C 语言编程,定义合适的数据结构。最后,需要说明设计思想,同时给出能够运行 的源程序,并给出对应的程序流程图。 设计提示: 首先设计计算机参加游戏的算法,计算机每次搬山时应遵循如下原则: (1) 当:剩余山的数目-1<=可移动的最大数 k 时,计算机要移(剩余山的数目-1)座, 以便将最后一座山留给人。 (2) 对于任意正整数 x, y,一定有: 0<=x%(y+1)<=y 因此,对于我们的问题来说,在有 n 座山的情况下,计算机为了将最后一座山留给人,
更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

而且又要控制每次搬山的数目不超过最大数 k,它应搬山的数目要满足下列关系: 搬山数量=(当前所剩的山数-1)%(k+1) 如果算出结果为 0,即整除无余数,则规定只搬一座山,以防止冒进后发生问题。 35. 35.关键路径的求解问题 一.问题的基本阐述: 通常把计划、施工过程、生产流程、程序流程的都当成一个工程。除了很小的工程外、 一般都把工程分为若干个叫做“活动”的子工程。 完成了这些“活动”的子工程, 这个工程 就可以完成了。 通常我们用有向图表示一个工程。在这种有向图中,用顶点表示活动,用 有向边 <Vi,Vj>表示活动 Vi 必须先于活动 Vj 进行。 如果在无有向环的带权有向图中用有向 边表示一个工程中的各项活动(ACTIVITY) ,用有向边上的权值表示活动的持续时间 (DURATION) ,用顶点表示事件(EVENT) ,则这种的有向图叫做用边表示活动的网络,简称 AOE(active on edges)网络。 AOE 网络在某些工程估算方面非常有用。他可以使人们了 解: (1) :研究某个工程至少需要多少时间? (2) :那些活动是影响工程进度的关键? 在 AOE 网络中,有些活动可以并行的进行。从源点到各个顶点,以至从源点到汇点的有 向路径可能不止一条。 这些路径的长度也可能不同。 完成不同路径的活动所需的时间虽然不 同,但只有各条路径上所有活动都完成了,这个工程才算完成。因此,完成整个工程所需的 时间取决于从源点到汇点的最长路径长度, 即在这条路径上所有活动的持续时间之和。 这条 路径长度就叫做关键路径(critical path) 。 二.:设计步骤: 1: 以某一工程为蓝本,采用图的结构表示实际的工程计划的时间。 2: 调查以分析和预测这个工程计划个阶段的时间。 3: 用调查的结果建立AOE 网(Activity On Edge Network) ,即边表示活动 的网络,并用图的形式表示。 4: 用图来存储这些信息。 5: 用 CreateGraphic();函数建立 AOE 图。 6: 用 SearchMapPath();函数求出最大路径,并打印出关键路径。 7:编写代码 8: 测试 三. 设计代码:(要求用 C 语言或 JAVA 语言实现) 36.囚徒困境的实际问题: 36.囚徒困境的实际问题: 的实际问题 一.基本问题阐述: 有两个参与者和一个庄家。参与者每人有一式两张卡片,各印有“合作”和“背叛”。参与 者各把一张卡片文字面朝下, 放在庄家面前。 文字面朝下排除了参与者知道对方选择的可能 性。然后,庄家翻开两个参与者卡片,根据以下规则支付利益: 一人背叛、一人合作:背叛者得 5 分(背叛诱惑),合作者 0 分(受骗支付)。 二人都合作:各得 3 分(合作报酬)。 二人都背叛:各得 1 分(背叛惩罚)。 二.求解(要求用 C 语言或 JAVA 语言) 1.每个人所能得分的所有情况及可得的最高分和最低分; 2.两个人能得分和的所有情况及最高分和最低分 3. 比较互相背叛的及单独背叛,合作获分比背叛高还是低
更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

37. 语言,设计一个学生的学籍管理系统; 37.用 C 语言或 JAVA 语言,设计一个学生的学籍管理系统; 要求:1.要有对学生的各信息进行各种操作的功能,比如添加删除学生等等 2.设计过程中会用到排序的算法,请你总结各种经典的排序算法, 3.设计过程中会用到查找得法,请你总结各种经典的查找算法 4.写出具体的设计过程

更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

37.

查找算法集锦

说明: 说明:查找,根据给定的某个值,在查找表(已经排好序)中确定一个其关键字等于给 定的记录或数据元素。若表中存在这样的一个记录,则称查找是成功的,此时查找的结果为 给出整个记录的信息, 或指示该记录在查找表中的位置; 若表中不存在关键字等于给定值的 记录,则称查找不成功。查找算法有多种,各有优缺点。 题目难度: 题目难度:难 设计要求: 设计要求:要求使用 C 语言编程,至少完成下述查找算法 1) 顺序查找 从表中最后一个记录开始,逐个进行记录的关键字和给定值的比较, 若某个记录的关键字和给定值比较相等,则查找成功,找到所查记录;反之,查找 不成功。 2) 折半查找 先确定待查记录所在的范围(区间) ,然后逐步缩小范围直到找到或 找不到该记录为止。 3) 二叉排序树查找 二叉排序树或者是一棵空树;或者是具有下列性质的二叉树: I. 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; II. 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; III. 它的左、右子树了分别为二叉排序树。 二叉排序树的插入和删除 二叉排序树是一种动态树表,其特点是,树的结构通常不是一资生成的,面是在查 找过程中, 当树中不存在关键字等于给定值的结点时再进行插入。 新插入的结点一定是 一个新添加的叶子结点, 并且是查找不成功时查找路径上访问的最后一个结点的左孩子 或右孩子结点。 设计提示: 设计提示: 参考相关资料、书籍,理解各种查找方法; 定义恰当的数据结构。

38.排序算法集锦 .
说明: 说明:排序,将一个数据元素的无序序列重新排列成一个按关键字有序的序列,排序的 顺序有升序和降序。数据可以是任意类型,如果是字符串则按字符的 ASCII 码值进行排序。 排序的方法有 20 多种,各有优缺点。 题目难度: 题目难度:难 设计要求: 设计要求:要求使用 C 语言编程,至少完成下述排序算法 (1)选择法 每一趟在 n-i+1(i=1,2,...n-1)个记录中选取关键字最小的记录作为有序序列 中第 i 个记录。包括:简单选择排序、树形选择排序和堆排序 (2)插入排序 包括:直接插入排序 是将一个记录插入到已排好序的有序表中,从而得到一个新的、 记录数增 1 的有序表 折半插入排序 为了提高查找速度,可以采用折半查找,这种排序称折半插入排序。 2-路插入排序 为减少排序过程中移动记录的次数, 在折半插入排序的基础上加以改 进: (3)冒泡排序法 (4)归并排序法 将两个或两个以上的有序表组合成一个新的有序表的方法叫归并。

更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

(5)合并排序法 将待排序元素分成大小大致相同的 2 个子集合, 分别对 2 个子集合进 行排序,最终将排好序的子集合合并成为所要求的排好序的集合。 (6)快速排序法 在快速排序中, 记录的比较和交换是从两端向中间进行的, 关键字较 大的记录一次就能交换到后面单元, 关键字较小的记录一次就能交换到前面单元, 记录每次 移动的距离较大,因而总的比较和移动次数较少。 设计提示: 设计提示: 参考相关资料、书籍,理解各种排序方法; 定义恰当的数据结构。

39.巨大整数的乘法(分治法) .巨大整数的乘法(分治法)
说明: 说明:此 2 数很大,以至于其已经超过了计算机能表示的整数的范围,或其乘积已经超 过了计算机能表示的整数的范围。 题目难度: 题目难度:难 设计要求: 设计要求:请使用 C 语言编程,设计一个有效的算法,可以进行两个 n 位(二进制数) 大整数的乘法运算。 设计提示: 设计提示: 将此 2 数转换为 2 进制字符串,并进行分段。

X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd 为了降低时间复杂度,必须减少乘法的次数。 1.XY = ac 2n + ((a-c)(b-d)+ac+bd) 2n/2 + bd 2.XY = ac 2n + ((a+c)(b+d)-ac-bd) 2n/2 + bd 考虑到 a+c,b+d 可能得到 m+1 位的结果,使问题的规模变大,故不选择第 2 种方案。 如果将大整数分成更多段, 用更复杂的方式把它们组合起来, 将有可能得到更优的算法。

40.蚂蚁觅食过程模拟 .
说明: 说明: 1) 各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。 2) 当一只找到食物以后,它会向环境释放一种信息素,吸引其他的蚂蚁过来,这样越来越 多的蚂蚁会找到食物。 3) 有些蚂蚁并没有象其它蚂蚁一样总重复同样的路, 他们会另辟蹊径, 如果令开辟的道路 比原来的其他道路更短,那么,渐渐,更多的蚂蚁被吸引到这条较短的路上来。 4) 最后,经过一段时间运行,可能会出现一条最短的路径被大多数蚂蚁重复着。 题目难度: 题目难度:难 设计要求:请使用 C 语言编程,设计一个有效的算法,模拟蚂蚁觅食的过程。 设计提示: 设计提示:
更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

1) 2) 3) 4)

要让蚂蚁能够避开*铮 就必须根据适当的地形给它编进指令让他们能够巧妙的避开 *铮 要让蚂蚁找到食物,就需要让他们遍历空间上的所有点; 如果要让蚂蚁找到最短的路径,那么需要计算所有可能的路径并且比较它们的大小。 更重要的是,你要小心翼翼的编程,因为程序的错误也许会让你前功尽弃。

41.棋盘覆盖问题(递归法) .棋盘覆盖问题(递归法)
说明: 说明:在一个 2k×2k 个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一 特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的 4 种不同形态的 L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何 2 个 L 型骨牌不得重叠 覆盖。

题目难度: 题目难度:难 设计要求: 设计要求:请使用 C 语言编程,设计一个有效的算法解决棋盘覆盖问题。 设计提示: 设计提示: 当 k>0 时,将 2k×2k 棋盘分割为 4 个 2k-1×2k-1 子棋盘(a)所示。特殊方格必位于 4 个较小子棋盘之一中, 其余 3 个子棋盘中无特殊方格。 为了将这 3 个无特殊方格的子棋盘转 化为特殊棋盘,可以用一个 L 型骨牌覆盖这 3 个较小棋盘的会合处,如(b)所示,从而将原 问题转化为 4 个较小规模的棋盘覆盖问题。递归地使用这种分割,直至棋盘简化为棋盘 1× 1。

42.循环赛日程表(动态规划法) .循环赛日程表(动态规划法)
说明: 说明:设计一个满足以下要求的比赛日程表: (1)每个选手必须与其他 n-1 个选手各赛一次; (2)每个选手一天只能赛一次; (3)循环赛一共进行 n-1 天。 题目难度: 题目难度:较难 设计要求: 设计要求:请使用 C 语言编程,设计一个有效的算法解决循环赛日程表问题。
更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

设计提示: 设计提示:按分治策略,将所有的选手分为两半,n 个选手的比赛日程表就可以通过为 n/2 个选手设计的比赛日程表来决定。递归地用对选手进行分割,直到只剩下 2 个选手时,比赛 日程表的制定就变得很简单。这时只要让这 2 个选手进行比赛就可以了。

43.完全加括号的矩阵连乘积(动态规划法) .完全加括号的矩阵连乘积(动态规划法)
说明: 说明:完全加括号的矩阵连乘积可递归地定义为: (1)单个矩阵是完全加括号的; (2)矩阵连乘积 A 是完全加括号的,则 A 可表示为 2 个完全加括号的矩阵连乘积 B 和 C 的乘积并加括号,即 A=(BC) 。如下例: 题目难度: 题目难度:较难 设计要求: 设计要求:请使用 C 语言编程,设计一个有效的算法解决下述问题:给定 n 个矩阵 {A1,A2,…,An} ,其中 Ai 与 Ai+1 是可乘的,i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计 算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。 设计提示: 设计提示:由于矩阵乘法满足结合律,计算矩阵的连乘可以有许多不同的计算次序。这种计 算次序可以用加括号的方式来确定。 若一个矩阵连乘积的计算次序完全确定, 也就是说该连 乘积已完全加括号,则可以依此次序反复调用 2 个矩阵相乘的标准算法计算出矩阵连乘积。 将矩阵连乘积 简记为 A[i:j] ,这里 i≤j

考察计算 A[i:j]的最优计算次序。 设这个计算次序在矩阵 Ak 和 Ak+1 之间将矩阵链断开, i≤k<j,则其相应完全加括号方式为 计算量:A[i:k]的计算量加上 A[k+1:j]的计算量,再加上 A[i:k]和 A[k+1:j]相乘的计算量。

44.最长公共子序列(动态规划法) .最长公共子序列(动态规划法)
说明: 说明:若给定序列 X={x1,x2,…,xm},则另一序列 Z={z1,z2,…,zk},是 X 的子序列是指存在一 个严格递增下标序列{i1,i2,…,ik}使得对于所有 j=1,2,…,k 有:zj=xij。例如,序列 Z={B,C, D,B}是序列 X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5, 7}。给定 2 个序列 X 和 Y,当另一序列 Z 既是 X 的子序列又是 Y 的子序列时,称 Z 是序列 X 和 Y 的公共子序列。 题目难度: 题目难度:难 设计要求: 设计要求:请使用 C 语言编程,设计一个有效的算法解决下述问题:给定 2 个序列 X={x1,x2,…,xm}和 Y={y1,y2,…,yn},找出 X 和 Y 的最长公共子序列。 设计提示: 设计提示: 设序列 X={x1,x2,…,xm}和 Y={y1,y2,…,yn}的最长公共子序列为 Z={z1,z2,…,zk} ,则 (1)若 xm=yn,则 zk=xm=yn,且 zk-1 是 xm-1 和 yn-1 的最长公共子序列。 (2)若 xm≠yn 且 zk≠xm,则 Z 是 xm-1 和 Y 的最长公共子序列。 (3)若 xm≠yn 且 zk≠yn,则 Z 是 X 和 yn-1 的最长公共子序列。 由此可见,2 个序列的最长公共子序列包含了这 2 个序列的前缀的最长公共子序列。 由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用 c[i][j]记录 序列和的最长公共子序列的长度。其中, Xi={x1,x2,…,xi};Yj={y1,y2,…,yj}。当 i=0 或 j=0 时,空序列是 Xi 和 Yj 的最长公共子序列。故此时 C[i][j]=0。其他情况下,由最优子结构性 质可建立递归关系如下:

? c[i ][ j ] = ? c[i ? 1][ j ? 1] + 1 ?max{c[i ][ j ? 1], c[i ? 1][ j ]} ?

? 0 i= 更多精彩,尽在大学生校园网(www.vvschool.cn)0,

j=0

i, j > 0; xi = y j i, j > 0; xi ≠ y j

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

45.多边形游戏(动态规划法) .多边形游戏(动态规划法
说明: 说明: 多边形游戏是一个单人玩的游戏, 开始时有一个由 n 个顶点构成的多边形。 每个顶点被 赋予一个整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从 1 到 n 编号。 游戏第 1 步,将一条边删除。随后 n-1 步按以下方式操作: (1)选择一条边 E 以及由 E 连接着的 2 个顶点 V1 和 V2; (2)用一个新的顶点取代边 E 以及由 E 连接着的 2 个顶点 V1 和 V2。 将由顶点 V1 和 V2 的整 数值通过边 E 上的运算得到的结果赋予新顶点。 最后,所有边都被删除,游戏结束。游戏的得分就是所剩顶点上的整数值。 题目难度: 题目难度:较难 设计要求: 设计要求: 请使用 C 语言编程,设计一个有效的算法解决下述问题:对于给定的多边形,计算最高得 分。 设计提示: 设计提示: 在所给多边形中, 从顶点 i(1≤i≤n)开始, 长度为 j(链中有 j 个顶点)的顺时针链 p(i, 可 j) 表示为 v[i],op[i+1],…,v[i+j-1]。 如果这条链的最后一次合并运算在 op[i+s]处发生(1≤s≤j-1), 则可在 op[i+s]处将链分割 为 2 个子链 p(i,s)和 p(i+s,j-s)。 设 m1 是对子链 p(i,s)的任意一种合并方式得到的值,而 a 和 b 分别是在所有可能的合 并中得到的最小值和最大值。m2 是 p(i+s,j-s)的任意一种合并方式得到的值,而 c 和 d 分 别是在所有可能的合并中得到的最小值和最大值。依此定义有 a≤m1≤b,c≤m2≤d (1)当 op[i+s]='+'时,显然有 a+c≤m≤b+d (2)当 op[i+s]='*'时,有 min{ac,ad,bc,bd}≤m≤max{ac,ad,bc,bd} 换句话说,主链的最大值和最小值可由子链的最大值和最小值得到。

46.图像压缩问题(动态规划法) .图像压缩问题(动态规划法)
说明: 说明: 图像的变位压缩存储格式将所给的象素点序列{p1,p2,…,pn},0≤pi≤255 分割成 m 个连 续段 S1,S2,…,Sm。 i ?i1 个象素段 Si 中(1≤i≤m), l[i]个象素,且该段中每个象素都只用 b[i] 第 有 位表示。设 t[i ] = 则第 i 个象素段 Si 为 l[ k ]


k =1

,则 h≤b[i] ≤8。因此需要用 3 位表示 b[i],如果限 制 1≤l[i] ≤255, 则需要用 8 位表示 l[i]。 因此, m 个象素段所需的存储空间为 l[i]*b[i]+11 第i 位。按此格式存储象素序列{p1,p2,…,pn},需要 l[i ] * b[i ] + 11m 位的存储空间。 i =1 题目难度:难 题目难度 设计要求: 设计要求:请使用 C 语言编程,设计一个有效的算法解决下述问题:确定象素序列 {p1,p2,…,pn}的最优分段, 使得依此分段所需的存储空间最少。 (每个分段的长度不超过 256 位。 ) 设计提示: 设计提示:设 l[i],b[i],是{p1,p2,…,pn}的最优分段。显而易见,l[1],b[1]是{p1,…,pl[1]} 的最优分段,且 l[i],b[i],是{pl[1]+1,…,pn}的最优分段。即图像压缩问题满足最优子结构 性质。 设 s[i],1≤i≤n,是象素序列{p1,…,pn}的最优分段所需的存储位数。由最优子结构性质易 知:

? ? ?? 设 hi = ?log? t [i ]+1max]+l [i ] pk + 1?? ≤ k ≤t [ i ? ?? ?



s[i ] =

1≤ k ≤ min{i , 256}

min

{s[i ? k ] + k * b max(i ? k + 1, i )} + 11

更多精彩,尽在大学生校园网(www.vvschool.cn)

大学生校园网—VvSchool.CN

努力打造的学生最实用的网络*台!

bmax(i, j ) = ?log? max{ pk } + 1?? 其中: ? ? ?
i≤k ≤ j

? ?

? ??

更多精彩,尽在大学生校园网(www.vvschool.cn)




友情链接: