算法设计技巧与分析课后习题答案沙特.docx

1、算法设计技巧与分析课后习题答案沙特算法设计技巧与分析课后习题答案沙特【篇一：高级算法设计实验指导书2009(李淑琴)】=txt一、适用专业 计算机科学与技术专业研究生 二、实验目的与任务 算法分析与设计是计算机科学与技术专业本科学生第八学期专业选修课程。实验课的目的是通过对一些常见而有代表性算法的上机实践，使学生理解和掌握算法设计的主要方法，培养学生对算法复杂性进行正确分析的能力，从而为独立地设计算法和对给定算法进行复杂性分析奠定坚实的基础。 三、实验内容安排 实验一 数据的排序算法比较 （一）、实验目的 1 通过上机实践，进一步理解、掌握几种著名的数据排序算法； 2 对排序算法的时间复杂性学

2、会比较、分析。 （二）、实验内容及要求 （1） 从已学过的内部排序算法中至少选择4种算法，比较这四种算法的关键字 移动次数以及比较次数。 （2） 待排序数据用随机数产生程序产生。 （3） 数据表的长度不小于100000，并且至少用五组不同的输入数据作比较。 （4） 最后对结果作出简单分析，包括对各组数据得出结果波动大小的解释。 （三）、实验步骤 1. 2. 3. 4. 5. 对于以上题目要认真分析和理解题意，设计出算法； 详细写出正确的高级语言源程序； 上机录入并调试程序； 请指导教师审查程序和运行结果并评定成绩； 撰写并上交实验报告。 （四）、实验报告内容 1 班级、学号、姓名、实验日期；

3、2 实验题目； 3 对于实验题目的理解与说明； 4 程序功能与框架； 5 设计说明（存储结构、特别构思等）； 6 调试报告（调试过程中遇到的问题及如何解决此问题，程序设计的得失，对于改进程序的设想、经验、体会等）； 7 对算法进行比较分析； 8 附录：源程序清单（加必要的注释）、测试数据及运行结果。 （五）、 实验成绩考核方法 实验成绩由实验结果、问题回答以及实验报告综合评定。 实验二 递归与分治策略 （一）、实验目的 通过编程实现递归与分治策略的有关算法，理解递归与分治策略算法的原理，掌握递归与分治策略基本思想与应用技巧。 （二）、实验内容及要求 实验内容 给定平面上的至少n个点（n=20）

4、，找出其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。 实验要求 1 参照教材中给出的最接近点对问题算法的部分程序代码。完善程序，实现该算 法。 2 结果显示出具体的距离最小的两个点坐标以及最小距离值。 （三）、实验步骤 1对于以上题目要认真分析和理解题意，设计出算法； 2详细写出正确的高级语言源程序； 3上机录入并调试程序； 4请指导教师审查程序和运行结果并评定成绩； 5撰写并上交实验报告。 （四）、实验报告内容 1. 班级、学号、姓名、实验日期； 2. 实验题目； 3. 对于实验题目的理解与说明； 4. 程序功能与框架； 5. 设计说明（存储结构、特别构思等）； 6. 调试

5、报告（调试过程中遇到的问题及如何解决此问题，程序设计的得失，对于改进程序的设想、经验、体会等）； 7. 对算法的时间复杂性进行分析； 8. 附录：源程序清单（加必要的注释）、测试数据及运行结果。 （五）、实验成绩考核方法 实验成绩由实验结果、问题回答以及实验报告综合评定。 实验三 动态规划 （一）、实验目的 通过编程实现动态规划的有关算法，理解动态规划的原理，掌握动态规划基本思想与应用技巧。 （二）、实验题目与要求： 实验题目： 若城市路径示意图如下图所示， 图中，每条边上的数字是这段道路的长度。条件：从a地出发，只允许向右或向上走。试寻找一条从a地到b地的最短路径和长度。 实验要求： 1 理

6、解动态规划算法的原理，认真阅读题目。完善程序，实现该算法； 2 结果具体显示出最短路径和最短距离长度。 （三）、实验步骤 1. 2. 3. 4. 5. 对于以上题目要认真分析和理解题意，设计出算法； 详细写出正确的高级语言源程序； 上机录入并调试程序； 请指导教师审查程序和运行结果并评定成绩； 撰写并上交实验报告。 （四）、实验报告内容 1. 班级、学号、姓名、实验日期； 2. 实验题目； 3. 对于实验题目的理解与说明； 4. 程序功能与框架； 5. 设计说明（存储结构、特别构思等）； 6. 调试报告（调试过程中遇到的问题及如何解决此问题，程序设计的得失，对于改进程序的设想、经验、体会等）；

7、 7. 对算法的时间复杂性进行分析； 8. 附录：源程序清单（加必要的注释）、测试数据及运行结果。 （五）、实验成绩考核方法 实验成绩由实验结果、问题回答以及实验报告综合评定。 实验四 分支界限算法 （一）、实验目的 通过编程实现有关的分支界限算法，理解分支界限算法的原理，掌握分支界限算法基本思想与应用技巧。 （二）、实验题目与要求 实验题目： 旅行商问题。给出一个城市的集合和一个定义在每一对城市间的耗费函数，找出耗费最小的旅行。 实验要求： 1. 2. 理解分支界限算法的原理，编写程序实现相应算法。 明确显示出运行结果； （三）、实验步骤 1. 2. 3. 4. 5. 对于以上题目要认真分析

8、和理解题意，设计出算法； 详细写出正确的高级语言源程序； 上机录入并调试程序； 请指导教师审查程序和运行结果并评定成绩； 撰写并上交实验报告。 （四）、实验报告内容 1. 2. 3. 4. 5. 6. 班级、学号、姓名、实验日期； 实验题目； 对于实验题目的理解与说明； 程序功能与框架； 设计说明（存储结构、特别构思等）； 调试报告（调试过程中遇到的问题及如何解决此问题，程序设计的得失，对于 改进程序的设想、经验、体会等）； 7. 对算法的时间复杂性进行分析； 8. 附录：源程序清单（加必要的注释）、测试数据及运行结果。 （五）、实验成绩考核方法 实验成绩由实验结果、问题回答以及实验报告综合评

9、定。 四、主要参考书 1. 算法设计技巧与分析 沙特m.h.alsuwaiyel著 吴伟 方世昌等译电子工2. 3. 4. 5. 6. 7. 业出版社 算法设计与分析郑宗汉 郑晓明清华大学出版社 数据结构习题集严蔚敏 吴伟民 米宁清华大学出版社 计算机算法基础余祥宣等 华中理工大学出版社 计算机算法：设计与分析引论 美s.巴斯著 朱洪等译 复旦大学出版社 算法分析与设计 王晓东 清华大学出版社 算法设计和分析 朱洪等 上海科技文献出版社【篇二：2012c语言程序课程设计备选题目】：（1）较重要c语言程序设计教科书中的例题或习题；（2）与计算机学科相关的后续课程，如数据结构、离散数学、组合数学、

10、计算方法等课程教科书中的例题或习题中，不需要相关后续课程的专门知识就可以很好解答的题目；其它有影响计算机程序设计类书籍或文章中的例题；（3）各级各类计算机程序设计竞赛（例如acm大赛）、程序员考试、求职面试的训练题和考试题等。欢迎老师和同学们提供更好的题目。 2题目内容涉及的知识点不超过大学一年级的知识水平，主要目标是训练学生将实际问题转化为计算机可以处理的形式并编写程序给出解答的能力。去掉了较复杂事务管理如图书管理、学生成绩管理之类的题目，这类事务管理方面题目希望在后续课程如c+面向对象程序设计、数据库应用及各专业的课程设计中进行。 3 题目有多种完全不同的解答，给出的提示主要供指导教师参考

11、。 题目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）编写函数maxprime(int *p,int n), 找出其中最大的素数，如果不存在素数函数结果为0。（5） 对于这些整数排序之后，分别输出相邻两数之差最大和之

12、差最小的两个数，如果有多组满足条件要输出所有的。（6）定义函数myinput(int a,int n)，用fgetc函数从文件“file1.dat”上逐个读入字符，并将其转换成独立的正整数,并依次存入数组a中。 提示：可查阅任何一本c语言程序设计教科书中关于文件部分，例如谭浩强，c程序设计（第三版），第13章。还需要熟悉随机数生成函数rand（），需要编写判断一个奇整数是否素数的程序等。部分可供参考程序如下： 题目2：两个文件同时对照显示：程序从两个文件中读出文本行，并列显示在屏幕上。假定屏幕有80列，25行，则第034列显示第一个文件的内容，第4074列显示第二个，第77-78行显示文本总的

13、行序号。每屏显示20行，超过20行就显示在下一屏。程序应该能够以这种方式显示任意的两个文本文件，例如两个c程序源代码文件，两篇内容类似的文章形成的两个文本文件等。 提示：先把两个文本文件读入，存入数组，再考虑显示的安排。 题目3：实现一个c语言程序设计自助学习系统,要求实现的基本功能如下： 1、测验 （1）可以按固定的试题数目，从题库中随机选取题目进行测试，如每次测试5道题或10道题。 （2）每次只显示一道题，包括问题描述、备选答案； （3）根据学生答题结果，对比试题答案，显示答题对错的信息；（4）答题全部结束后给出本次测试的成绩，按百分制评分。 2、学习管理 （1）通过题目浏览，自我测验，查

14、看题解的过程来帮助学生学习。 （2）需要为学生提供多种学习方式，至少应包括顺序选题学习和随机选题学习等方式。 （3）如果是采用顺序选题方式学习，需要做到可以从中间某个位置开始学习，不是每次一定从第一题开始学习。 3、题库管理 （1）试题库中保存全部试题及其相关信息。 （2）将要入库的试题，按固定格式编辑整理好保存在ascii文件中，通过计算机程序读取该文件，并将文件中的全部试题添加到已有的试题库中。 （3）今后需要对于所有试题分类进行管理，在库结构设计时，要考虑这些扩展功能的数据接口要求。 （4）试题库初始化，将试题库内容全部清空，便于重新建立系统。 提示：可以参考：余江，肖淑芬主编，c语言程

15、序设计，天津科学技术出版社，2001年5月，273-313页。 题目4：实现题目3中c语言程序设计自助学习系统得升级版，可考虑实现功能： 一、测验 1、系统自动组卷 （1）试卷结构说明：以题库提供的试题类别和各类试题的数量为依据来实现。系统组卷前需要获得的信息是对于每类试题要含有类别名称、试题数、分数，所有类别的分数累加在一起要恰好是100分。 （2）试卷保存：将上述组卷结果保存在二进制文件中，文件名由用户输入。 （3）个性化组卷：输入学号后，系统根据试卷结构说明的规定自动组卷，做到每个学生试卷不同。 2、错题本功能 （1）答错的题目自动加入到错题本中； （2）可以对错题本中的题目逐题测验，不

16、分题目类别； （3）可以制定分类测试。 3、多科目测试 二、学习管理 1、分类别学习 2、错题本内容学习 3、多科目学习，选择科目后可以进行指定类别的分类别学习和错题本内容学习。 三、题库管理 1、入库试题文件格式正确性检查。包括：试题的描述的合法性检查，类别信息合法性检查，给出出错位置的信息。2、对于分类试题存储方式的优化，例如：同类试题连续存储的实现； 3、目前完成的是单科目多类别的题库管理，要实现多科目多类别的题库管理。 四、用户管理 1、系统注册 2、登录 3、错题本等个性化信息管理 4、屏幕背景颜色和字符颜色的设置 5、学习位置的记载，要按科目记载，每个科目要按类别记载。 提示：鼓励

17、使用更多方法实现，例如使用数据库系统，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层；（4）相同层上的数从左向右从小到大排列。其实第i层是有i个素数因子的数的从小到大的排列。例如对n=6，符合这组规则的数字金字塔如下： 1 2 3 5 46 每个数按照它在塔中的位置从上到下从左到右从1开始编号，例如5，编号应该是4。要求你编写程序，输入

18、一个正整数n，5n50, 再输入3个不大于n的正整数，然后程序输出所构造的数字金字塔，及所输入3个不大于n的正整数在数字金字塔中的编号。例如设输入了6，3，4，5，程序可以输出： 1 2 3 5 4 6/用数组形式表示数字金字塔。 3，5，4 /分别是3，4，5在数字金字塔中的编号。 程序编写完成后，要求给出你的程序对下列两组输入的结果： （1）10，7，8，9 （2）25，15，20，25 提示：本题为2010年acm大赛题目，鼓励使用更多方法实现。 题目6：你一定很熟悉著名的hanoi塔游戏，当理解了圆盘数目较多需要的时间太长之后，你可以放弃实际去移动圆盘，但你不应该放弃如下一个有点类似的

19、游戏：设有n根柱子，每根柱子上有一个圆盘，圆盘上有一个正整数，不同圆盘上的数不同。初始时假定柱子按照其上圆盘上数的大小从左向右排列，移动规则是从左向右看，当前一根柱子最下圆盘上数与后一根柱子最上圆盘上数相加的和是一个完全平方数时，前一根柱子上所有圆盘移动到后一根柱子上方。要求你编写程序，输入柱子数目和圆盘上的整数，输出移动的过程和结果。例如，一组输入是：4，1，3，5，6，第一个数4表示有4根柱子，圆盘上的数依次是1，3，5， 6。你的程序运行后，可以输出1-3-6, 5, c=2，表示移动是1到3，3到6，因为1+3=4, 3+6=9,而4和9是完全平方数，符合条件的移动只有这两次。移动结果

20、是还有2根柱子上有圆盘，即c=2，有圆盘的一根柱子上圆盘3个，有数1-3-6，有圆盘另一根柱子上圆盘一个，有数5，它其实没有发生移动。程序编写完成后，要求给出你的程序对下列两组输入的结果：（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进制数中有

21、判断整除性的二个简单规则：一个正整数能够被3整除，当且仅当，它的各位数字之和能够被3整除；一个正整数能够被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，则要

22、输出x为7，y为11（请自己验证这是对的）。（本题为2011年acm大赛题目。） 提示：对于10进制数，10-1=9=3*3，10+1=11，10进制数n可以一般地表示为： n = ak10k + ak-110k-1 + + a110 + a0 保持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分，这时比较甲同学和乙同学的成

23、绩，只能说语文较差，数学较好，综合到一起就属于无法比较，但对丙同学可以比较，可以说甲和乙同学的成绩都比丙同学好。一般情况，设有一个三元向量的集合，若其中有向量p=(p1, p2, p3), q=(q1, q2, q3), 规定pq 当且仅当 p1q1, p2q2, p3q3 。其中一个向量称为是一个极小元素，当且仅当它只 它自己。例如如下三个三元向量组成了向量组（80，90，100），（90，80，70），（60，70，60），其中只有一个最小元素，是（60，70，60）。请编写程序，输入n个三元向量，输出其中最小元素的数目。（本题为2011年acm大赛题目。） 提示：先对第一个坐标排序，再考

24、虑第二个坐标，第三个坐标。 题目9：在某城市有n座摩天大楼，问那二座之间的距离最小？设可以输入所有大楼的位置坐标，请编写程序输出距离最近的二座大楼及它们之间的距离。两点(x1d按照两种不同方式规定：（1）euclid距离（2）manhattan距离 d = | x1 x2 | + | y1 y2 |。显然的解法是计算所有点对之间的距离再找出最小值，但本题只要求输出距离最近的二点及之间距离，所以应该给出不计算所有点对之间距离的更有效率的解法（本题为2011年acm大赛题目）。（可查阅：沙特m.h.alsuwaiyel著，吴伟昶等译，算法设计技巧与分析，电子工业出版社，2004年8月，第121-1

25、24页。或者： 美michael t.goodrich等著，霍红卫译，算法分析与设计，人民邮电出版社，2006年10月，第385-387页。） 提示：找到两点距离d后，接下去可检查宽不超过d的长条。 题目10：一条贪吃的蛇在一个n*m的网格中游走，它只能从一个方格走向另一个相邻的方格，这里相邻的意思是两个方格有公共边。每个方格可以看作是一个房间，其中一些是空的，一些存放有苹果。贪吃的蛇根本不进入空的房间，而进入有苹果的房间后就可以带走所有苹果使房间成为空的。蛇从一个指定的房间出发，最终回到它的家，把一路带来的苹果存储到家中，当然，它希望带来的苹果最多。请编写程序，输入有整数n和m，及n*m的一

26、个矩阵，矩阵元素数值中有一个是 -1，表示蛇的出发位置，有一个是 -2，表示蛇的家的位置，其余数值是非负整数，0表示房间为空，非零整数表示苹果的数目。输出蛇选择的游走路径和获得的最多的苹果数目。例如输入4*4矩阵： 704 18 4011 157 11-1 0 12 -20 则应输出 (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。（本题为2011年acm大赛题目）。（可查阅：吕国英，任瑞征等编著，算法设计与分析（第2版），清华大学出版社，20

27、09年1月，第200-202页。 提示：这是一个利用回溯算法的迷宫搜索类型问题，可参考类似问题的已有解法。 题目11：化学家研究原子团的行为时，认为每个原子具有整数能量，这个整数可以是正数、零和负数，绝对值不超过100。可以认为原子排列成为一行，一行中任意多个连续的原子可以形成原子团，原子团的能量是其中各原子能量的代数和。问题是怎样编写程序，求出具有最大能量的原子团和能量数值。要求程序输入一列原子的能量数值，以-1结束，输出找到的能量最大的原子团及能量数值。例如输入8，0，6，4，-2，-1，应输出原子团8，0，6，4，及能量数值18。（本题为2010年acm大赛题目）(可查阅：吕国英，任瑞征

28、等编著，算法设计与分析，清华大学出版社，2009年1月，第265-270页)。 提示：这是最大子段和问题。 题目12：一刀可以把蛋糕分为两个部分，现在给出要分为两部分的面积的比值，希望求出切口的弦的长度。这里当然要假定蛋糕是一个圆，并设其半径为1。例如，输入两部分比值为1：1，切口是直径，长为2；输入1：2，应输出1.9285；【篇三：回溯法(马周游问题)实验报告】txt姓名黎国庄 学号 20062101247 院系计算机学院 专业计算机科学与技术 年级班级 小组实验任务分工独立完成 实验时间 2008年6月 3 日 实验名称回溯法的应用 指导老师及职称 陈卫东老师 华南师范大学教务处编印 实

29、验课程：算法分析与设计 实验名称：回溯法的应用 （综设型实验） 第一部分 实验内容 1实验目标 （1）熟悉使用回溯法求解问题的基本思路。 （2）掌握回溯算法的程序实现方法。 （3）理解回溯算法的特点。 2. 实验任务 （1）从所给定的题目中选择一题，使用回溯法求解之。 （2）用文字来描述你的算法思路，包括解空间、限界函数、算法主要步骤等。 （3）在windows环境下使用c/c+语言编程实现算法。 （4）记录运行结果，包括输入数据，问题解答及运行时间。 （5）分析算法最坏情况下时间复杂度和空间复杂度。 （6）谈谈实验后的感想，包括关于该问题或类似问题的求解算法的建议。 3. 实验设备及环境 p

30、c；c/c+等编程语言。 4. 实验主要步骤 (1) 根据实验目标，明确实验的具体任务； (2) 设计求解问题的回溯算法，并编写程序实现算法； (3) 设计实验数据并运行程序、记录运行的结果； (4) 分析算法时空性能； (5) 实验后的心得体会。 第二部分 问题及算法 1. 问题描述 2. 回溯法的一般思路 对于马所在其中一格时，它可以走的位置有以下8种情况： 马 所以对于每一个马所在的格子里，马可以走对应的8个方向。 用满8叉树，每一个子树对应马可跳的方向 当要走下一子树（跳下一格）时，该子树可走（还没有走过并且在棋盘里边），即沿该方向走下去，当不可以走，即回溯到上一步，选择另一方向往下走

31、；当该子树的8个子棋都遍历完了（即8个方向都走过了），则回溯到它父亲那里。 重复一直做下去，到棋盘每个格子都走过一遍，而且回到出发点或者找不到路径即结束。 3. 求解问题的回溯算法描述 算法如下： 输入：v（x,y）马开始的起点 输出：马从第一步到最后一步（64）的先后次序数字 1v （） 2.flag false 3k 1 4while k1 5while x 没有被穷举 k 6. x x 中的下一个元素；将x 加入v kkk 7if v为最终解then set flag true，且从两个while循环退出 8. else if v是部分解then k k+1 前进 9. end while k11 k k-1回溯 12end while 13if flag then output v 14else output “no solution” 4. 算法实现的关键技