《算法设计与分析》课程实验与设计 福州大学 王晓东

习题2-1 求下列函数的渐进表达式：3n^2+10n; n^2/10+2n; 21+1/n; logn^3; 10 log3^n 。

解答：3n^2+10n=O(n^2),n^2/10+2^n=O(2^n),21+1/n=O(1),logn^3=O(logn),10log3^n=O(n).习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n^2,logn,3^n,20n,2,n^2/3。

解答：照渐进阶从高到低的顺序为：n!、3^n、4n^2 、20n、n^2/3、logn、2习题2-4(1)假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。

在某台计算机上实现并完成该算法的时间为t秒。

现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？(2)若上述算法的计算时间改进为T(n)=n^2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？(3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答：(1)设能解输入规模为n1的问题，则t=3*2^n=3*2^n/64,解得n1=n+6(2)n1^2=64n^2得到n1=8n(3)由于T（n)=常数，因此算法可解任意规模的问题。

习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。

对于计算复杂性分别为n，n^2，n^3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？解答：n'=100nn'^2=100n^2得到n'=10nn'^3=100n^3得到n'=4.64nn'!=100n!得到n'<n+log100=n+6.64习题2-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ（g(n)），并简述理由。

《算法设计与分析》课程实验教学大纲Design and Analysis of Computer Algorithm总学时 16 总学分 0.5 实验学时 16一、基本情况1. 课程性质：专业实践2. 设课方式：独立设课3. 适用专业：计算机科学与技术专业4. 开课学期：第5学期5. 实验教材：《算法设计与分析》实验指导书6. 先修课程：高级语言程序设计、离散数学、数据结构二、课程简介算法设计与分析实验将覆盖计算机软件实现中的大部分算法，具有一定的深度和广度，目的是让学生掌握递归与分治策略、动态规划、贪心算法、回溯法、分支限界法等算法思想；能独立运用相关算法策略来分析、解决实际问题并编程实现。

同时，算法设计与分析实验是对学生在软件设计方面的综合训练，包括问题分析，总体结构设计，程序设计基本技能和技巧等，以培养良好的编程风格和科学作风。

通过理论联系实际，最终提高学生动手操作的能力以及分析问题和解决问题的能力，培养对算法的复杂性进行分析的逻辑思维能力。

三、实验目的与任务实验是教学内容的重要一环，其目的一方面是为了让学生掌握算法设计与分析中的一些常用的典型的算法设计思想和方法；另一方面是为了让学生切实掌握各种算法的具体实现方法，培养学生的实际动手能力，加强学生创新思维能力的培养。

四、课程的基本要求（1）了解实验目的，熟悉实验环境。

（2）预习实验，准备好实验题目和操作步骤。

（3）能编译调试源程序,分析错误原因并加以修改,得出正确结果。

（4）能运用所学的知识正确分析程序得出的结果，并能给出改进的方案。

（5）将上述各项要求及实验结果编写成实验报告。

实验前学生要认真预习实验内容，按要求编写源程序及准备测试数据。

实验中,要按操作规程操作计算机，集中精力调试程序,并认真测试实验数据。

对实验程序的故障应自行分析解决，不拷贝其它人的成果。

对实验得出的结果能加以分析，提出改进的具体措施。

掌握递归与分治策略、动态规划、贪心算法、回溯法、分支限界法等算法思想；能独立运用相关算法策略分析问题、解决实际问题并编程实现。

第一章作业1.证明下列Ο、Ω和Θ的性质1）f=Ο(g)当且仅当g=Ω(f)证明：充分性。

若f=Ο(g)，则必然存在常数c1>0和n0，使得∀n≥n0，有f≤c1*g(n)。

由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。

必要性。

同理，若g=Ω(f)，则必然存在c2>0和n0，使得∀n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。

2）若f=Θ(g)则g=Θ(f)证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得∀n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。

由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。

3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。

证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得∀n≥n1，有F(n) ≤ c1 (f(n)+g(n))= c1 f(n) + c1g(n)≤ c1*max{f,g}+ c1*max{f,g}=2 c1*max{f,g}所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g))对于Ω和Θ同理证明可以成立。

4）log(n!)= Θ(nlogn)证明：∙由于log(n!)=∑=n i i 1log ≤∑=ni n 1log =nlogn ，所以可得log(n!)= Ο(nlogn)。

∙由于对所有的偶数n 有，log(n!)= ∑=n i i 1log ≥∑=n n i i 2/log ≥∑=nn i n 2/2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。

当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得∀n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。

《算法设计与分析》课程实验与设计福州大学王晓东第1章算法引论算法实现题1-1 统计数字问题算法实现题1-2 字典序问题算法实现题1-3 最多约数问题算法实现题1-4 金币阵列问题算法实现题1-5 最大间隙问题第2章递归与分治策略算法实现题2-1 输油管道问题算法实现题2-2 众数问题算法实现题2-3 邮局选址问题算法实现题2-4 马的Hamilton周游路线问题算法实现题2-5 半数集问题算法实现题2-6 半数单集问题算法实现题2-7 士兵站队问题算法实现题2-8 有重复元素的排列问题算法实现题2-9 排列的字典序问题算法实现题2-10 集合划分问题算法实现题2-11 集合划分问题2算法实现题2-12 双色Hanoi塔问题算法实现题2-13 标准2维表问题算法实现题2-14 整数因子分解问题算法实现题2-15 有向直线2中值问题第3章动态规划算法实现题3-1 独立任务最优调度问题算法实现题3-2 最少硬币问题算法实现题3-3 序关系计数问题算法实现题3-4 多重幂计数问题算法实现题3-5 编辑距离问题算法实现题3-6 石子合并问题算法实现题3-7 数字三角形问题算法实现题3-8 乘法表问题算法实现题3-9 租用游艇问题算法实现题3-10 汽车加油行驶问题算法实现题3-11 圈乘运算问题算法实现题3-12 最少费用购物算法实现题3-13 最大长方体问题算法实现题3-14 正则表达式匹配问题算法实现题3-15 双调旅行售货员问题算法实现题3-16 最大k乘积问题算法实现题3-17 最小m段和问题算法实现题3-18 红黑树的红色内结点问题第4章贪心算法算法实现题4-1 会场安排问题算法实现题4-2 最优合并问题算法实现题4-3 磁带最优存储问题算法实现题4-4 磁盘文件最优存储问题算法实现题4-6 最优服务次序问题算法实现题4-7 多处最优服务次序问题算法实现题4-8 d森林问题算法实现题4-9 汽车加油问题算法实现题4-10 区间覆盖问题算法实现题4-11 硬币找钱问题算法实现题4-12 删数问题算法实现题4-13 数列极差问题算法实现题4-14 嵌套箱问题算法实现题4-15 套汇问题算法实现题4-16 信号增强装置问题算法实现题4-17 磁带最大利用率问题算法实现题4-18 非单位时间任务安排问题算法实现题4-19 多元Huffman编码问题算法实现题4-20 多元Huffman编码变形算法实现题4-21 区间相交问题算法实现题4-22 任务时间表问题第5章回溯法算法实现题5-1 子集和问题算法实现题5-2 最小长度电路板排列问题算法实现题5-3 最小重量机器设计问题算法实现题5-4 运动员最佳匹配问题算法实现题5-5 无分隔符字典问题算法实现题5-6 无和集问题算法实现题5-7 n色方柱问题算法实现题5-9 拉丁矩阵问题算法实现题5-10 排列宝石问题算法实现题5-11 重复拉丁矩阵问题算法实现题5-12 罗密欧与朱丽叶的迷宫问题算法实现题5-13 工作分配问题算法实现题5-14 独立钻石跳棋问题算法实现题5-15 智力拼图问题算法实现题5-16 布线问题算法实现题5-17 最佳调度问题算法实现题5-18 无优先级运算问题算法实现题5-19 世界名画陈列馆问题算法实现题5-20 世界名画陈列馆问题（不重复监视）算法实现题5-21 部落卫队问题算法实现题5-22 虫蚀算式问题算法实现题5-23 完备环序列问题算法实现题5-24 离散01串问题算法实现题5-25 喷漆机器人问题算法实现题5-26 n2-1谜问题第6章分支限界法算法实现题6-1 最小长度电路板排列问题算法实现题6-2 最小长度电路板排列问题算法实现题6-3 最小权顶点覆盖问题算法实现题6-4 无向图的最大割问题算法实现题6-5 最小重量机器设计问题算法实现题6-6 运动员最佳匹配问题算法实现题6-7 n皇后问题算法实现题6-8 圆排列问题算法实现题6-9 布线问题算法实现题6-10 最佳调度问题算法实现题6-11 无优先级运算问题算法实现题6-12 世界名画陈列馆问题算法实现题6-13 骑士征途问题算法实现题6-14 推箱子问题算法实现题6-15 图形变换问题算法实现题6-16 行列变换问题算法实现题6-17 重排n2宫问题算法实现题6-18 最长距离问题第7章概率算法算法实现题7-1 模平方根问题算法实现题7-2 素数测试问题算法实现题7-3 集合相等问题算法实现题7-4 逆矩阵问题算法实现题7-5 多项式乘积问题算法实现题7-6 皇后控制问题算法实现题7-7 3SAT问题算法实现题7-8 战车问题算法实现题7-9 圆排列问题算法实现题7-10 骑士控制问题算法实现题7-11 骑士对攻问题第9章近似算法算法实现题9-1旅行售货员问题的近似算法算法实现题9-2 可满足问题的近似算法算法实现题9-3 最大可满足问题的近似算法算法实现题9-4 子集和问题的近似算法算法实现题9-5 子集和问题的完全多项式时间近似算法算法实现题9-6 实现算法greedySetCover算法实现题9-7 装箱问题的近似算法First Fit算法实现题9-8 装箱问题的近似算法Best Fit算法实现题9-9 装箱问题的近似算法First Fit Decreasing 算法实现题9-10 装箱问题的近似算法Best Fit Decreasing 算法实现题9-11 装箱问题的近似算法Next Fit第10章算法优化策略算法实现题10-1 货物储运问题算法实现题10-2 石子合并问题算法实现题10-3 最大运输费用货物储运问题算法实现题10-4 五边形问题算法实现题10-5 区间图最短路问题算法实现题10-6 圆弧区间最短路问题算法实现题10-7 双机调度问题算法实现题10-8 离线最小值问题算法实现题10-9 最近公共祖先问题算法实现题10-10 达尔文芯片问题算法实现题10-11 多柱Hanoi塔问题算法实现题10-12 线性时间Huffman算法算法实现题10-13 单机调度问题算法实现题10-14 最大费用单机调度问题算法实现题10-15 飞机加油问题《算法设计与分析》期中试卷1 试题1 数列极差问题试题2 双调TSP回路问题试题3 最佳调度问题《算法设计与分析》期中试卷2 试题1 石子合并问题试题2 整数因子分解问题试题3 汽车加油问题《算法设计与分析》期终试卷1 试题1 乘法表问题试题2 工作分配问题试题3 飞行员配对方案问题《算法设计与分析》期终试卷2 试题1 直线k中值问题试题2 图形变换问题试题3 无向图的最大割问题。

《计算机算法设计与分析》第二版王晓东“最大m字段和优化函数”——P57注释之所以想到要注释一下，没别的意思，只是因为几个月前刚学DP，完全看不懂，前几天费了几个小时终于看懂了，注释下来，能使自己整理一下思路，也作为自己的一篇日记。

当时我能看懂时间和空间均为O(MN^2)的函数，但可能由于自己看书是直接从动态规划一章看起，书上对于经过优化的函数也没有更多的解析，当时看起来完全不知所云。

前几天看的时候，是对着方程结合书上的几句话自己去理解，尝试自己动手去写，但错了。

看书上代码，都要自己去理解那些变量数组是干什么用的，感觉也是非常吃力。

1，我觉得理解那个优化函数，必须先要充分理解那个二维的DP方程：b[i][j]=max(b[i][j-1]+a[j],max(b[i-1][t])+a[j]) (i-1<=t<j)b[i][j]表示的是第i段在前j项（含第j项）的最大值。

对于b[i][j]含有第j项必须要理解好！则方程的意思是：对于a[j]项，要么将它加到第i段，要么它自己作为新的一段。

注意到方程外层的max选择，都要加上a[j]这一项。

这里可能很容易产生一个疑问，如果a[j]是一个负数，为什么还要加上a[j]呢？回到b[i][j]所表示的意义上解释，由于b[i][j]表示的是含有第j项的最大值，所以a[j]是肯定要加进来的。

假使a[j]是一个负数，它加进来了也不会影响在第i段中前j-1项的最大值。

所以第m段的最大值，并不是b[m][n]，而是b[m][m~n]之间的最大值。

同样道理，第i-1段的最大值是b[i-1][t],(i-i<=t<j)。

2，理解了上述的DP方程后，再来考虑优化，正如书上所说的，由于在第i段中，只用到第i段和第i-1段的值。

如果采用一维数组存储b[]，只要在计算第i段的时候，没有去改变第i-1段保留下来的值即可。

再考虑到，内层max选择，需要用到第i-1段在i-1到j-1位置的最大值，不但要进行重复计算，也影响到b[j]的计算，因为j前面的值既要用作b[j]的计算，也要更新作为下一段i+1计算时所用。

习题2-1 求下列函数的渐进表达式：3n^2+10n; n^2/10+2n; 21+1/n; logn^3; 10 log3^n 。

解答：3n^2+10n=O(n^2),n^2/10+2^n=O(2^n),21+1/n=O(1),logn^3=O(logn),10log3^n=O(n).习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n^2,logn,3^n,20n,2,n^2/3。

解答：照渐进阶从高到低的顺序为：n!、3^n、4n^2 、20n、n^2/3、logn、2习题2-4(1)假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。

在某台计算机上实现并完成该算法的时间为t秒。

现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？(2)若上述算法的计算时间改进为T(n)=n^2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？(3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答：(1)设能解输入规模为n1的问题，则t=3*2^n=3*2^n/64,解得n1=n+6(2)n1^2=64n^2得到n1=8n(3)由于T（n)=常数，因此算法可解任意规模的问题。

习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。

对于计算复杂性分别为n，n^2，n^3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？解答：n'=100nn'^2=100n^2得到n'=10nn'^3=100n^3得到n'=4.64nn'!=100n!得到n'<n+log100=n+6.64习题2-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ（g(n)），并简述理由。

算法设计与分析课程设计教学大纲课程代码：10115102 课程名称：算法设计与分析课程设计学时：1周学分：1学分适应专业：；软件工程(本科)执笔人：银星编写日期：2007年8月一、课程设计的教学目的和任务通过本课程设计教学所要达到的目的是：培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用；通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

本课程设计的任务是：学生应该根据所选题目完成方案设计、程序设计和调试等任务，并完成相关文档的撰写。

二、课程设计的内容和基本要求利用《算法设计与分析》课程中所学到的编程知识和编程技巧，完成具有一定难度和工作量的程序设计题目，帮助学生掌握编程、调试的基本技能，独立完成所布置的任务。

课程设计的题目可由指导教师根据具体情况和大刚的要求来确定，参考题目：题目一,棋牌游戏设计五子棋;象棋;围棋;军棋;跳棋;24点;斗地主等,要求:包涵部分格局;设计游戏的核心算法;可视化的软件设计;参考的知识:回溯法;程序语言不限;题目二,地图着色问题(限1 人完成)设计要求:已知中国地图,对各省进行着色,要求相邻省所使用的颜色不同,并保证使用的颜色总数最少.题目三,校园导航问题(限1 人完成)设计要求:设计你的学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径).题目四,学校超市选址问题(带权有向图的中心点)(限1 人完成) 设计要求:对于某一学校超市,其他各单位到其的距离不同,同时各单位人员去超市的频度也不同.请为超市选址,要求实现总体最优.题目五,走迷宫游戏(限1 人完成)程序开始运行时显示一个迷宫地图,迷宫中央有一只老鼠,迷宫的右下方有一个粮仓.游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处.要求:老鼠形象可辨认,可用键盘操纵老鼠上下左右移动;迷宫的墙足够结实,老鼠不能穿墙而过;正确检测结果,若老鼠在规定时间内走到粮仓处,提示成功,否则提示失败;添加编辑迷宫功能,可修改当前迷宫,修改内容:墙变路,路变墙;找出走出迷宫的所有路径,以及最短路径。

计算机算法设计与分析第1章王晓东(第三版)第4章第4章贪心算法学习要点理解贪心算法的概念。

掌握贪心算法的基本要素(1)最优子结构性质(2)贪心选择性质理解贪心算法与动态规划算法的差异理解贪心算法的一般理论通过应用范例学习贪心设计策略。

(1)活动安排问题；(2)最优装载问题；(3)哈夫曼编码；(4)单源最短路径；(5)最小生成树；(6)多机调度问题。

顾名思义，贪心算法总是作出在当前看来最好的选择。

也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

当然，希望贪心算法得到的最终结果也是整体最优的。

虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。

如单源最短路经问题，最小生成树问题等。

在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

4.1活动安排问题活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。

该问题要求高效地安排一系列争用某一公共资源的活动。

贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。

4.1活动安排问题设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。

每个活动i都有一个要求使用该资源的起始时间i和一个结束时间fi,且i<fi如果选择了活动i,则它在半开时间区间[i,fi)内占用资源。

若区间[i,fi)与区间[j,fj)不相交，则称活动i与活动j是相容的。

也就是说，当i≥fj或j≥fi时，活动i与活动j相容。

4.1活动安排问题下面给出解活动安排问题的贪心算法GreedySelector:template<claType>voidGreedySelector(intn,Type[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i<=n;i++){if([i]>=f[j]){A[i]=true;j=i;}eleA[i]=fale;}}各活动的起始时间和结束时间存储于数组和f中且按结束时间的非减序排列4.1活动安排问题由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。