一、目的要求
   
   
1 ．学会对相对复杂问题的系统设计、数据结构设计、算法设计和程序设计。

2 ．熟练掌握块状结构程序的设计方法。

3 ．掌握处理大数据量的程序设计方法。

4 ．掌握文件输入输出的操作方法。

5 ．掌握初步的菜单设计方法。

6 ．学会编写软件设计报告。

  
二、启事与范例
  
  
 1 、（难度等级 B ，人数 1 ）穷举搜索法

　　穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和实验，并从中找出那些符合要求的候选解作为问题的解。

　　[题目 7.1] 将 A 、 B 、 C 、 D 、 E 、 F 这 6 个变量排成如图 7.1 （ a ）所示的三角形，这 6 个变量分别取 [1 ，6] 上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。如图 7.1 （ b ）就是一个解。

2 、（难度等级 B ，人数 1 ）递推法

　　递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为 N 的解，当 N=1 时，解或为已知，或能非常方便地得到。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为 i-1 的解后，由问题的递推性质，能从已求得的规模为 1 、 2 、 … 、 i-1 的一系列解，构造问题规模为 i 的解。这样，程序可从 i=0 或 i=1 出发，由已知解，通过递推得到问题规模为 N 的解。

　　[题目 7.2] 求出 n! ，设 n ≥ 2 且 n ≤ 50 。

　　提示：因为计算机对整数位数的限制，宜用数组 a[] 来存储大整数 i! 。设数组的每个元素存放大整数的一位数字，并将整数 i! 自个位到高位顺序存放于 a[0] ， a[1] ， … 中。

　　为求 i! ，可利用已求得的（ i-1 ） ! 。 1!=1 可立即得到。所以程序可采用 递推法，由 1! 求得 2 ！， 由 2 ! 求得 3 ！， … ， 由 （ i-1 ） ! 求得 i! ， …… 直到求得 n! 后结束。

　　由 （ i-1 ） ! 求得 i! 的具体办法：当（ i-1 ） ! 已按上述约定存于数组 a[] 时，可用 i 依次去乘（ i-1 ） ! 的个位、十位、 …… 来得到。当用 i 乘（ i-1 ） ! 的第 j 位求 i! 的第 j 位时，需要考虑求 i! 的第 j-1 位时的进位 c 。该进位 c 与 i 乘上（ i-1 ） ! 的第 j 位的乘机之和为 t ，可以得到 i! 的第 j 位数字和新的进位。

3 、（难度等级 D ，人数 1 ）递归法

　　能采用递归描述的算法一般具有如下特征：为求规模为 N 的问题，设法将它分解成一些规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模稍大问题的解。特别地，当规模 N=1 时，能直接得到解。

　　[题目 7.3] 背包问题。设有不同价值、不同重量的物品 n 件，从这 n 件物品中选取一部分物品的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和为最大。

　　提示：设 n 件物品的重量分别为w0 、w1、 … 、wn-1，物品的价值分别为v0、v1、 … 、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案，并保留了其中总价值最大的方案于数组 option[] ，该方案的总价值存于变量 vmax 。当前正在考虑新方案，其物品选择情况保存于数组 cop[] 。假定当前方案已考虑了前 i-1 件物品，现在要考虑第 i 件物品；当前方案已包含的物品的重量之和为 tw ；至此，若其余物品都选择是可能的话，本方案能达到的总价值的期望值设为 tv 。算法引入 tv 是当一旦当前方案的总价值的期望值也小于前面方案的总价值 vmax 时，继续考虑当前方案变成无意义的工作，应当终止当前方案，立即去考察下一个方案。

　　对于第 i 件物品的选择有两种可能：

　　（ 1 ）物品 i 被选择。这种可能性仅当包含它不会超过方案总重量的限制时才是可行的。选中后，继续递归去考虑其余物品的选择。

　　（ 2 ）物品 i 不被选择。这种可能性仅当不包含物品 i 也有可能会找到价值更大的方案的情况。

4 、（难度等级 D ，人数 2-3 ）回溯法

　　回溯法也称试探法。该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。若当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，并继续试探的过程称为向前试探。

　　[题目 7.4] 求出在一个n x n的棋盘上，放置 n 个不能互相捕捉的国际象棋“皇后”的所有布局。

　　提示：这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线四个方向相互捕捉。如图 7.2 所示，一个皇后放在棋盘的第四行第三列位置上，则棋盘上凡打“ * ”的位置上的皇后就能与第四行第三列位置上的皇后相互捕捉。从图 7.2 得到以下启示：一个合适的解应是在每列、每行确实有一个皇后，且在一条斜线上也最多只有一个皇后。

　　求解过程从空配置开始，在第一列至第 m 列为合理配置的基础上，再配置第 m+1 列。直至第 n 列配置也是合理时，就找到了一个解。接着改变第 n 列配置，希望获得下一个解。另外，在任一列上，可能有 n 种配置，开始时，配置在第一行，以后改变时，顺序选择第二行、第三行、 … 直至第 n 行。当直至第 n 行也找不到一个合理的配置时，就要回溯，去改变前一列的配置。

　　求解皇后问题的算法如下：

　　{

　　　输入棋盘大小值 n ；

　　　m=0 ； /* 从空配置开始 */

　　　good=1 ； /* 空配置中皇后不相互捕捉 */

　　　do

　　　{

　　　　if(good)

　　　　　if(m= =n)

　　　　　{

　　　　　　输出解；

　　　　　　改变之，形成下一个候选解；

　　　　　}

　　　　　else 扩展候选解至下一列；

　　　　else 改变之，形成下一个候选解；

　　　　good= 检查当前候选解的合理性；

　　　}while (m!=0)

　　}

　　[题目 7.5] 马的遍历问题。在 8 x 8 方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
  
三、处理类
  
  
  [题目 7.6] （难度等级 B ，人数 1-2 ）十佳运动员统计

　　国家体委与中央电视台联合举办十佳运动员有奖评选活动，具体说明如下：

　　（ 1 ）国家体委组织有关人士评出了如下 20 个候选人名单。

运动员编号	运动员姓名
01	田 亮
02	孙 雯
…	…
20	邓亚苹

　　（ 2 ）中央电视台在网上设立了投票站供市民投票，以便用计算机进行统计和核对。选票格式如下：

选票编号	0000001
投票人姓名					投票人地址
拟选运动员编号

　　选票号为 7 位数字，有效的运动员编号是 01~20 。

　　（ 3 ）计算机统计的具体任务是：

　　　① 统计出各侯选人的得票数，并根据得票数排定名次，选出十佳。

　　　② 根据命中率选出十个获奖的参选者，并排定名次。

　　　　命中率 = 命中分 + 次序分

　　　　命中分：选中十佳中的一个即得 10 分，选中 n 个得 n*10 分（不考虑次序）。

　　　　次序分：选票中的第一个运动员与十佳中的第一名相符（简称选中第一名）得 9 分，选中第二名得 8 分，……，选中第十名得 0 分。

　　（ 4 ）编写出完成以上统计任务的程序。

　　具体要求如下：

　　　① 候选人数据和选票数据应以文本文件的方式分别存放在两个文件中，选票中参选人的地址可以不考虑。

　　　② 程序中，对选票数据要求采用结构体作数据结构。

　　　③ 程序除能完成统计功能外，应具有核对选票数据的功能，并且，每一功能的实现要采用点菜单的方式进行（使用简单的文本菜单），菜单至少包含以下几项：

　　　　1 ．统计

　　　　2 ．核对选票

　　　　3 ．退出

　　　④ 程序和数据中不提倡使用汉字，相应的地方用英文代替。

　　　⑤ 各大功能和各个相对独立的任务要求编写成独立的函数，主函数只用于管理菜单和组织调用各功能函数。

　　　⑥ 统计结果除在屏幕显示外，还要求输出到文件中。

[题目 7.7] 方格网上观测数据的窗口滑动平均处理。

　　题 意：

　　已知 M 行 N 列方格网上的观测数据，为了压制其中的高频干扰信号，使各观测点之间的数据平滑过度，要求编写程序对该方格网上的观测数据进行窗口滑动平均处理。

　　所谓窗口滑动平均，就是用 9 点或 25 点的窗口在观测区域上移动，每次移动时窗口中心所对应的观测点重新取值为：窗口内所有观测点数据的平均值。

　　对于 9 点圆滑有：

a_i,j=(a_i-1,j-1+a_i-1,j+a_i-1,j+1+a_i,j-1+a_i,j+a_i,j+1+a_i+1,j-1+a_i+1,j+a_i+1,j+1)/9

　　对于 25 点圆滑的情况可自己列出。

　　要 求：

　　　①使用文件输入输出，已知数据要事先存在文件中，处理结果要输出到文件中。

　　　② 观测点的行数和列数任意。

　　　③ 使用 9 点还是 25 点圆滑可选。

　　　④ 对于窗口跨越观测区域内外的边缘点，只取其中落在观测区域内的数据参加平均值计算。

[题目 7.8] （难度等级 C ，人数 1 ）字型加阴影

　　为增加屏幕字符或汉字的艺术效果，常常需要对字型加阴影，增加立体感，请编程实现该功能。为简化问题，假设原字型点阵存在一个二维数组 W （ 1:48 , 1:48 ）中。字型象素点的值为 0 。在右下方加阴影，阴影宽度为 2 ，阴影象素点的值为 5 。

　　提示：从上到下逐行扫描含有字型的二维数组。对于扫描到的点（ i , j ），如果（ i , j ）值为 0 ，说明是背景象素点，不做任何处理。如果（ i , j ）值为 10 ，说明是字型象素点，则看（ i+2, j+2 ）点的值。若（ i+2 , j+2 ）点的值为 10 ，表明（ i+2 , j+2 ）点与（ i , j ）点一样同为字型象素点，不做任何处理。若（ i+2 , j+2 ）点的值为 0 ，则将其值置为 5 ，成为（ i , j ）点的阴影点。

[题目 7.9] （难度等级 D ，人数 2-3 ）全屏幕的编辑小软件。

　　利用 TC 或 VC 实现一个全屏幕的编辑小软件，具备以下简单功能：

　　（ 1 ）全屏幕编辑操作。

　　（ 2 ）新建、打开、保存等文件功能；

　　（ 3 ）剪切、复制、粘贴，查找、替换等编辑功能；

　　（ 4 ）设置一些简单的段落格式：文字左、居中、右对齐等；

　　（ 5 ）设置一些简单的文字属性：改变文字大小、字体、颜色等。

[题目 7.10] （难度等级 C ，人数 1-2 ） 汉诺塔的动态演示。要求能允许用户输入塔盘的数量，支持鼠标和键盘操作，用图象或图形方式演示盘子的移动过程 。

[题目 7.11] （难度等级 C ，人数 1 ）线段 AB 长 100 。 a 点从 A 出发到 B 后返回、到 A 后再反转向 B ，每秒速度为 24 ，循环往复； b 点从 B 端出发，每秒速度为 17 ，运动规律与 a 点类似。编程，显示这两点的运动轨迹。

[题目 7.12] （难度等级 C ，人数 1 ） 设有 n=2k 个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：

　　（ 1 ）每个选手必须与其他 n-1 个选手各赛一次；

　　（ 2 ）每个选手一天只能赛一次；

　　（ 3 ）循环赛一共进行 n-1 天。

　　将结果用表格的形式体现出来。

[题目 7.13] （难度等级 B ，人数 1 ） 用 TC 或 VC 绘制 1 个自行车轮，通过键盘控制可以看到车轮旋转或停止旋转。