课程设计设计题

1、课程设计设计题本手册提供的设计题大致可分为为3类：第一类侧重于算法设计与实现；第二类侧重于文件操作；第三类则属于综合类（侧重于程序结构的设计与实现，当然也包括算法设计与文件操作）。前两类问题可用C+面向过程的方式来实现，而后一类则需用C+面向对象的方式来实现。当然，这种划分不是绝对的，我们期望同学尽可能用面向对象的方式来完成这些题目。（一）算法设计类题目1. Fibonacci数列。Fibonacci数列的计算公式如下： fib（1） = 1；fib（2） = 1；fib（n） = fib（n-1） + fib（n-2）；    /对大于等于3的任意n（1）简单变

2、量“数据平移”方法计算Fibonacci数列的第n项（正整数n通过键盘输入）：说明变量old1=1，old2=1，newItem；新的Fibonacci项newItem总是“距它最近”的前两项（old1与old2）的累加和。而后通过“old1=old2; old2=newItem;”进行所谓的“数据平移”。接着计算另一个新的Fibonacci项newItem，依次循环，直到求出数列的第n项时为止。（2）使用数组求出Fibonacci数列的第n项（正整数n通过键盘输入）并显示在屏幕上：说明数组f用来存放Fibonacci数列的各项之值，且仅初始化前两个元素f0=1，f1=1，而后通过fi=fi-

3、2+fi-1；依次计算出f2到fn-1（注意fn-1恰为所要求出的第n项）并将该值显示在屏幕上。2. 编程序，循环进行如下的处理过程：由计算机生成简单的四则运算题；用户给出答案；计算机判断对错。直到用户回答说不再继续做了时结束程序。提示：可让用户选择指定出加、减、乘、除哪一种运算题，以及出一位数还是两位数的运算题；而后通过使用“rand()%10”或“rand()%100”来获得一个0到9的一位整数随机值或得到0到99的两位整数随机值来为用户出题。还可进一步对用户所做算术题的对错次数进行记录，结束程序时给出一个某种形式的成绩。3. 数的进制转换（1） 将输入的2进制数（一个非“0”即“1”的字

4、符串）化为10进制数。 提示：用字符数组a盛放所输入的二进制数；而后从后往前逐一计算每一位的“位权”w (2的0次方、2的1次方、.)，再计算“位权”乘以“位值”并累加到一个初值为0的变量value上，最后输出该value。（2）如何把8进制数或16进制数化为10进制数。（3）如何把某一个k进制的数化为10进制数呢？4. 编程序，输入正整数m，它代表一个人民币钱数（元数）。求取这样一个方案，使用最少张数的人民币纸币，凑成上述的钱数m，并输出求取结果。注意，现在共有7种元以上面值的人民币纸币，分别为：100，50，20，10，5，2，1。5. 在体育、文艺比赛及选举等打分类项目中，为了

5、公平起见，往往n个评委打出分数后，要去掉一个最高分和一个最低分，然后求取平均得分。当n较大时（本题设为9），则应取掉两个最高分和两个最低分，然后求取平均分。编程实现该算法。6. 用户任意输入一个年份以及该年的1月1日是星期几，而后再输入该年的任意一个月份，由程序负责在屏幕上按照你所设计的格式显示出这一个月的月历。 思考：利用元年元月元日（即1年1月1日）是星期一的已知事实，可对程序进行改造，让用户仅输入任意一个年份和一个月份，则程序就应按格式显示出该年那一个月的月历。7. 有n人围坐成一圈（假设他们的编号沿顺时针方向依次为1到n）。编程序，使用数组来存放各数据（人员编号），而后从1号

6、人员开始数起（沿顺时针方向），当数到k时（其中k>1由用户通过cin输入指定），则该号人员被“淘汰出局”；接着仍沿顺时针方向从被淘汰出局者的下一人员又重新从1开始数起，数到k后，淘汰第2个人；如此继续，直到最后剩下一个人时停止。请输出先后被“淘汰”的人的编号。 8. 编制具有如下原型的函数prime，用来判断整数n是否为素数：bool prime(int n); 而后编制主函数，任意输入一个大于4的偶数d，找出满足d=d1+d2的所有数对，其中要求d1与d2均为素数（通过调用prime来判断素数）。如偶数18可以分解为11+7以及13+5；而偶数80可以分解为：43+37、61+19、6

7、7+13、73+7。提示：i与d-i的和恰为偶数d，而且只有当i与d-i均为奇数时才有可能成为所求的“数对”。9. 编一通用排序程序，程序可以对任意类型的数值常数或字符串构成的行进行排序，通过人机对话选择程序是按数值进行排序还是按字符顺序进行排序。排序是针对数据文件的。例如初识数据为：12，24，9，128，3，76，345按数值大小排序应为：3，9，12，24，76，128，345按字符串大小排序应为：12，128，24，3，345，76，910. 编一程序对至少三个排序方法进行比较，比较方法是生成一组数据(400)，用选定的排序方法进行排序。输出每种方法数据比较或交换的次数。最后输出所花费

8、的时间。注：此题要用到VC+函数库中time()函数time_t time(time_t *timeptr)参数说明：time_t *timeptr 指向存放自格林威治标准时间1970年1月1日00:00:00：至现在经过多少秒数，类型为time_t的指针变量。功能描述：函数读取当前时间，然后计算自格林威治标准时间1970年1月1日00:00:00：至现在经过多少秒数，结果被放在类型为time_t的指针变量所指向的地址变量中。函数返回值：返回自格林威治标准时间1970年1月1日00:00:00：至现在经过多少秒数头文件：time.h11. 编一函数(过程)集, 可分别将整数、实数、布尔值转换成

9、相应的字串，及将以字串表示的整数、实数、布尔值转换成相应类型的值。（整数字串，实数字串均应规定位宽）。12. 输入一批学生某门课程考试的各题的分数，计算每个人的总分,统计各分数段049, 5059, 6069,7079, 8089, 90100的人数及占总人数的百分比。要求输入：课程名称，考试日期，学生班号，学生姓名，学号，课程考试得分。输出要求：课程名称，考试日期，学生班号；各分数段的人数及百分比。 13验证卡布列克运算任意一个四位数，只要它们各个位置上的数字是不全相同的，就有这样的规律：（1）将组成这个四位数的四个数字由大到小排列，形成由这四个数字构成的最大的四位数；（2）将组成这个四位数

10、的四个数字由小到大排列，形成由这四个数字构成的最小的四位数（如果四个数字中含有0，则得到的数不足四位）；（3）求两个数之差，得到一个新的四位数。（4）重复以上过程，最后得到的结果总是6174。14100!的末尾有多少个零由于计算机所能表示的整数范围有限，不可能用求出100!之后再数其尾数有多少个零的方法。必须从数学上分析100!末尾出产生零的条件。不难看出：一个整数若含有一个5的因子则必然会在求100!时产生一个零。因此原问题转换为求1到100这100个整数中包含了多少5的因子。15高次方数的尾数求13的13次方的尾数。乘法的规律：乘积的最后三位的值只与乘数和被乘数的后三位有关，与乘数和被乘数

11、的高位无关。16输出正六边型编写程序输出边长为N的空心正六边型(N由用户输入)，其边由*”组成。思考：输出边长为N的空心正M边型(N，M由用户输入)。17. 输出空心圆编写程序在屏幕上输出一个由”*”围成的空心圆。由于屏幕是25行×80列，故将园心定在屏幕中心40列的位置，将半径定为10行，这样可保证整个图形显示在一屏中。利用圆的方程X2Y2R2（R10）可求出坐标（X，Y），然后用对称性算出右侧对应点的坐标。18横向绘制余弦曲线 在屏幕上用”*”横向显示0360度的cos(x)曲线。此题关键在于余弦曲线在0360度的范围内，一行要显示两个点。考虑到cos的对称性，将屏幕的行方向定义

12、为x，列方向定义为y，则0180度的图形是左右对称的。若将图形的总宽度定义为62列，计算出x行0180度时y点的坐标m，那么在同一行与之对称的180360度的y点的坐标就应为62m。程序中利用反余弦函数acos计算坐标(x，y)的对应关系。19绘制余弦曲线和直线在屏幕上显示0360度的cos(x)曲线与直线f(x)=45*(x-1)+31的迭加图形。其中cos图形”*”表示，f(x)用”+”表示，在两个图形交叉点处则用f(x)图形的符号。图形迭加的关键是要在分别计算出同一行中两个图形的列方向点坐标后，正确判断相互的位置关系。为此，可以先判定图形的交点，再分别控制打印不同的图形。20模拟人工洗牌

13、 编写一个模拟人工洗牌的程序，将洗好的牌分别发给四个人。使用结构card 来描述一张牌，用随机函数来模拟人工洗牌的过程，最后将洗好的52张牌顺序分别发给四个人。对每个人的牌要按桥牌的规则输出。即一个人的牌要先按牌的花色（顺序为梅花、方块、红心和黑桃）进行分类，同一类的牌要再按A、K、Q、J、3、2牌的大小顺序排列。另发牌应按四个人的顺序依次分发。注：C+随机数函数有：void srand(unsigned seed) 功能：函数可以设置rand函数所用得到随机数产生算法的种子值。任何大于1的种子值都会将rand随机数产生函数所产生的虚拟随机数序列重新设置一个起始点。int rand(void)

14、功能：此函数可以产生介于0到32767间的虚拟随机数，所谓虚拟随机数的意思就是因为当只设置相同的启动种子值，所产生的数值序列都是可预测的。要产生不可预测的数值序列，必须通过srand函数不断改变随机数的启始种子值，已产生最佳的随机数。头文件：stdlib.h21. 用户猜测藏物位置：计算机在n行n列（行号为0到n-1，列号为0到n-1）的“棋盘”的某一位置处“藏放一物件”（具体位置通过使用“rand()%10”来随机产生）；用户通过输入行列号来“寻找”该物件；若没猜对时计算机要告诉用户与藏放物件的位置有多远（取整后的近似距离）。思考：若没猜对时也可增加告诉用户藏物的方向信息；另外在猜对结束时，

15、还可告诉用户共猜了几次。22. 编写具有如下函数原型的递归与非递归两种函数f，负责判断数组a的前n个元素是否从大到小完全有序了，是则返回true，否则返回false。并编制主函数对它们进行调用，以验证其正确性。bool f(int a, int n);提示： （1）非递归函数中只需逐对地判断各ai与ai+1是否都已从大到小有序排列（i = 0，1，n-2）。（2）递归函数中将问题分解处理为：若n=1（即只有1个元素时）则返回true而递归出口；n>1时，若最后一对元素不顺序则返回false，否则进行递归调用（传去实参a与 n-1，去判断前n-1个元素的顺序性），并返回递归调用的结果（与前

16、n-1个元素的是否顺序性相同）。23. 编写具有如下函数原型的递归与非递归两种函数equ，负责判断数组a与b的前n个元素值是否按下标对应完全相同，是则返回true，否则返回false。并编制主函数对它们进行调用，以验证其正确性。bool equ(int a, int b, int n);提示：递归函数中可按如下方式来分解并处理问题，先判断最后一个元素是否相同，不同则返false；相同则看n是否等于1，是则返回true，否则进行递归调用（传去实参a、b与 n-1，去判断前n-1个元素的相等性），并返回递归调用的结果（与前n-1个元素的是否相等性相同）。24. 编程序，让计算机来猜测用户“暗记”的

17、某张扑克牌：计算机从一副扑克牌（54张）中任意抽出27张，摆放在不同的三行上（每行9张），用户“暗记”某张纸牌，而后告诉计算机所“暗记”的那张纸牌处于哪一行中；之后计算机再两次将纸牌重新摆放，并让用户再回答两次相同的提问（那张纸牌在重新摆放后又处在哪一行上）；此时计算机会将用户所“暗记”的那张纸牌给挑出来。例如，程序执行后的屏幕显示结果可设计为（其中的前缀a、b、c、d代表四种不同的花色）：-Line 1:   c-9   d-3   a-7   d-9   a-9   c-

18、3   b-8   a-A   d-7Line 2:  b-10   a-Q   d-6   b-4   a-3   b-9   b-K   c-A   d-8Line 3: KING2   d-A   b-A   a-4   a-2   b-7  

19、 d-5   c-7   a-8-Remember a card, and tell me what line it reside in(1/2/3): 3-Line 1:   c-9   d-3   a-7  b-10   a-Q   d-6 KING2   d-A   b-ALine 2:   d-9   a-9   c-3 

20、0; b-4   a-3   b-9   a-4   a-2   b-7Line 3:   b-8   a-A   d-7   b-K   c-A   d-8   d-5   c-7   a-8-What line the card you remembered reside in now (1/2/3) : 1-Li

21、ne 1:   c-9  b-10 KING2   d-9   b-4   a-4   b-8   b-K   d-5Line 2:   d-3   a-Q   d-A   a-9   a-3   a-2   a-A   c-A   c-7Line 3: &#

22、160; a-7   d-6   b-A   c-3   b-9   b-7   d-7   d-8   a-8-What line the card you remembered reside in now (1/2/3) : 1-Your remembered card is : KING2 提示：（1）要从一副54张的扑克牌中任意抽出27张，可通过“rand()%54”所产生的随机值来确定。但注意，一旦随机抽走哪张，下次牌中就没有

23、这张了。（2）程序总按照一种策略将三行纸牌重新“摆放”，而后进一步让用户进行指定。上述所谓的策略指的是，总将纸牌“一分为三”：第一次要将每一行的9张分散到不同的3行上（每行仅“剩”3张），而第二次则要将上次“确定”出的某3张进一步分散到不同的3行上（每行只“剩”1张。此时靠用户再指定一次行号则可唯一确定所“暗记”的那张纸牌）。25. 编写程序求解骑士巡游问题：在n行n列的棋盘上（如n=5），假设一位骑士（按象棋中“马走日”的行走法）从初始坐标位置(x1，y1)出发，要遍访（巡游）棋盘中的每一个位置一次。请编一个程序，为骑士求解巡游“路线图”（或告诉骑士，从某位置出发时，无法遍访整个棋盘 问题无

24、解）。当n=5时，意味着要在5行5列的棋盘的25个“点”处，按骑士行走规则，依次将1至25这25个“棋子”（数码）分别摆放到棋盘上（摆满25个位置则成功，否则失败问题无解）。例如，当n=5且初始坐标位置定为(1，1) 即最左上角的那个点时，如下是一种巡游“路线图”。程序执行后的输出结果为：(x1,y1)? => (1=>5, 1=>5) : 1 1 1   6  15  10  21 14   9  20   5  16 19   2 &

25、#160; 7  22  11 8  13  24  17   4 25  18   3  12  23提示：（1）“棋盘”可用二维数组B表示。（2）编制一个具有如下原型的递归函数solve，用于完成任务：从(i,j)点出发，做第k至第n*n（即n的平方）次的移动 将k直到n的平方这些数码按规则分别摆放到棋盘即数组B中，若成功则通过引用参数ok返回true，否则返回false。void solve(int i, int j, int k, bool& ok)；（3）编

26、制主函数，让用户输入作为巡游起点的初始坐标位置(x1,y1)，在该处摆放“棋子”（数码）1，而后进行调用“solve(x1, y1, 2, ok);”来完成所求任务。欲处理的初始问题为：从某点(x1,y1)出发，按所给行走规则，作24次移动，遍访棋盘中没被访问过的各点（或发现无路可走）。可分解化简为如下两个子问题（正是形成递归函数的基础）： 由点(x1,y1)出发，按所给行走规则作1次移动到达(g,h)（或发现无路可走）； 从(g,h)点出发，按所给行走规则，作23次移动，遍访棋盘中没被访问过的各点（或发现无路可走）。solve函数具体实现时，若由(i,j)点出发已“无路可走”，则将引用参数o

27、k置为false而递归出口；否则，先“迈一步”到达(g,h)点，而后再进行递归调用：solve(g, h, k+1, ok)；以实现从新点(g,h)出发，将k+1直到25这些“棋子”（数码）分别摆放到棋盘上，若成功则通过引用参数ok返回true（否则返回false）。点评：（1）也可编制第二种解法的主函数：将棋盘上的n平方个点依次作为巡游起点的初始坐标位置(x1,y1)，判断从每一位置出发是否有解或无解（输出“OK!”或“NO!”，但并不输出“路线图”）。（2）若更改程序中的n值（如改为4或6等），便可求解其他阶数的巡游“路线图”。（3）可改用非递归方法设计并编写solve函数，那样的话，通常

28、要增加一个记录摆放“棋子”信息的数组，可记录下是沿着什么方向到达了当前的什么位置（在那儿摆放了“棋子”）等，而且对上述数组可按照栈（stack）的方式来使用（栈总是采用FILO即所谓的先进后出使用方式），以便在“无路可走”的情况下，回退（回溯）到上一个位置，接着按照另外的方向去寻找其他的“行走”方法。26. 设计程序在棋盘上放尽可能多的马，以使相互间不能被吃掉。最后给出最大可放置的马的数量及其放置方法。27. 编写程序对八皇后问题进行求解：在8行8列的棋盘上放置8个皇后，使任一个皇后都不能吃掉其他的7个皇后（注：皇后可吃掉与她处于同行或同列或同一对角线上的其他棋子），并将结果以某种方式显示出来

29、。例如，当求出下述的一个解时，可输出如下信息来表示该解（输出了表示摆放皇后的坐标位置以及“棋盘状态” 棋盘中有皇后的位置放一个“Q”字符，其他位置为“+”字符）。(1,1) (5,2) (8,3) (6,4) (3,5) (7,6) (2,7) (4,8)Q + + + + + + + + + + + + Q + + + + Q + + + + + + + + + Q+ Q + + + + + + + + Q + + + + + + + + Q + + + Q + + + + +提示:（1） 通过“int LineNum9; bool a9, b15, c15;”说明具有全局作用域的4个数组。

30、其中的：LineNumi表示第i列的皇后要放的行位置（只用其中的列号1到8）；ai为true（i =1，2，8）表示第i行上尚未放皇后；bi为true（i =0，1，2，14）表示第i条斜对角线上尚未放皇后（斜对角线指的是“/”状对角线，该对角线上各点的行列号之和i+j为一个常数）；ci为true（i=0，1，2，14）表示第i条反斜对角线上尚未放皇后（反斜对角线指的是“”状对角线，该对角线上各点的行列号之差i-j为一个常数）。从而当使用语句“if ( aj && bi+j-2 && ci-j+7 ) LineNumi=j;”时，可用于判断并实现：如果在第j行的

31、第i列上放置皇后安全的话，则将一枚皇后放置到那儿。（2）编制一个具有如下原型的递归函数solve，它负责往第i列开始的连续8-i+1列上均放上皇后，若成功则通过引用参数ok返回true（否则返回false）。void solve(int i, bool& ok);摆放皇后之后，若i=8即已放满时则递归出口；否则通过solve(i+1,ok);进行递归调用。（3）编制主函数，首先初始化一个“空棋盘”，即将a、b、c数组的各元素均置为true（表示当前棋盘的8个行、15条斜对角线以及15条反斜对角线上都尚未摆放皇后）。而后执行调用语句“solve(1, ok);”，它负责往第1列开始的连续

32、8列上均放上皇后，若成功则通过引用参数ok返回true（否则返回false）。点评：（1）可改用非递归方法设计并编写solve函数，那样的话，通常要设置数组来记录皇后的摆放位置信息，还要记录这些皇后所产生的“影响面”（所建立的“势力范围”） 使得哪些行列位置不可再摆放皇后。当在新的行列位置摆放了皇后、但此时又无法进一步摆放其他的皇后时，要回退（回溯）到上一个位置接着去考虑另外的“行走”方法（若还有的话）等等。但注意，“回退”一步后，要同时“撤销”由于该步的回退而关联的那些“影响面”（释放“势力范围”）。（2）本程序只是找到了某一种“摆放方案”而终止，还可进一步考虑寻找其他各种不同的“摆放方案”

33、（实际上共有92种）。（3）也可用同样的方法去处理其他“阶数”的皇后问题，如求解四皇后问题等。28八车问题。设计程序在棋盘上放八个车，以使相互间不能被吃掉。29. 编一迷宫游戏程序，迷宫生成有用户输入和程序自动生成两种方式(迷宫以矩阵表示)，要求输出迷宫和走出迷宫的路径。30. 编一棋盘游戏程序，人为一方，计算机为一方，人下时字符 * 将放在所指定的位置，而计算机下时字符 将放在某一空格位置。行、列、或两对角线有连续三个相同字符一方为胜方，也有平局情况。要求能动态演示。 31. 一个人带有一只羊, 一框菜和一只狼要过河, 但船上除了载一人以外, 最多每次只能再带一样东西。而当人不在场的情况下,

34、 羊和菜在一起, 羊要吃菜, 狼和羊在一起, 狼会吃羊。问怎样安排, 人才可以安全地把三样东西都运过河去。32. Hanoi（汉诺）塔问题。据说这是古代印度布拉玛神庙里的僧侣玩的一种游戏。游戏的装置是一块铜板，上面有3根金刚石的针，在其中一根针上放着从大到小的64个盘子。游戏的目标是把所有盘子从以根针上移到另一根针上，还有一根针作为中间过渡。游戏规定每次只能移动一个盘子，并且大盘子不能压在小盘子上面。由于需要移动的次数太多，该游戏的结束标志着世界的末日。要求用动画形式演示盘移动结果。33. 魔方阵。把整数1到n2排成一个n×n方阵, 使方阵中的每一行, 每一列以及对角线上的数之和都相

35、同。如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列的那个格子中。编一程序实现上述算法，并模拟显示其过程。34. 一个有机体生命游戏在一个矩阵上进行,

36、每一个矩阵方格可以包含一个有机体, 不在边上的方格有8个相邻的方格, 用occ(k)表示与方格k相邻的有机体个数, 应用简单的规则从前一代有机体配置产生下一代有机体的配置：(1) 如果2occ(k)3, 那么方格中的有机体活倒下一代, 否则或孤独而死亡, 或因拥挤而死亡；(2) 如果occ(k)=3, 那么在一个空方格k中诞生出一个新有机体。编一程序实现上述算法，并模拟显示其过程。35. 23根火柴游戏: 两个游戏者开始拥有23根火柴(或小棒)。每个游戏者轮流移走根、根或根火柴，拿到最后一根火柴的就算输了。编一程序与计算机玩这个游戏。36. 设计一种结构能表示最多有1000位（或其它指定位数）

37、的大整数（正、负整数均可）,并实现这类数的加、减、乘、除法运算。37搬山游戏 设有n座山，计算机与人作为比赛的双方，双方轮流搬山。规定每次搬山的数目不能超过k座，谁搬最后一座谁输。游戏开始时，计算机请人输入山的总数(n)和每次允许搬山的最大数目(k)。然后请人先开始，人输入了需要搬走的山的数目后，计算机马上输出它搬多少座山，并提示尚余多少座山。双方轮流搬山直到最后一座山搬完为止。计算机显示谁是赢家，并问人是否要继续比赛。若人不想玩了，可以输入山的总数为0，计算机便会告诉人共完了几局，双方胜负如何。解决这类问题的基本方法是先进行分析，找出游戏对弈的规律性，然后让计算机按照游戏的规则，模拟人进行游

38、戏。这类程序中计算机游戏水平的高低，实际上取决于程序设计者对游戏规律的认识。首先设计计算机参加游戏的算法，计算机每次搬山时应遵循如下原则：(1) 当：剩余山的数目1<=可移动的最大数k时，计算机要移(剩余山的数目1)座，以便将最后一座山留给人。(2) 对于任意正整数x, y，一定有：0<=x%(y+1)<=y因此，对于我们的问题来说，在有n座山的情况下，计算机为了将最后一座山留给人，而且又要控制每次搬山的数目不超过最大数k，它应搬山的数目要满足下列关系： 搬山数量（当前所剩的山数1）（k+1）如果算出结果为0，即整除无余数，则规定只搬一座山，以防止冒进后发生问题。38调车头下

39、面铁路线A段中，有n个车头，按图中所示的顺序编号为1，2，.，n。每个车头都可以在铁路上独立行驶，但约定，当B段或C段已有车头时，新进入这二段的车头号必须比该段中已有的车头号小。设计一个程序，调用递归过程，将A段中车头的顺序颠倒过来。B段C段A段2.1nn-139地图着色地图上有不同国家（不同区域），每个国家都与其他一些国家邻接。现要求对地图着色，使所有的国家与它的邻接的国家有不同的颜色。通常由四种颜色就已足够。提示：可采取试探的方法逐步逼近最后解，即按某种模式生成一个部分解，检查它是否合格。如为合格，在扩展这个部分解向最后解逼近，否则为不合格，不管如何扩展这个部分解都不会得到最后解。这时必须

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

41、5，它不能是已着好的蓝色，也不能着蓝色的下一种颜色绿色，因为这会使它与区域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=

42、n) prtmap; /输出结果 else colorarea(j+1); /进一步着色下一个区域 区域j退去c色 40. 安排研究生课程表。设有m个研究生和可选修的n门课程，如果某个研究生选修的两门课程安排在同一时间内上课，则这两门课程就会发生冲突，要求不冲突地安排课程表。提示：研究生选课信息可存放在m×n矩阵a中，ai,j=1表示研究生i选修了课程j，ai,j=0表示研究生i未选修了课程j。（二）文件类题目1. 统计一源程序语句数、行数、字符数、类及函数的个数。2. 将源程序每行前加上行号并删除其所有注释后生成一打印文件。注意C+语言程序注释形式有：/注释内容 和 /* 注释内容

43、 */ 两种形式。3. 编一查找给定字符串程序，要求输出给定字符串在文件中的出现的行数，第一个字符在此行中的位置。应区分给定字符串本身构成一个字和作为另外一个字的子串两种情况。4. 设计一文件阅读器, 可以一次一屏(20或22行)显示文件内容, 每次显示完一屏内容后, 提示使用者键入一控制字符以控制屏幕翻滚。如字符'n'显示下一屏, 字符'p'返回上一屏, 字符'q'结束阅读。5. 编一程序显示指定文件的第 n 行, 并可对此行执行拷贝、修改、删除、在此行后增加一行等功能。6编程序CompFile，首先让用户输入两个文件名及其路径（二文件均为te

44、xt文件），而后通过使用类成员函数getline逐行读入这两个指定文件的内容并进行比较。若发现有不同，则在屏幕上显示出相异二行的行号及其内容，并暂停下来询问用户是否需要继续比较后继行，直到用户回答不需要继续进行比较，或者已经比到了二文件的结束时停止处理。思考：也可改写程序，将“让用户输入两个文件名及其路径”改为从命令行参数处获取这两个文件名及其路径。7. 编程序，从键盘输入某个C+源程序文件名，而后通过getline依次读入该文件中的各行（假设每行都不超过100个字符），并统计显示出该源程序文件中出现了哪些你所关心的C+关键字，以及各关键字出现的次数（所关心的那一批关键字由程序进行指定）。提示

45、：可将m个所关心的关键字存放在一个二维字符数组A之中，而后从各读入行中“分解”出每一个“字”，并依次与A中的各关键字进行比较。若二维字符数组A中的关键字是按“从小到大”的顺序存放的话，则还可以使用折半查找方法在A中进行“查找”以提高速度。8. 设计一个程序，该程序输入一个英语单词和它的释义（应考虑一个单词可以有多个释义）。将单词和它的释义分别存放在文件word.dat和meaning.dat中。文件word.dat中存储的数据的结构为：class index public: char word20; streampos offset;其中，数据成员offset用于记录单词word的释义在文件m

46、eaning.dat中的位置。用户输入一个单词，屏幕输出该单词的释义。9. 编写程序，从键盘读入一个文本文件名字（可带路径），为该文件中的所有单词建立一个词汇索引。按字母顺序显示所有单词（仅一次），后面紧跟着它们所在的行号。大写与小写字母被认为是相同的。例如，对于下列的输入文件：To be ornot to be,that is the question.产生的词汇索引如下：be 1 2is 3not 2or 1question 3that 3the 3to 1 210. 编写程序，检查所给的两个文本文件是否包含相同的单词（不分大小写），不管它们的顺序和出现次数。假设这两个文件是A和B，如果出

47、现在A中的单词也出现在B中，则输出这个单词，以及它在文件A和文件B中第一次出现的行好。思考：两个文本文件是否包含完全相同的单词（不分大小写），不管它们的顺序和出现次数。假设这两个文件是A和B，如果出现在A中的每一个单词也出现在B中，并且出现在B中的每一个单词也出现在A中，则这两个文件就包含完全相同的单词。11. 编写程序，读取任何文本文件，查看圆括号和大括号是否匹配，即只允许成对出现，并按正常的方式排列。例如，下面是正确的例子：（()()()）注意，两个大括号之间的圆括号（）是按适当的方式成对出现的。不正确的例子有：()(（三）综合类题目1. 有理数运算问题描述有理数是一个可以化为一个分数的数

48、，例如2/3，533/920，-12/49都是有理数，而就为无理数。在C+中，并没有预先定义有理数，需要时可以定义一个有理数类，将有理数的分子和分母分别存放在两个整型变量中。对有理数的各种操作都可以用重载运算符来实现。基本要求定义并实现一个有理数类，通过重载运算符+、-、*、/对有理数进行算术运算，通过重载运算符=实现判定两个有理数是否相等。写一个优化函数，它的作用是使有理数约去公分母，也即是使保存的有理数分子和分母之间没有公约数（除去1以外）。此外，还要定义一个将有理数转换为实数的函数，再加上构造函数和有理数输出函数。测试数据在应用程序中，创建若干有理数对象，通过带参数的构造函数使得各有理数

49、对象值各不相同，然后分别进行各类运算，输出运算结果，检验其正确性。实现提示设有两个有理数a/b和c/d，则有：（1） 有理数相加 分子=a*d+b*c；分母=b*d（2） 有理数相减 分子=a*d-b*c；分母=b*d（3） 有理数相乘 分子=a*c； 分母=b*d（4） 有理数相除 分子=a*d； 分母=b*c优化函数在创建有理数对象时应执行，在执行其它各种运算之后也需执行它，这样可保证所存储的有理数随时都是最优的。对于判断两个有理数是否相等，由于在对有理数进行各种运算后都对其进行优化，所以判定两个有理数是否相等只需判定它们两个的分子和分母分别相等即可。选做内容重载插入（<<）和

50、提取（>>）运算符，使得对有理数可以直接输入输出。设有理数输入格式为：整数1 整数2 /整数1为分子，整数2为分母有理数输出格式为：分子/分母2. 通讯录管理 问题描述编写一个简单的通讯录管理程序。通讯录记录有姓名，地址(省、市(县)、街道)，电话号码，邮政编码等四项。基本要求程序应提供的基本基本管理功能有：1） 添加：即增加一个人的记录到通信录中2） 显示：即在屏幕上显示所有通信录中的人员信息，应能分屏显示。3） 存储：即将通讯录信息保存在一个文件中。4） 装入：即将文件中的信息读入程序。5） 查询：可根据姓名查找某人的相关信息，若找到显示其姓名、地址、电话号码和邮政编码。6）

51、修改：可修改一个人的除姓名外其它信息。测试数据程序应输入不少于10个人员的通讯录信息，应考虑到人员可以同名的情况。实现提示程序可用一个单向链表来管理人员信息，每个人员的姓名，地址，电话号码和邮政编码用一个类Cperson来实现，作为链表的值指针指向这些Cperson类对象，通过链表的遍历可以操作这些数据。选做内容为了加快数据定位查找的速度，采用常用优先的方法对链表的各个节点进行排序，即一旦操作了一个人员的数据，他的数据就将被调用到链表的链首。这样经过有限次操作，经常查阅的人员的信息就将排在链表的前端。虽然不能说链首的节点一定是最常用的，但常用的节点一定会排在较靠前的部分，链表查找时所要走的平均

52、距离一定较短。3. 商品销售统计问题描述编写商品销售统计程序，商品的信息有：商品的名称，计量单位（重量或件），单价。所有商品的信息事先已存入计算机，屏幕上显示所有商品的名称，选择商品名，输入商品计量单位(如重量，件数等)，根据单价算出总价。客户一次购物可能购买多种商品，程序应计算出客户应付的钱款数。基本要求程序分为两个部分：第一部分用于输入商品的信息并允许修改和删除；第二部分实现销售统计。程序运行时由用户选择进入哪一部分功能，并能在运行时在两部分之间切换。第二部分运行时，首先显示所有商品名称及代码（商品数目较多时，应考虑分屏显示），用户输入商品代码及商品重量或件数，用户一次操作可输入若干商品的

53、购买信息，然后输入一个特殊的代码（如-1）表示本次购物结束。此时。程序计算出应付钱款数并显示。测试数据程序应输入不少于10种商品的信息，并进行模拟运行。实现提示本程序的商品信息管理可采用与课程设计题目二类似的数据结构，既定义一个商品类，每种商品作为商品类的实例（对象）存储在链表节点中。选做内容程序在营业结束时统计每种商品的销售量，销售金额及总营业额。因此第二部分应有营业结束的选择，当用户选择此项时屏幕上显示当天营业的每种商品的销售量，销售金额及总营业额。注意，商品类的数据成员应增加有商品的销售量和销售金额。总营业额是所有商品的营业额之和，可用静态数据成员实现。或可由原商品类派生出一个特殊的类，

54、增加上面的数据成员及相应的成员函数。4. 研究生初试录取问题描述研究生考试课程为4门，其中数学、外语、政治为统一命题，而专业基础课则根据不同的专业由招生学校自行命题。国家对初试录取分数有总分要求（如某一年要求4门课总分应达到310分），另外还有对每门课的最低分数要求（如总分为100的试卷最低应达到40分，总分为150的试卷最低应达到65分）。编程统计初试合格的人数，并按总分由高到低的顺序输出合格考生的信息。基本要求程序运行时首先要求输入：考生姓名，准考证号，报考专业，是否应届生，4门课程（政治、数学、外语、专业基础课）成绩。这些原始数据应保存到一个文件中。然后输入：录取的总分要求，各课程的最低

55、分数要求。输出要求：过线考生的姓名，准考证号，报考专业，是否应届生，4门课程（政治、数学、外语、专业基础课）成绩及总分，这些信息应存放到另一个文件中。测试数据程序应输入不少于10名考生的信息，其中应届生和历届生分别有若干名，并且都有合格和不合格的情况。实现提示可定义一个考生类存放有关信息和实现相应的操作。分数线数据（总分要求和各门课程的要求）可定义另外的类来存放，但应能被考生类及其派生类直接访问。选做内容初试合格的考生应经过复试才能决定是否录取，复试成绩合格（大于一给定分值）可以录取，否则被淘汰。而录取的顺序假设是按照专业基础课和复试成绩的平均值来确定的（因为这涉及到是计划内还是委培问题）。因

56、此，应首先输入初试合格考生的复试成绩及复试的合格线分数，然后按上面要求排序输出并标明被淘汰的学生。5. 足球联赛积分问题描述足球联赛采用主客场双循环赛制，胜一场得3分，平局各得1分，负一场得0分，联赛排名以积分多者在前，当两队（或多队）积分相同时，则净胜球（即进球数与失球数之差）多者在前，若净胜球相同，则进球数多者在前，若仍相同，则抽签或踢附加赛决定名次（这在联赛结束后进行，联赛未结束则两队名次并列，本程序不做这方面要求）。试编一程序统计最近一轮比赛后，各队积分及排名。基本要求设积分表结构如下：队名（不超过15个字符），已比赛的场数，赢的场数，平的场数，负的场数，进球数，失球数，积分。积分表放

57、在正文文件中。最近一轮的结果从键盘输入，其形式为：主队名（可用代码），客队名（可用代码），主队得分（即进球数），客队得分（即进球数）。程序应根据此轮结果修改各队的积分和名次，所得的最新记分表仍在原积分文件中并同时在屏幕上显示。测试数据可选择我国当年的甲A或甲B联赛的数据输入，并检查与报章公布的数据是否一致。实现提示定义一个球队类，每个球队是均是此类的对象。由于联赛中参赛的队伍数是固定的，因此可用对象数组来实现（当然也可以用链表结构）。每输入两个队的比赛成绩，则相应的队的有关数据（比赛场数，赢的场数，平的场数，负的场数，进球数，失球数，积分等）即可进行修改，比赛成绩录入完成，调用联赛排序方法（对象数组作为参数）排出名次并输出。选做内容篮球联赛（如NBA）往往采用胜率来决定名次，胜率就是取胜的场数比赛场数之比。若胜率相同，再由净胜球及进球数来决定名次，通过继承性完成上述要求。6. 银行账户管理程序问题描述设计一个银行账户管理程序，账户的信息有账号（唯一）、姓名、余额、身份证号码、单位、电话号码、地址等，允许用户进行如下操作：开户、销户、存款、取款、转账、查询，一个用户可以有多个户头，账户的数值没有上限。基本要求 程序运行时，可以由用户选择进行何种操作，开户操作要求输入用户信息后自动获取账号，