编程训练题目（转）
转自：http://blog.163.com/goodskyfly/
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个方块均“不可
通”，则应从“当前路径”中删除该通道块。使用栈结构记录当前路径，当前位置入栈表示向前行，出栈则表示从当前位置退回。
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） 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
5. 图的遍历
功能：实现图的深度优先, 广度优先遍历算法，并输出原图结构及遍历结果。
分步实施：
1) 初步完成总体设计，搭好框架；
2) 完成最低要求：两种必须都要实现，写出画图的思路；
3) 进一步要求：画出图的结构，有兴趣的同学可以进一步改进图的效果。
要求：1）界面友好，函数功能要划分好
2）总体设计应画一流程图
3）程序要加必要的注释
4) 要提供程序测试方案
5) 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
6． n维矩阵乘法：A B－1
功能：设计一个矩阵相乘的程序，首先从键盘输入两个矩阵a，b的内容，并输出两个矩阵，
输出ab－1
结果。
分步实施：
1） 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；
2） 完成最低要求：建立一个文件，可完成2维矩阵的情况；
3） 一步要求：通过键盘输入维数n。有兴趣的同学可以自己扩充系统功能。
要求：1）界面友好，函数功能要划分好
2）总体设计应画一流程图
3）程序要加必要的注释
4）要提供程序测试方案
5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
7．
数组应用
功能： 按照行优先顺序将输入的数据建成4维数组，再按照列优先顺序输出结果，给出任意处的元素值，并给出对应的一维数组中的序号。
分步实施：
1．初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；
2． 完成最低要求：完成第一个功能；
3． 进一步要求：进一步完成后续功能。有兴趣的同学可以自己扩充系统功能。
要求：1）界面友好，函数功能要划分好
2）总体设计应画一流程图
3）程序要加必要的注释
4）要提供程序测试方案
5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
8．
数组应用2
功能： 读入数组下标，求出数组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） 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
11．
公园的导游图
功能：给出一张某公园的导游图，游客通过终端询问可知：
从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。
分步实施：
1． 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；
2． 完成最低要求：建立一个文件，包括5个景点情况，能完成遍历功能；
3． 进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。
要求：1）界面友好，函数功能要划分好
2）总体设计应画一流程图
3）程序要加必要的注释
4）要提供程序测试方案
5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
12．
商店存货管理系统
功能：建立一商店存货管理系统，要求每次出货时取进货时间最早且最接近保质期中止时间的货物。
分步实施：
1． 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；
2． 完成最低要求：建立一个文件，包括5个种类的货物情况，能对商品信息进行扩充（追加），修改和删除以及简单的排序；
3． 进一步要求：扩充商品数量，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。
要求：1）界面友好，函数功能要划分好
2）总体设计应画一流程图
3）程序要加必要的注释
4）要提供程序测试方案
5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
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) 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
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
17．分词算法----正向最大匹配分词算法
说明：
何为分词？中文分词与其他的分词又有什么不同呢？分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。在英文的行文中，单词之间是以空格作为自
然分界符的，而中文只是字、句和段可以通过明显的分界符来简单划界，唯独词没有一个形式上的分界符，虽然英文也同样存在短语的划分问题，但是在词这一层
上，中文比之英文要复杂的多、困难的多。
正向最大匹配分词算法就是从左到右进行切词，以最大词组进行匹配。例如：“中华人民共和国成立了。”这个词可以切分为“中华/人民/共和国/成立/了。”也可以切分成“中华人民共和国/成立/了。”而后一种就是最大正向匹配算法了。
题目难度：一般
设计要求：利用VC++、JAVA之类有界面的编程工具进行编写。要求输入一篇文章，在一定的时间之内进行分词，并显示分词时间。
并根据分词效果，提出改进方案。
设计提示：词组数据库由教师给出，学生也可以自己添加词汇，学生建立数据的连接，并进行分词匹配。
18． 野人过河问题
说明：野人过河问题属于人工智能学科中的一个经典问题，问题描述如下：
有三个僧人和野人准备渡过一条河，但是只有一条船，而且船每次最多可以载两个人。现在他同在河的一边，想渡过河去，条件是：在河的任何一边必须保证僧人的数目大于等于野人的数目，否则野人就会把僧人吃掉，请给出渡河方案。
题目难度：较难
设计要求：模拟僧人和野人的渡河顺序，要求使用C语言编程，定义合适的数据结构。最后，需要说明设计思想，同时给出能够运行的源程序，并给出对应的程序流程图。
设计提示：先分析问题的初始状态和目标状态，假设河分为甲岸和乙岸：
初始状态：甲岸，3野人，3牧师；
乙岸，0野人，0牧师；
船停在甲岸，船上有0个人；
目标状态：甲岸，0野人，0牧师；
乙岸，3野人，3牧师；
船停在乙岸，船上有0个人；
整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的。考虑用什么样的数据结构和搜索算法
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个人或鬼，而且至少要有一个人或鬼船才能行驶。请设计一种算法，把人和鬼都送到对岸。
注：不论是在河边、船上，如果人鬼数量相同，则鬼和人能和谐相处，鬼不吃人，否则，鬼吃掉人。要求算法能给出整个运送过程，包括每次船行驶的方向（是驶向
对岸还是返回），船上的人和鬼数量。
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 1／6＝0.1(6)
5 7 1
1 250 5/7=0.(714285)
00 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
P U
AT RIGHT
R
T
Unable to make two crosses
23
．校园导游咨询（为来访的客人提供各种信息服务）
1、基本要求：
1）设计大学城平面图，在校园景点选10个左右景点。以图中顶点表示大学城内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。
2）为来访客人提供图中任意景点相关信息的查询。
3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。
实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。
24．十进制数与八进制数互换的实现
要求: 采用相应的数据结构,实现十进制数到八进制数的转换.
25．大整数乘法的实现
要求: 以数组这种数据结构来实现,整数最大允许的长度为80位.
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语言编程，设计一个有效的算法解决下述问题：对于给定的多边形，计算最高得分。
设计提示：
在所给多边形中，从顶点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方阵， 使方阵中的每一行， 每一列以及对角线上的数之和都相同。
题目难度：一般
设计要求：要求使用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语言编程，定义合适的数据结构。最后，需要说明设计思想，同时给出能够运行的源程序，并给出对应的程序流程图。
设计提示：可采取试探的方法逐步逼近最后解，即按某种模式生成一个部分解，检查它是否合格。如为合格，在扩展这个部分解向最后解逼近，否则为不合
格，不管如何扩展这个部分解都不会得到最后解。这时必须放弃已生成的部分解中的某些结果，“回朔”到先前的部分解，在生成一个部分解，直到获得最后解。这
种算法称为回朔算法。以着色一个六个区域的地图为例。
区域邻接关系
|
区域 |
邻接区域 |
|||||
|
1 |
2 |
3 |
4 |
5 |
6 |
0 |
|
2 |
1 |
3 |
4 |
0 |
|
|
|
3 |
1 |
2 |
4 |
5 |
6 |
0 |
|
4 |
1 |
2 |
3 |
6 |
0 |
|
|
5 |
1 |
3 |
6 |
0 |
|
|
|
6 |
1 |
3 |
4 |
5 |
0 |
|
表中数据正是所需输入的数据，可以用一个n×n的矩阵来存放（n为区域数目）。0表示邻接区域的结束。
设着色的颜色次序为红、蓝、绿、黄。
对于区域起首先着成红色。对于区域2，因与区域1邻接，所以不能再着红色，而只能着第二种颜色，即蓝色。同理区域3着绿色，区域4着黄色，区域5着
蓝色，区域6由于与区域1、3、4和5邻接，所以四种颜色都不合适。这时，必须回溯到区域5，它不能是已着好的蓝色，也不能着蓝色的下一种颜色绿色，因为
这会使它与区域3同色，再选下一种颜色，即黄色，它与区域1和3不同色。所以区域5退去蓝色，改着黄色。此后，区域6可着蓝色。最后，得到的解为各区域的
颜色依次为红、蓝、绿、黄、黄、蓝。
采用递归算法：
区域编号以自然数编号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座山的情况下，计算机为了将最后一座山留给人，而且又要控制每次搬山的数目不超过最大数k，它应搬山的数目要满足下列关系：
搬山数量＝（当前所剩的山数－1）％（k+1）
如果算出结果为0，即整除无余数，则规定只搬一座山，以防止冒进后发生问题。
35．关键路径的求解问题
一.问题的基本阐述:
通常把计划、施工过程、生产流程、程序流程的都当成一个工程。除了很小的工程外、一般都把工程分为若干个叫做“活动”的子工程。完成了这些“活动”
的子工程，这个工程就可以完成了。通常我们用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边
<Vi,Vj>表示活动Vi必须先于活动Vj进行。如果在无有向环的带权有向图中用有向边表示一个工程中的各项活动（ACTIVITY），用
有向边上的权值表示活动的持续时间（DURATION），用顶点表示事件（EVENT），则这种的有向图叫做用边表示活动的网络，简称
AOE（active on edges）网络。 AOE网络在某些工程估算方面非常有用。他可以使人们了解：
（1）：研究某个工程至少需要多少时间？
（2）：那些活动是影响工程进度的关键？
在AOE网络中，有些活动可以并行的进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的
活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这
条路径上所有活动的持续时间之和。这条路径长度就叫做关键路径（critical path）。
二.：设计步骤：
1: 以某一工程为蓝本，采用图的结构表示实际的工程计划的时间。
2: 调查以分析和预测这个工程计划个阶段的时间。
3: 用调查的结果建立ＡＯE网（Activity On Edge Network），即边表示活动的网络，并用图的形式表示。
4: 用图来存储这些信息。
5: 用CreateGraphic();函数建立AOE图。
6: 用SearchMapPath();函数求出最大路径，并打印出关键路径。
7:编写代码
8: 测试
三. 设计代码：(要求用C语言或JAVA语言实现)
36．囚徒困境的实际问题:
一.基本问题阐述:
有两个参与者和一个庄家。参与者每人有一式两张卡片，各印有“合作”和“背叛”。参与者各把一张卡片文字面朝下，放在庄家面前。文字面朝下排除了参与者知道对方选择的可能性。然后，庄家翻开两个参与者卡片，根据以下规则支付利益：
一人背叛、一人合作：背叛者得5分（背叛诱惑），合作者0分（受骗支付）。
二人都合作：各得3分（合作报酬）。
二人都背叛：各得1分（背叛惩罚）。
二.求解(要求用C语言或JAVA语言)
1.每个人所能得分的所有情况及可得的最高分和最低分;
2.两个人能得分和的所有情况及最高分和最低分
3. 比较互相背叛的及单独背叛，合作获分比背叛高还是低
37．用C语言或JAVA语言,设计一个学生的学籍管理系统;
要求:1.要有对学生的各信息进行各种操作的功能,比如添加删除学生等等
2.设计过程中会用到排序的算法,请你总结各种经典的排序算法,
3.设计过程中会用到查找得法,请你总结各种经典的查找算法
4.写出具体的设计过程
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）归并排序法 将两个或两个以上的有序表组合成一个新的有序表的方法叫归并。
（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语言编程，设计一个有效的算法，模拟蚂蚁觅食的过程。
设计提示：
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语言编程，设计一个有效的算法解决循环赛日程表问题。
设计提示：
按分治策略，将所有的选手分为两半，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。其他情况下，由最优子结构性质可建立递归关系如下：
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个象素段Si中(1≤i≤m)，有l[i]个象素,且该段中每个象素都只用b[i]位表示。
设 则第i个象素段Si为
设 ，则h≤b[i]
≤8。因此需要用3位表示b[i],如果限制1≤l[i]
≤255，则需要用8位表示l[i]。因此，第i个象素段所需的存储空间为l[i]*b[i]+11位。按此格式存储象素序列{p1,p2,…,pn}，
需要 位的存储空间。
转自：http://blog.163.com/goodskyfly/