2012C语言程序课程设计备选题目

1、说明：1题目来源是：(1)较重要C语言程序设计教科书中的例题或习题；(2)与计算 机学科相关的后续课程，如数据结构、离散数学、组合数学、计算方法等课程教 科书中的例题或习题中，不需要相关后续课程的专门知识就可以很好解答的题 目；其它有影响计算机程序设计类书籍或文章中的例题；(3)各级各类计算机程 序设计竞赛(例如 ACM 大赛)、程序员考试、求职面试的训练题和考试题等。 欢迎老师和同学们提供更好的题目。题目内容涉及的知识点不超过大学一年级的知识水平，主要目标是训练学生将 实际问题转化为计算机可以处理的形式并编写程序给出解答的能力。去掉了较复 杂事务管理如图书管理、学生成绩管理之类的题目，这类事

2、务管理方面题目希望 在后续课程如C+面向对象程序设计、数据库应用及各专业的课程设计中进行。题目有多种完全不同的解答，给出的提示主要供指导教师参考。题目 1：文件存取练习：要求实现如下功能：(1)定义函数 Rand1000(), 随机生成 1000 个均不相同的正整数，并写入到文本 文件“file1.dat”中，各数之间用空格来分隔。(2)编写一个函数input (int a,int n),将上述数据读入到数组a中。(3)编写一个函数digitcount(int a,int n,int b10), 统计数组 a 的每个元素保存的整数中，每位数字出现的次数，并分别保存在 b0 到b9中。(4)编写

3、函数maxprime(int *p,int n),找出其中最大的素数，如果不存 在素数函数结果为 0。(5) 对于这些整数排序之后，分别输出相邻两数之差最 大和之差最小的两个数，如果有多组满足条件要输出所有的。 (6)定义函数 myinput(int a,int n)，用fgetc函数从文件“file1.dat”上逐个读入字符，并将其 转换成独立的正整数,并依次存入数组 a 中。提示：可查阅任何一本C语言程序设计教科书中关于文件部分，例如谭浩强，C 程序设计(第三版)，第13章。还需要熟悉随机数生成函数rand()，需要编写 判断一个奇整数是否素数的程序等。部分可供参考程序如下：题目 2：两个

4、文件同时对照显示：程序从两个文件中读出文本行，并列显示在屏 幕上。假定屏幕有 80 列， 25 行，则第 034 列显示第一个文件的内容，第 4074 列显示第二个，第 77-78 行显示文本总的行序号。每屏显示 20 行，超过20 行就 显示在下一屏。程序应该能够以这种方式显示任意的两个文本文件，例如两个 C 程序源代码文件，两篇内容类似的文章形成的两个文本文件等。 提示：先把两个文本文件读入，存入数组，再考虑显示的安排。题目 3：实现一个 C 语言程序设计自助学习系统,要求实现的基本功能如下：1、测验可以按固定的试题数目，从题库中随机选取题目进行测试，如每次测 试 5 道题或 10 道题。

5、( 2)每次只显示一道题，包括问题描述、备选答案；(3)根据学生答题结果，对比试题答案，显示答题对错的信息；（4）答题全部结束后给出本次测试的成绩，按百分制评分。2、学习管理（1）通过题目浏览，自我测验，查看题解的过程来帮助学生学习。（2）需要为学生提供多种学习方式，至少应包括顺序选题学习和随机选题 学习等方式。（3）如果是采用顺序选题方式学习，需要做到可以从中间某个位置开始学 习，不是每次一定从第一题开始学习。3、题库管理（1）试题库中保存全部试题及其相关信息。（2）将要入库的试题，按固定格式编辑整理好保存在 ASCII 文件中，通过 计算机程序读取该文件，并将文件中的全部试题添加到已有的试

6、题库中。（3）今后需要对于所有试题分类进行管理，在库结构设计时，要考虑这些 扩展功能的数据接口要求。（4）试题库初始化，将试题库内容全部清空，便于重新建立系统。提示：可以参考：余江，肖淑芬主编，C语言程序设计，天津科学技术出版社， 2001 年 5 月， 273-313 页。题目 4：实现题目 3 中 C 语言程序设计自助学习系统得升级版，可考虑实现功能：一、测验1、系统自动组卷（1）试卷结构说明：以题库提供的试题类别和各类试题的数量为依据来实现。 系统组卷前需要获得的信息是对于每类试题要含有类别名称、试题数、分数，所 有类别的分数累加在一起要恰好是 100 分。（2）试卷保存：将上述组卷结果

7、保存在二进制文件中，文件名由用户输入。（3）个性化组卷：输入学号后，系统根据试卷结构说明的规定自动组卷，做到 每个学生试卷不同。2、错题本功能（1）答错的题目自动加入到错题本中；（2）可以对错题本中的题目逐题测验，不分题目类别；（3）可以制定分类测试。3、多科目测试二、学习管理1、分类别学习2、错题本内容学习3、多科目学习，选择科目后可以进行指定类别的分类别学习和错题本内容学习。三、题库管理1、入库试题文件格式正确性检查。包括：试题的描述的合法性检查，类别信息 合法性检查，给出出错位置的信息。2、对于分类试题存储方式的优化，例如：同类试题连续存储的实现；3、目前完成的是单科目多类别的题库管理，

8、要实现多科目多类别的题库管理。四、用户管理1、系统注册2、登录3、错题本等个性化信息管理4、屏幕背景颜色和字符颜色的设置5、学习位置的记载，要按科目记载，每个科目要按类别记载。 提示：鼓励使用更多方法实现，例如使用数据库系统，VC+等。题目5：给出一个正整数n 个存放1到n共n个正整数的数字金字塔构造如 下：（1）1 在最上方第 0 层；（2）如果 x 大于 y 并且 x 除以 y 的余数为 0（即 xy & x%y = = 0 ）， x 要放在 y 下方一层（即若 y 在第 i 层， x 应在 i+1 层）；（3） 每个数应尽可能放在更下方，即如果可以放在第 i 层，就不能放在 i-1 层；

9、（4） 相同层上的数从左向右从小到大排列。其实第 i 层是有 i 个素数因子的数的从小 到大的排列。例如对n=6，符合这组规则的数字金字塔如下：123546每个数按照它在塔中的位置从上到下从左到右从 1 开始编号，例如 5，编号应该 是 4。要求你编写程序，输入一个正整数 n， 5n3-6, 5, c=2,表示移动是1到3，3到6,因 为 1+3=4, 3+6=9,而 4 和 9 是完全平方数，符合条件的移动只有这两次。移动结 果是还有2根柱子上有圆盘，即c=2,有圆盘的一根柱子上圆盘3个，有数1-3-6, 有圆盘另一根柱子上圆盘一个，有数 5，它其实没有发生移动。程序编写完成后， 要求给出你

10、的程序对下列两组输入的结果：（1）9，1，2，3，4，5，6，7，8，9（2）10，1，3，5，7，9，11，13，15，17，19 （本题为 2010年 ACM 大赛题目。）提示：输入：9，1，2，3，4，5，6，7，8，9 输出：1-3-6, 2-7-9,4-5,8,c=4 输入：10，1，3，5，7，9，11，13，15，17,19 输出：1-3-13, 5-11,7-9,15,17-19,c=5题目 7：我们知道，在 10 进制数中有判断整除性的二个简单规则：一个正整数 能够被3 整除，当且仅当，它的各位数字之和能够被 3整除；一个正整数能够被 11整除，当且仅当，它的奇数位数字之和与

11、偶数位数字之和的差能够被 11整除； 现在要问：对于b进制数，具有类似于10进制数的3和11的这种整除性判断的 数是什么？具体地，请编写程序，输入进制的基数b，输出最小的可以如上判断 整除性的数x和y。为确定，输入输出均采用10进制数。例如输入b为10,则 自然要输出x为3, y为11；若输入b为8,则要输出x为7, y为3 （例如8进 制数25，按上述规则判断应能够被7和 3 整除，事实上， 8 进制数25是 10进制 数21,能够被7和3整除是显然的）；若输入b为120，贝U要输出x为7, y为 11 （请自己验证这是对的）。（本题为2011年ACM大赛题目。）提示：对于10进制数，10-

12、1=9=3*3, 10+1=11, 10进制数n可以一般地表示为： n = a 10k + a 10k-1 + + a 10 + ak k-1 1 0保持n不改变数值将10换为10 - 1和10+1，可以看出3和11可以如上判断整 除性的理由。对于b进制数，n = akbk + ak-1bk-1 + + a1b + a0可以想到只需考虑b - 1和b+1的最小因子。题目 8：如果语文数学两门课程的成绩，甲同学分别是80分和 90分，乙同学是 90分和 80分，丙同学是70和 60分，这时比较甲同学和乙同学的成绩，只能说 语文较差，数学较好，综合到一起就属于无法比较，但对丙同学可以比较，可以 说

13、甲和乙同学的成绩都比丙同学好。一般情况，设有一个三元向量的集合，若其 中有向量 p=（pp2, p3）, Q=（qq2, q3），规定 p = Q 当且仅当 p1 =p2=q2,p3wq3。其中一个向量称为是一个极小元素，当且仅当它只三它自己。例如如 下三个三元向量组成了向量组（ 80， 90， 100），（ 90， 80， 70），（ 60， 70， 60）， 其中只有一个最小元素，是（60, 70, 60）。请编写程序，输入n个三元向量， 输出其中最小元素的数目。（本题为2011年ACM大赛题目。） 提示：先对第一个坐标排序，再考虑第二个坐标，第三个坐标。题目9：在某城市有n座摩天大楼，问

14、那二座之间的距离最小？设可以输入所有 大楼的位置坐标，请编写程序输出距离最近的二座大楼及它们之间的距离。两点（X, y）和（x2, y2）之间的距离d按照两种不同方式规定：（1） Euclid距离 d = *；（x -x ）2 + （y 一 y ）2（2） Manhattan 距离 d = I x1 -x2 | + | y1 -y2 I。显然的解法是计算所有点对之间的距离再找出最小值，但本题只要求输出距离最近的二 点及之间距离，所以应该给出不计算所有点对之间距离的更有效率的解法（本题 为 2011 年 ACM 大赛题目)。(可查阅： 沙特 M.H.Alsuwaiyel 著，吴伟昶等译， 算法设

15、计技巧与分析，电子工业出版社，2004 年 8 月，第 121-124 页。或者： 美Michael T.Goodrich等著，霍红卫译，算法分析与设计，人民邮电出版社，2006 年 10 月，第 385-387 页。)提示：找到两点距离 d 后，接下去可检查宽不超过 d 的长条。题目 10：一条贪吃的蛇在一个 n*m 的网格中游走，它只能从一个方格走向另一 个相邻的方格，这里相邻的意思是两个方格有公共边。每个方格可以看作是一个 房间，其中一些是空的，一些存放有苹果。贪吃的蛇根本不进入空的房间，而进 入有苹果的房间后就可以带走所有苹果使房间成为空的。蛇从一个指定的房间出 发，最终回到它的家，把

16、一路带来的苹果存储到家中，当然，它希望带来的苹果 最多。请编写程序，输入有整数n和m,及n*m的一个矩阵，矩阵元素数值中 有一个是 -1，表示蛇的出发位置，有一个是 -2，表示蛇的家的位置，其余数值 是非负整数， 0 表示房间为空，非零整数表示苹果的数目。输出蛇选择的游走路 径和获得的最多的苹果数目。例如输入 4*4 矩阵：7 0 4 18401115 7 11 -10 12 -2 0则应输出 (2, 3), (1, 3), (0, 3), (0, 2), (1, 2), (2, 2), (2, 1), (3, 1), (3, 2), 带回苹果数 为 1+18+4+1+11+7+12 = 54

17、 。(本题为 2011 年 ACM 大赛题目)。(可查阅：吕国 英，任瑞征等编著，算法设计与分析(第 2 版)，清华大学出版社， 2009 年 1 月， 第 200-202 页。提示：这是一个利用回溯算法的迷宫搜索类型问题，可参考类似问题的已有解法。题目 11：化学家研究原子团的行为时，认为每个原子具有整数能量，这个整数 可以是正数、零和负数，绝对值不超过 100。可以认为原子排列成为一行，一行 中任意多个连续的原子可以形成原子团，原子团的能量是其中各原子能量的代数 和。问题是怎样编写程序，求出具有最大能量的原子团和能量数值。要求程序输 入一列原子的能量数值，以-1 结束，输出找到的能量最大的

18、原子团及能量数值。 例如输入 8， 0， 6， 4， -2， -1，应输出原子团 8， 0， 6， 4，及能量数值 18。(本 题为 2010 年 ACM 大赛题目)(可查阅：吕国英，任瑞征等编著，算法设计与分 析，清华大学出版社， 2009 年 1 月，第 265-270 页)。提示：这是最大子段和问题。题目 12：一刀可以把蛋糕分为两个部分，现在给出要分为两部分的面积的比值， 希望求出切口的弦的长度。这里当然要假定蛋糕是一个圆，并设其半径为1。例 如，输入两部分比值为 1：1，切口是直径，长为 2；输入 1：2，应输出 1.9285； 输入 10：1，应输出 1.4145。（本题为 201

19、0 年 ACM 大赛题目）提示：计算半弦长，可以利用公式a2=2rh-h2 ,计算弓形面积，用公式 s=0.5*xita*r*r-a*sqrt（r*r-a*a）; 其中 h 是弓形的高， r 是半径， xita 是圆心角。一 个思路是用二分搜索法寻找合适的h,使用该h求得的面积比值符合题目要求。题目 13：年历显示，要求至少具有如下功能：（1）输入一个年份，输出是在屏幕上显示该年的日历。假定输入的年份在 1940-2040 年之间。（2）输入年月，输出该月的日历。（3）输入年月日，输出距今天还有多少天，星期几，是否是公历节日。（4）某人自 1990 年 1 月 1 日开始，“三天打鱼两天晒网”

20、，输入一个 1990 年以 后的日期，输出他这一天是打鱼还是晒网。（可查阅：杨克昌编著，计算机程序设计典型例题精解，国防科技大学大学出版 社， 1999 年 3 月，第 154-156 页）提示：应理解（1）能被 4 整除不能被 100 整除的年份是閏年；（2）能被 100 整 除又能被 400 整除的年份也是閏年。可以查一下今年的日历看今年 1 月 1 日是星 期几，用这些数据就可以编写程序。题目 14 小学生测验，面向小学12 年级学生，随机选择两个整数和加减法形成 算式要求学生解答。要求至少具有如下功能：（1）电脑随机出 10 道题，每题 10 分，程序结束时显示学生得分；（2）确保算式

21、没有超出 12 年级的水平，只允许进行 50 以内的加减法，不允许 两数之和或之差超出 050 的范围，负数更是不允许的；（3）每道题学生有三次机会输入答案，当学生输入错误答案时，提醒学生重新 输入，如果三次机会结束则输出正确答案；（4）对于每道题，学生第一次输入正确答案得 10 分，第二次输入正确答案得 7 分，第三次输入正确答案得 5 分，否则不得分；（5）总成绩 90 以上显示“SMART”，80-90 显示“GOOD”，70-80 显示“OK”， 60-70 显示“PASS”，60 以下“TRY AGAIN”。 提示：可以利用随机数生成函数 rand（）。题目 15：“上海自来水来自海

22、上，黄山落叶松叶落山黄”，“客上天然居，居然天 上客”，“人过大佛寺，寺佛大过人”，都是著名的“回文”的例子。回文就是正 读和反读都相同的字符串。请编写程序判断输入的字符串是否回文，要求：（1） 用循环和递归各编写一个程序；（2）如果不是回文，就从两端向中间检查，发现 不同后，在后端加入一个与前端相同的字符，使得到一个回文字符串。（3）类似， 正读和反读都相同的数字就是回文数，例如， 23532 就是一个回文数。请编写程 序，输入两个正整数n1和n2，n1 T,如果T是S的前缀，或者存 在 整 数 i ， 使 对 于 j Ti 。 例 如 字 符 串 abed abe abbd 。请编写程序，

23、输入一个任意的字符串，输出它的按照 字典序最大的子串。这里对子串的理解见题目 13，例如输入字符串 debadebbd, 应 输出dcbbd；输入abbasd,应输出sd。（本题为2011年ACM大赛题目。） 提示：本题属于比较容易，直接解法是检查所有子串，但显然可以优先考虑较大 字符引起的字符串。题目 18：某期刊的编辑使用文本文件审阅和修改论文草稿，草稿文本正文后要 列出参考文献，很多草稿对参考文献的使用不符合出版要求，你的任务是编写程 序，输入不一定符合出版要求的草稿文本，输出修改后至少在列出的参考文献方 面符合出版要求的文本。具体要求是：（1）参考文献要按照在论文中首次被引用 的次序从

24、 1 开始连续编号；（2）所有参考文献按照新编号次序依次放在论文末尾；（3）不改变论文的段落顺序，不改变论文其它内容。例如，输入数据：28 Auther1, Auther2, Paper name one , Magazine1, August 1983.You and me, 15 and 28; Me and you,28 and 15.15 Auther1, Auther2, Auther3, Paper name two ,Magazine1, August 1983.这时应该得到的输出数据是：You and me, 1 and 2; Me and you,2 and 1.1 Auth

25、er1, Auther2, Paper name one , Magazine1, August 1983.2 Auther1, Auther2, Auther3, Paper name two ,Magazine1, August 1983.（可查阅文献：董东，周丙寅编著，计算机算法与程序设计实践，北京：清华大 学出版社，2010 年 5 月，93-97 页）提示：此题属于练习字符串操作，应设草稿存于文本文件，首先读入并存储，再 考虑进行转换。要将论文正文出现的参考文献编号按照出现顺序重新编号，记录 新旧编号间对应关系。输出时，先输出正文段落，再输出新编号序号和按照对应 旧编号的参考文献段落

26、。题目 19：排班系统：学校实验楼有 7 名保安人员：钱、赵、孙、李、周、吴、 陈。由于工作需要进行轮休制度，一星期中每人休息一天。预先让每一个人选择 自己认为合适的休息日。请编制程序，打印轮休的所有可能方案。当然使每个人 都满意，例如每人选择的休息日如下：钱：星期一、星期六赵：星期二、星期四孙：星期三、星期日李：星期五周：星期一、星期四、星期六吴：星期二、星期五陈：星期三、星期六、星期日运行结果:Solution: 1赵钱孙李周吴陈 星期四 星期一 星期三 星期五 星期六 星期二 星期日Solution: 2赵钱孙李周吴陈 星期四 星期一 星期日 星期五 星期六 星期二 星期三Solutio

27、n: 3赵钱孙李周吴陈 星期四 星期六 星期三 星期五 星期一 星期二 星期日Solution: 4赵钱孙李周吴陈 星期四 星期六 星期日 星期五 星期一 星期二 星期三题目20：用英文单词模拟数学计算：读入两个小于100的正整数A和B,计算 A+B。需要注意的是：A和B的每一位数字由对应的英文单词给出。具体的输入输出格式规定如下：输入格式：测试输 入 包含若 干 测试用 例 ，每个测 试用例 占一行，格 式为 A + B = ，相邻两字符串有一个空格间隔。当 A 和 B 同时为 zero 时输入 结束，相应的结果不要输出。输出格式：对每个测试用例输出 1 行，即 A+B 的值。 输入样例：

28、one + two = three four + five six = zero seven + eight nine = zero + zero =输出样例：three nine zero nine six题目 21：C 语言关键字中英翻译机。要求输入中文的名词和关键字，可以将其翻译成英语，如输入“基本整型” +回车，得到int；输入英文的单词int,则可以翻译成中文“基本整型”可多次 查询，输入 bye 时退出。提示：可模拟文曲星来实现。题目22： 2003年突发的非典型肺炎（SARS）是一种病源还不完全了解的新型传 染病，需要隔离所有疑似病例。在 N 大学，有许多学生团体，一个学生可以加

29、 入多个团体，同一个学生团体内部成员被认为是经常接触的。 N 大学为了应付 SARS，规定若一个学生被认为是疑似病例，则他所在团体的所有学生都被认为 是疑似病例。现在需要你编写一个程序，在发现一个学生是疑似病例后，找到所 有与之直接或间接接触过的疑似病例。可以设每一名学生用数字 0 到 n-1 编号， 输入有学生总数n,学生团体数k每个学生团体的人数和成员的编号，可能是 SARS 疑似病例的学生编号，输出所有找到的疑似病例学生编号。例如，输入数 据如下：100 4 /100 名学生， 4 个学生团体；2 1 2/第一个学生团体有 2 人，是编号 1 和 2 的两位学生，以下三个团体类似；5 1

30、0 13 11 12 142 0 12 99 20/现在发现编号 0 的学生是疑似病例。这时应输出如下：4， 0， 1， 2， 99 表示发现有 4 位疑似病例，是编号是 0， 1， 2， 99 的四位。（可查阅文献：董东，周丙寅编著，计算机算法与程序设计实践，北京：清华大 学出版社， 2010 年 5 月， 55-58 页） 提示：需要将互相接触过的同学组成集合，再检查发现是疑似病例学生所在的集 合的学生成员并计算学生数。初始每个学生自己组成一个集合，然后不断合并参 加了同一个团体的学生所在集合，完成后再寻找给出疑似病例学生所在集合。题目23：设计多种解法计算圆周率n并进行方法比较。例如可以

31、考虑下述方法:(1)随机数法，思路是取一个边长为 1 的单位正方形，在其中做它的内切圆， 再向正方形内扔点，点落在圆内则计数，落在圆外不计数。扔到 5000 个点后停 止，用落入圆内的点数的4倍除以总的扔的点数，就得到n的一个近似值。(2) 用我国古代数学家祖冲之的方法，即用圆内接正多边形逼近。可以从圆内接正六 边形出发，迭代计算园内接正12、24 边形的边长。(3)采用级数：n/2 = 1 + 1/3 + (1*2)/(3*5) +(1*2*3)/(3*5*7) +(1*2*.n)/(3*5*.(2n+1)=1+1/3*(1+2/5*(1+(n-1)/(2n-1)*(1+n/(2n+1).)

32、。说明解法(3)最有利于高精度 计算，例如你用这一解法编写的的程序应该能够求出圆周率n精确到小数点后 100 位，求出 圆周率 n = 3. 1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170677。 提示：(2)可以推导得出若圆内接正i边形边长的一半为xi ,则正2i边形边长的 一半是：X. = (*2 - 2討_ x2 )/2(3)可查阅：杨克昌编著，计算机程序设计典型例题精解，国防科技大学大学 出版社， 1999 年 3 月，第

33、 297-299 页)题目 24：请编写程序,输入正整数 n， 1n=1(1) 输入 n 和 x 的数值，输出此时勒让得多项式的数值。例如输入2，1，应输 出 1/2。(2)输入 n 的数值, 输出此时的勒让得多项式。例如输入 2，应输出 3/2 x2 -1/2。(可查阅：谭浩强著，C程序设计，清华大学出版社(第3版)，2005年7 月第 202 页，习题 8.13) 提示：(1)可以用递归求解，也可以用循环求解。(2)可以用数组表示多项式， 可以用三个数组，前两个计算第三个，计算按递归公式做多项式乘法。输出时插 入字母 x 及其方幂。供参考程序段如下，其中为避免计算分母计算的是 n!Pn(x

34、), 用公式：n!*P (x)=(2n-1)*x*(n-1)!*P 1 (x)-(n-1)*(n-1)*(n-2)!*P 2(x)o 得到 Legendre 多项式还应该用n!与各项系数约分；0系数不输出等，这里省略，请自己加入。题目 27：有一个 3 行 3 列的矩形框，可以看做是 3*3 矩阵，要在其中填入九个 数字 1、2、3、4、5、6、7、8、9，要求左边的大于右边的，上边的大于下边的， 请编写程序输出所有可能的这样的矩阵。例如，你的程序的输出中应该有下面的 矩阵：983762541提示：一个可供参考的解答如下：思路是枚举无相同数字的九位数填入矩阵再检 查是否满足题目要求。分析知左上

35、 00 位置必为 9，因其余 8 数需小于它，左上 中01位置需大于6,因下2左3共5个数需小于它，如此分析可减少枚举 范围。题目 28：(1)设 n 是奇数，请编写程序构造 n*n 阶魔方阵，即行、列、两对角 线上 n 个数之和相等的方阵，图 1 是一个 3*3 魔方阵实例。提示：(2)构造 3*3 素数魔方阵，即找出 9 个不大于 500 的素数并排成魔方阵，图 2 是一个实例，其 行、列、两对角线上 3 个数之和都是 177。8 1 61711347357895929492715101图 1 奇数阶魔方阵图 2 素数魔方阵(可查阅：杨克昌编著，计算机程序设计典型例题精解，国防科技大学大学

36、出版 社， 1999 年 3 月，第 157-162 页)提示：(1)构造规则是：数 1 填在第一行中间，从 2 开始， i+1 放在 i 的上一行 后一列(如 5 在 4 右上)，若格位置超界，则对 n 取模(如 2 右上出界，取模到 左方)，若应放数处已有数，则放在此数下(如 7 放 6 下， 4 放 3 下)。(2)思路 是枚举所有可能性，但要设法减少枚举范围。例如分析 3*3 素数魔方阵可知它应有形式： n-x n+w n-y n+z n n-z n+y n-w n-x中间行列和对角线之和都是3n,其它行列也应是，可推知z=x-y, w=x+y等关系。 因此可生成小于500所有素数，对

37、每个这样的素数n,枚举x，y,检查是否素数 魔方阵。题目 29：大整数的四则运算。大整数指超过十位的十进制整数，这里为简便， 假定不超过 100 位。这类大整数在 C 语言系统中因超界溢出，是不能直接表达 和计算的。可以用数组来表示大整数，在此基础上编写出实现大整数加、减、乘、 除的程序。利用你的程序，计算如100！ 1*3*5*101、264、3ioo、12.3459等的准确数值。提示：可查阅文献：董东，周丙寅编著，计算机算法与程序设计实践，北京：清 华大学出版社， 2010年5月， 126-130页；吕国英，任瑞征等编著，算法设计与 应用，清华大学出版社， 2008年3月， 78-81页等

38、。如果能够做出大整数的加减 的程序，乘法可以累加，除法可以累减。题目30：题目10：穿越沙漠问题：一辆吉普车穿越1000公里的沙漠，吉普车的 总装耗油量为 500 加仑，耗油率为每小时 1 加仑。由于沙漠中没有油库，必须先 用这辆车在沙漠中建立临时油库。请编程求解，若让吉普车用最少的耗油量穿越 沙漠，应该在那些地方建立临时油库，在每个临时油库存储的油量应该是多少。 （可查阅文献：吕国英，任瑞征等编著，算法设计与应用，清华大学出版社， 2008 年3月， 128-130页。）提示：可以从终点向起点分析，第一段长度应是 500 公里，倒数的第一个加油点 应存储500加仑油。第二段就必须有往返了，最

39、有效率的走法应该满足：（1）走 奇数次，保证最后向终点方向；（2）向终点时要满载；（3）本储油点要存储下一 储油点需要和路上消耗的油量。题目31最小包围圆问题：输入平面上n个点的坐标，输出一个圆的圆心和半径， 这个圆刚好包围了给出的n个点，即这个圆是包围了给出所有点的最小的圆。设 这n个点是n个居民点的位置，考虑修建一个向各居民点供应物资的仓库就应该 选择在最小包围圆的圆心。（参考书：Mark de Berg等著，邓俊辉译，计算几何- 算法与应用（第3版），清华大学出版社， 2009年8月， 91-94页。还可见杨克 昌编著，计算机程序设计典型例题精解，国防科技大学大学出版社， 1999 年

40、3 月，第226-229页等。） 提示：直接解法是计算圆周边界过点集中两点、三点的所有圆再找最小的。一个 思路是记点集Pi= p2,pi, Di为点集片的最小包围圆。注意到以下性质 是可以利用的：若点p WD.则D. = D.,即若i-1个点的最小包围圆已经i i-1i i-1i-1求出，新的一点R,若在Di-1内部，则Di-1也是加入新点后的最小包围圆；若点 p不是在D.1内部，则最小包围圆D是圆周边界通过点p并包含了前面i-1个 ii-1ii点的一个圆，不再是D. 1 了。这样可以通过下面三个函数求出最小包围圆（这里 只给出框架，请加细完成, 即需要增加的函数或代码请自行设计和完成。例如，

41、 设计：函数MiniDisc（ P“），求输入点集Pn的最小包围圆。函数MiniDiscOne（ Pn, q），求通过点q，包含了点集Pn中所有点的最小包围圆。函数MiniDiscTwo（ P：,qq2)，求通过点ql和q2，包含了点集Pn中所有点的最小包围圆。题目 32：设海岸线是一条任意长的直线，海洋中有一些岛屿，希望在海岸线上 修建雷达站，使发射半径能够覆盖所有岛屿。可以假定直角坐标系中 x 轴是海岸 线， x 轴上方是海洋，下方是陆地，给出各岛屿位置坐标 (xi, yi), yi 0, i = 0丄2,n-1;雷达发射可以覆盖的半径d,你的任务是编写程序，判断是否可以 修建出满足要求的

42、雷达站，如果可以，找到覆盖所有岛屿需要的最少的雷达站个 数及可以安排的位置。(可查阅文献：董东，周丙寅编著，计算机算法与程序设 计实践，北京：清华大学出版社， 2010 年 5 月， 180-183 页)提示：容易看出对任意yi，如果出现yi d,则问题无解。问题有解时，覆盖点 (xi, yi) 的圆的圆心位置可以在如下区间中：I x _ d2 y2, x +d2 y2 iii ii剩下的问题是对这些区间进行分组和求交了。题目 33：五猴分桃问题是：五只猴子合作摘了很多桃子，感到累了，决定先去 睡觉，醒后再分。不知过了多久，第一只猴子醒了，看见其它猴子都没有醒，就 把所有桃子分为五堆，发现多一

43、个，就吃了一个，拿走一堆，把剩下的又堆在一 起走了。第2 只猴子醒来，以为自己是第一个，也是把桃子分为五堆，也是多一 个，就吃了一个，拿走一堆，剩下的又堆在一起走了。第3， 4， 5 只猴子都是这 样。现在问总共摘了多少桃子，每只猴子连吃再拿是多少？最后还剩多少？据说， 这个问题是著名物理学家狄拉克提出来的，美籍中国著名物理学家李政道访问中 国科技大学少年班时用做考题，少年班的同学都没有当时解答出来。我们是计算 机系的同学，可以编写一个很简单的程序轻松地解此问题。当然程序解答后也可 以考虑一下如何更简单巧妙些解此问题。(可参阅：谈祥柏著，乐在其中的数学， 科学出版社，2005年8月，总序v -

44、vii页。) 提示：可参考以下程序段： /五猴分桃问题void main()/从 1 至 10000 枚举 int i,x,c; /在上范围内找到三个解： 3121, 6246, 9371 for(i=1;i10000;i+)x=i;c=0;while(x-1)%5 = 0)x=x-1-(x-1)/5;c+; if(c=5) printf(i=%d,x=%dn,i,x); getchar();题目34：勾股数生成：满足关系x2 + y2= z2的一组三个正整数(x, y, z),称为是 一组勾股数。请编写程序。输出所有小于 100 的勾股数组。本题要求给出效率较 高的程序，即如果用三重循环枚举所有小于 100 的正整数三元组算一种解法，那 么至少还要给出另外一种效率更高的解法。进一步考查是否存在一组三个正整数 (x, y, z), 满足 x3 + y3 = z3， x4 + y4 = z4 等。(可查阅：杨克昌编著，计算机程序设计典型例题精解，国防科技大学大学出版 社， 1999 年 3 月，第 64-67 页)提示：注意到若 x=a2-b2, y=2ab, z=a2+b2, 则 x, y, z 是一组勾股数。题目 35：组合与排列的生成：先考虑组合