《算法设计综合实训》题目讲解

一、实验目的1. 理解和掌握最优路径搜索算法的基本原理和实现方法。

2. 能够根据实际问题选择合适的算法，并对其进行优化和改进。

3. 提高算法分析和设计能力，以及编程实现能力。

二、实验内容本次实验要求设计并实现一种最优路径搜索算法，以解决迷宫问题。

迷宫由二维数组表示，其中1表示障碍，0表示通路。

要求算法能够从入口位置出发，找到到达出口的最短路径。

三、实验原理1. Dijkstra算法：Dijkstra算法是一种基于贪心策略的最短路径算法，适用于图中所有边的权重都为非负值的情况。

算法的基本思想是从起点出发，逐步扩展到相邻节点，计算到达每个节点的最短路径长度，并记录下到达该节点的最短路径。

2. A搜索算法：A搜索算法是一种启发式搜索算法，结合了Dijkstra算法和最佳优先搜索算法的优点。

算法的基本思想是在Dijkstra算法的基础上，引入启发函数来估计从当前节点到目标节点的距离，从而优先搜索那些更有可能到达目标节点的路径。

四、实验过程1. 算法设计（1）Dijkstra算法实现：1）初始化：设置一个距离数组dist[]，用于存储从起点到各个节点的最短路径长度，初始时将起点到自身的距离设为0，其余节点设为无穷大。

2）更新距离：从距离数组中选取距离最小的节点，将其标记为已访问，并将该节点到其相邻节点的距离进行更新。

3）重复步骤2），直到找到目标节点或所有节点都已访问。

（2）A搜索算法实现：1）初始化：设置一个开放列表openList和封闭列表closedList，分别用于存储待搜索节点和已搜索节点。

将起点加入openList，并设置其f值（g值+启发函数值）。

2）搜索过程：从openList中选取f值最小的节点，将其标记为当前节点，并将其加入closedList。

3）更新相邻节点：对于当前节点的相邻节点，计算其g值、h值和f值，如果相邻节点不在closedList中，且其f值小于openList中对应节点的f值，则将其加入openList。

实验5、《算法综合实验》一、实验目的1. 理解和复习所学各种算法的概念2. 掌握和复习所学各种算法的基本要素3. 掌握各种算法的优点和区别4. 通过应用范例掌握选择最佳算法的设计技巧与策略二、实验内容1. 使用贪心算法、回溯法、分支限界法解决0-1背包问题；2. 通过上机实验进行算法实现；3. 保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。

三、算法思想分析1.贪心算法理论上只能解决满足贪心选择性质的问题，而0-1背包并不满足该性质，所以并不能保证能够找到最优解法，只能找到最接近的解，当然如果运气好，也是可以找到最优解的。

利用按重量从小到大、按价值从大到小、按价值/重量从大到小三种方式通过贪心算法求得每种方式的最终结果，并比较三种方式的最大价值取最大的那个，即为贪心算法获得的最优解。

2.回溯法解决0-1背包问题的解空间为子集树，利用回溯法的基本代码模版即可，其中左子树为约束条件，即背包能否装下该物品，右子树为限界条件，即当前物品不放入背包，剩余物品是否有可能创造比当前最大价值更大的价值，如果可以则进入右子树，反之，则直接剪去右子树。

3.0-1背包的解空间为子集树，分支界限法是采用广度优先搜索，每次选取队列的最前面的结点为活结点。

1）算法从根结点A即标记结点开始，初始时活结点队列为空，A入队列。

2）A为活结点，A的儿子结点B、C为可行结点。

将B、C加入队列，舍弃A。

此时队列元素为C-B；3）B为活结点，B的儿子结点D、E,而D为不可行结点。

将E入队列，舍弃B。

此时队列元素为E-C；4)循环以上步骤按照以上方式扩展到叶节点。

四、实验过程分析1.贪心算法的思路很简单即为一直循环下去，直至不满足指定条件。

用于解决0-1背包问题时需要考虑多种放入方式，因为不管哪种方式都不能百分百会得到最优解，只能取多种放入方式中的最优解作为问题的最优解。

这道题目的收获在于贪心算法对于不能保证获得最优解的情况下，如何获得最接近的解，比如0-1背包问题则是采用多种放入方式再进行比较取最优解。

《算法设计综合实验》教案（5篇）第一篇：《算法设计综合实验》教案《算法设计综合实验》教案统计与应用数学学院2012年5月11日制实验一数据类型、运算符和表达式实验目的：1、掌握C语言数据类型，熟悉如何定义一个整型、字符型和实型的变量，以及对它们赋值的方法；2、掌握不同的数据类型之间赋值的规律；3、学会使用C的有关算术运算符，以及包含这些运算符的表达式，特别是自加和自减运算符的使用；4、学会使用赋值运算符及复合赋值运算符；5、进一步熟悉C程序的编辑、编译、连接和运行的过程。

实验环境：Windows操作系统、Visual C++6.0实验学时：2学时；实验内容：1、整型变量实型变量、字符型变量的定义与输出，赋整型常量值时的情形，以及给整型变量赋字符常量值时的情形；2、各类数值型数据间的混合运算；3、要将“China”译成密码，密码规律是：用原来的字母后面第4各字母代替原来的字母。

例如，字母“A”后面第4个字母是“E”，用“E”代替“A”。

因此，“China”应译成“Glmre”。

请编一程序，用赋初值的方法使c1、c2、c3、c4、c5这5个变量的值分别为’C’、’h’、’i’、’n’、’a’，经过运算，使c1、c2、c3、c4、c5分别变为’G’、’l’、’m’、’r’、’e’，并输出。

实验二顺序结构程序设计实验目的：1、掌握C语言中赋值语句的使用方法；2、掌握各种类型数据的输入输出方法，能正确使用各种格式转换符；3、学习调试程序。

实验环境： Windows操作系统、Visual C++6.0 实验学时：2学时；实验内容：1、掌握各种格式转换符的正确使用方法；2、设圆半径r=1.5，圆柱高h=3，求圆周长、圆面积、圆球表面积、圆球体积、圆柱体积。

用scanf输入数据，输出计算结果。

输出时要有文字说明，取小数点后两位数字。

3、编程序：用getchar函数读入两个字符给c1、c2，然后分别用putchar函数和printf函数输出这两个字符。

《算法设计综合实训》指导书一、实训目的依据人才培养方案的要求及教学计划的安排，在《数据结构》课程后安排这次课程实训，通过这次实训可达到以下目的：（1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。

（2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。

（3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。

（4）激发学生的学习兴趣。

（5）提高学生的计算思维能力，具备一定的算法分析与设计的能力。

二、实训内容1、根据设计的需求，能阅读和理解；2、根据功能的需求，使用所学知识转化成计算机管理；三、实训进度内容安排序号实训内容计划学时（天）教学要求教法建议1 选题与搜集资料 1 学生听老师讲授，并能理解一些细节通过讲解让学生简单了解系统的需求2 分析与概要设计3 根据搜集的资料，进行程序功能与数据结构分析，并选择合适的数据结构、并在此基础上进行实现程序功能的算法设计3 程序设计 5 运用掌握C/C++/Java语言编写程序，实现所编程序的各个模块功能。

调试程序，并记录测试情况。

符合代码编写规范。

辅导，出现问题多可以统一解答4答辩1提交设计报告、成果、成果演示、答辩教学主任教研室主任课程负责人合计10四、基本要求（一）设计要求（1）所有学生统一在机房进行设计；（2）听从指导老师的统一安排；（3）严格遵守作息时间、不迟到、不早退，病、事假必须向指导老师请假；（4）使用C/C++/JA V A进行开发；（5）满足编程规范；（6）设计结构清晰（模块化开发）。

（7) 根据任务书的要求选择设计题目，针对线性表、栈、队列与递归、字符串算法设计至少选作2个题目，树、图至少选作1个题目，查找与排序至少选作1个题目。

根据题目难易程度进行综合评分。

（8）抄袭他人程序者记零分。

（二）报告要求（1）问题描述：描述要求编程解决的问题。

算法设计与分析常见习题及详解⽆论在以后找⼯作还是⾯试中，都离不开算法设计与分析。

本博⽂总结了相关算法设计的题⽬，旨在帮助加深对贪⼼算法、动态规划、回溯等算法的理解。

1、计算下述算法执⾏的加法次数：输⼊：n =2^t //t 为整数输出：加法次数 k K =0while n >=1 do for j =1 to n do k := k +1 n = n /2return k解析：第⼀次循环执⾏n次加法，第⼆次循环执⾏1/2次加法，第三次循环执⾏1/次加法…因此，上述算法执⾏加法的次数为==2n-12、考虑下⾯每对函数 f(n) 和 g(n) ，如果它们的阶相等则使⽤Θ记号，否则使⽤ O 记号表⽰它们的关系解析：前导知识：，因为解析：，因为解析:，因为解析：解析:3、在表1.1中填⼊ true 或 false解析：利⽤上题的前导知识就可以得出。

2=21/4n +n +21n +41...+1n +n −n +21n −21n +41....−1f (n )=(n −2n )/2，g (n )=6n1<logn <n <nlogn <n <2n <32<n n !<n ng (n )=O (f (n ))f (n )=Θ(n ),g (n )=2Θ(n )f (n )=n +2,g (n )=n n 2f (n )=O (g (n ))f (n )=Θ(n ),g (n )=Θ(n )2f (n )=n +nlogn ,g (n )=n nf (n )=O (g (n ))f (n )=Θ(nlogn ),g (n )=Θ(n )23f (n )=2(log ),g (n )=n 2logn +1g (n )=O (f (n ))f (n )=log (n !),g (n )=n 1.05f (n )=O (g (n ))4、对于下⾯每个函数 f(n),⽤f(n) =Θ(g(n))的形式，其中g(n)要尽可能简洁，然后按阶递增序排列它们（最后⼀列）解析：最后⼀个⽤到了调和公式：按阶递增的顺序排列：、、、、、、、、、(n −2)!=Θ((n −2)!)5log (n +100)=10Θ(logn )2=2n Θ(4)n 0.001n +43n +31=Θ(n )4(lnn )=2Θ(ln n )2+3n logn =Θ()3n 3=n Θ(3)n log (n !)=Θ(nlogn )log (n )=n +1Θ(nlogn )1++21....+=n1Θ(logn )=∑k =1nk 1logn +O (1)1++21....+n 15log (n +100)10(lnn )2+3n logn log (n !)log (n )n +10.001n +43n +313n 22n (n −2)!5、求解递推⽅程前导知识：主定理前导知识：递归树：例⼦：递归树是⼀棵节点带权的⼆叉树，初始递归树只有⼀个结点，标记为权重W(n)，然后不断进⾏迭代，最后直到树种不再含有权为函数的结点为⽌，然后将树根结点到树叶节点的全部权值加起来，即为算法的复杂度。

《算法设计》中一道探究题的解析崇明中学陈超一、题目提出一次听课时，授课教师用“小明有只密码锁的拉竿箱，忘记了密码，密码锁是四位数字，只记得这个四位数前三位为均为1。

请问你能帮他解决这个问题吗？”作为枚举算法引入的实例，由于该实例来自于学生身边，在师生的共同分析研究下，学生较快地理解与掌握了枚举算法。

对该实例进行探究后，得到了以下多种算法。

二、算法递进1、枚举法（当时授课教师提供，略作改变）结构特点：循环结构嵌套分支结构。

算法分析：循环结构用于一一列举；分支结构用于逐一检验，并输出密码值。

Dim key As Integer, i As IntegerRandomizeKey = Int(10 * Rnd())i = 0Do While i <= 9If i = Key ThenPrint 1110 + KeyEnd Ifi = i + 1Loop2、改进版枚举法，消除冗余循环结构特点：1、循环结构嵌套分支结构；2、循环结构中设置退出出口。

算法分析：密码值具有唯一性，所以找到密码后即可输出结果，并退出循环结构。

（1）、重置循环变量的值，使循环的条件不成立，从而实现退出循环结构。

VB 代码如下：Dim key As Integer, i As Integer RandomizeKey = Int(10 * Rnd()) i = 0Do While i <= 9 If i = Key Then Print 1110 + Key i = 9 End If i = i + 1 Loop（2）、强制退出循环结构。

VB 代码如下：Dim key As Integer, i As Integer RandomizeKey = Int(10 * Rnd()) i = 0Do While i <= 9If i = Key Then Print 1110 + KeyExit Do End If i = i + 1Loop3、改变循环条件的设置 结构特点：单循环结构。

『嗨威说』算法设计与分析-PTA程序存储问题删数问题最优合并问题（第四章上机实践报告）本⽂索引⽬录：⼀、PTA实验报告题1 ：程序存储问题 1.1 实践题⽬ 1.2 问题描述 1.3 算法描述 1.4 算法时间及空间复杂度分析⼆、PTA实验报告题2 ：删数问题 2.1 实践题⽬ 2.2 问题描述 2.3 算法描述 2.4 算法时间及空间复杂度分析三、PTA实验报告题3 ：最优合并问题 3.1 实践题⽬ 3.2 问题描述 3.3 算法描述 3.4 算法时间及空间复杂度分析四、实验⼼得体会（实践收获及疑惑）⼀、PTA实验报告题1 ：程序存储问题 1.1 实践题⽬： 1.2 问题描述： 题意是，题⼲给定磁盘总容量和各个⽂件的占⽤空间，询问该磁盘最多能装⼏个⽂件。

1.3 算法描述： 签到题，只需要将各个⽂件从⼩到⼤排序，并拿⼀个变量存储已占⽤的容量总和，进⾏对⽐即可得到结果。

#include<bits/stdc++.h>#include<algorithm>using namespace std;#define MAXLENGTH 1000int interger[MAXLENGTH];int main(){int num,length;int sum = 0;int counter = 0;int m = 0;cin>>num>>length;for(int i=0;i<num;i++){cin>>interger[i];}sort(interger,interger+num);while(true){if(sum+interger[m]>length||counter==num)break;sum+=interger[m];counter++;m++;}cout<<counter<<endl;return0;} 1.4 算法时间及空间复杂度分析： 整体算法上看，输⼊需要O（n）的时间进⾏输⼊，最快⽤O（nlogn）的时间复杂度进⾏排序，使⽤O（n）的时间进⾏结果叠加，总时间复杂度为O（nlogn），时间复杂度花费在排序上。

《算法设计综合实验》教案统计与应用数学学院2012年5月11日制实验一数据类型、运算符和表达式实验目的：1、掌握C语言数据类型，熟悉如何定义一个整型、字符型和实型的变量，以及对它们赋值的方法；2、掌握不同的数据类型之间赋值的规律；3、学会使用C的有关算术运算符，以及包含这些运算符的表达式，特别是自加和自减运算符的使用；4、学会使用赋值运算符及复合赋值运算符；5、进一步熟悉C程序的编辑、编译、连接和运行的过程。

实验环境：Windows操作系统、Visual C++6.0实验学时：2学时；实验内容：1、整型变量实型变量、字符型变量的定义与输出，赋整型常量值时的情形，以及给整型变量赋字符常量值时的情形；2、各类数值型数据间的混合运算；3、要将“China”译成密码，密码规律是：用原来的字母后面第4各字母代替原来的字母。

例如，字母“A”后面第4个字母是“E”，用“E”代替“A”。

因此，“China”应译成“Glmre”。

请编一程序，用赋初值的方法使c1、c2、c3、c4、c5这5个变量的值分别为’C’、’h’、’i’、’n’、’a’，经过运算，使c1、c2、c3、c4、c5分别变为’G’、’l’、’m’、’r’、’e’，并输出。

实验二顺序结构程序设计实验目的：1、掌握C语言中赋值语句的使用方法；2、掌握各种类型数据的输入输出方法，能正确使用各种格式转换符；3、学习调试程序。

实验环境：Windows 操作系统、Visual C++6.0实验学时：2学时；实验内容：1、掌握各种格式转换符的正确使用方法；2、设圆半径r=1.5，圆柱高h=3，求圆周长、圆面积、圆球表面积、圆球体积、圆柱体积。

用scanf 输入数据，输出计算结果。

输出时要有文字说明，取小数点后两位数字。

3、编程序：用getchar 函数读入两个字符给c1、c2，然后分别用putchar 函数和printf 函数输出这两个字符。

上机运行程序，比较用printf 和putchar 函数输出字符的特点。

算法设计技术与方法大作业学院电子工程学院专业电路与系统姓名学号导师姓名1.分别实现多项式求值的四种运算，若针对不同规模的输入值a ，各算法的运行时间，问题 规模n 分别取10，50，100，150，200，300，400，500，10000，20000，50000，100000时绘制四种算法运行时间的比较图。

2.分别实现矩阵相乘的3种算法，比较三种算法在矩阵大小分别为2222⨯，3322⨯，4422⨯，5522⨯，6622⨯，7722⨯，8822⨯，9922⨯，101022⨯，111122⨯，121222⨯时的运行时间与MATLAB 自带的矩阵相乘的运行时间，绘制时间对比图。

3.利用遗传算法求解下面的问题：)20sin()4sin(5.21),(max 221121x x x x x x f ππ⋅+⋅+=⎩⎨⎧≤≤≤≤-8.51.41.120.3..21x x t s1、分析题意可知，该题要用四种不同的方法实现对多项式的求值计算，每种方法取从10-100000不同的规模。

本文采用了以下方法进行求值：直接代入法和递归法。

而其中递归法分三类不同思路进行递归：① n n n n x a x P x P +=-)()(1；② 0a P =,1=Q ,Q a P P Qx Q i +==,；③ i n i i a x x P x P --+'=')()(1。

本文对上述四种方法进行了编程，具体代码如下：程序1.1文件名poly.m% 主程序：实现不同规模下多项式求值的四种运算clc;close all ;clear all ;n=[10 50 100 150 200 300 400 500 10000 20000 50000 100000];x=2;for i=1:12a=rand(1,(n(i)+1)); % 产生多项式,最高次幂为n(i)+1tic;p1(i)=polyval(a,x); % 直接代入法t1(i)=toc;tic;p2(i)=0;for j=1:(n(i)+1)p2(i)=p2(i)+a(j)*x^(j-1); % 递归法1t2(i)=toc;tic;p3(i)=0;q=1;for j=2:(n(i)+1)q=q*x;p3(i)=p3(i)+a(j)*q; % 递归法2endt3(i)=toc;tic;p4(i)=0;for j=1:n(i);p4(i)=x*p4(i)+a(n(i)+1-j); % 递归法3endt4(i)=toc;endfigure(1);subplot(2,2,1);h=semilogx(n,t1); % 这里不能用plot，横轴需要取对数，下同set(h,'linestyle','-','linewidth',1.8,'marker','*','color','g','markersize',6); xlabel('The scale of the problem:n');ylabel('time for first method(s)');title('the relationship between time and scale');grid on;subplot(2,2,2);h=semilogx(n,t2);set(h,'linestyle','-','linewidth',1.8,'marker','*','color','b','markersize',6); xlabel('The scale of the problem:n');ylabel('time for second method(s)');title('the relationship between time and scale');grid on;subplot(2,2,3);h=semilogx(n,t2);set(h,'linestyle','-','linewidth',1.8,'marker','*','color','k','markersize',6); xlabel('The scale of the problem:n');ylabel('time for third method(s)');title('the relationship between time and scale');grid on;subplot(2,2,4);h=semilogx(n,t2);set(h,'linestyle','-','linewidth',1.8,'marker','*','color','r','markersize',6); xlabel('The scale of the problem:n');ylabel('time for forth method(s)');title('the relationship between time and scale');grid on;figure(2);g=semilogx(n,t1,'g+',n,t2,'bx',n,t3,'k*',n,t4,'ro');legend('the first method','the second method','the third method','the forth method'); set(g,'linestyle','-','linewidth',2.0,'markersize',8);xlabel('n=10, 50, 100, 150, 200, 300, 400, 500, 10000, 20000, 50000, 100000'); ylabel('time');title('The comparison chart of four different methods for polyval');grid on;运行结果如下：图 1.1 四种方法所用时间随规模不同而变化的结果图图 2.2 四种方法所用时间随规模不同而变化的对比图由理论分析可知，四种算法的时间复杂度分别为)(2n O 、)(2n O 、)(n O 、)(n O ，由图1.2分析可知，直接带入计算和递归法所用时间相差无几，这与理论分析一直。

实验五程序设计常用算法5.1实验要求与目的1．熟悉和掌握算法以及算法的特性2．熟练掌握结构化程序设计的三种基本结构3. 掌握常用的数值算法（求最大公约数，迭代法、牛顿迭代法和二分法等）4. 培养解决实际问题的能力5.2实验指导算法（Algorithm）是计算机解题的基本思想方法和步骤，算法被称为程序设计的灵魂，也是学习编程的必备知识。

学习和掌握算法，必须要十分清楚，输入什么数据，输出什么结果，采用什么结构以及如何合理安排语句等。

通常使用自然语言、结构化流程图、伪代码等来描述算法。

利用计算机解决问题，首先要设计出适合计算机执行的算法，此算法包含的步骤必须是有限的，每一步都必须是明确的，最终能被计算机执行，而得到结果。

算法可分为两类：1.数值运算算法。

对问题求数值解，通过运算得出一个具体值，如求方程的根等，此类算法一般有现成的模型，算法较成熟。

2.非数值运算算法。

如用于事务管理领域，图书检索等。

根据实际问题设计算法时，还要尽量考虑用重复的步骤去实现，使算法简明扼要，通用性强，不仅能减少编写程序的时间，减少上机输入和调试程序的时间，还能减少程序本身所占用的内存空间。

算法应具有以下的特性：1.有穷性：一个算法应包含有限的操作步骤而不能是无限的。

2.确定性：算法中每一个步骤应当是确定的，而不能具有二义性。

3.有零个或多个输入：通常，处理的数据对象需要从外界通过输入来获得数据。

4.有一个或多个输出：算法的目的就是得到结果，将其结果输出。

没有输出的算法是无意义的。

5.有效性：算法中每一个步骤应当能有效地执行，并得到确定的结果。

【5.1】编程实现，求两个正整数的最大公约数和最小公倍数。

程序文件名ex5_1.c。

分析：利用欧几里德辗转相除法求最大公约数。

算法思想，假定两个整数m,n（m>n），用较小的数n（除数）除较大的数m（被除数），得到余数r1；若余数r1不为零，则除数作为被除数，余数r1作为除数，相除得到余数r2；若余数r2还不为零，仍是将除数作为被除数，余数r2作为除数，相除得到余数r3，这样辗转相除，直到余数是零为止。

101i 的个数仓储问题作业二1.x i ＝0,1是货柜i 的个数，仓储问题：max nx l 1∑∑=n ii i 令C [k ,y ]是只允许装前k 个货柜，库房长度为y 时的最大收益1,0,1=≤=i i i ix L x l 1],1[],[k L l y y k C y k C k ⎨⎧>−−−<−=1],1[}],1[],,1[max{l y C l y l l y k C y k C kk k =⎩≥≥+1伪码略.W (n )=O (nD )33. 作业调度与01背包问题类似使用动态规划方法0-1背包问题类似，使用动态规划方法. 令N j (d )表示对作业集{1,2,…,j }，结束时间为d 的最优调度的效益那么效益，那么)(}))((),(max{)(11≥+−=−−j t d v j t d N d N d N j j j j 1)()()(1⎧≤<=−dt v j t d d N d N j j 0)1(0)()(11>⎩⎨>=d d t d N 自底向上计算，存储使用备忘录。

可以使用标记函数B (j )记录使得N j (d )达到最大是否N j (d )=N j −1(d ). 如果不等，B (j )=1，0.3否则为0.时间W (n )=O (nD )输入：加工时间伪码Job(t ,v ,D )t [1..n ]，效益v [1..n ]，结束时间D 输出：最优效益N [n,D ],标记函数B ，解是{k | B [k ]=1}1.for 1to −1. for d ←1 to t [1]12. N [1,d ]←0, B [1] ←03. for d ←t [1] to D4. N [1,d ]←v [1], B [1]←15. for k ←2 to n6for 1to 6. for d ←1 to D7. N [k ,d ]←N [k −1,d ]8.8. B [k ]←09. if d ≥t [k ] and N [k −1,d −t [k ]]+v [k ]>N [k −1,d ]10. then N [k ,d ]←N [k −1,d −t [k ]]+v [k ]411. B [k ]←14014. 双约束0-1背包问题种物品背包重量限制为m [i ,j ,k ]表示使用前i 种物品，背包重量限制为j ,容积为k 时的最大价值+−−−−=}],,1[],,,1[max{],,[v c k w j i m k j i m k j i m i i i <<−=≥≥or ],,1[],,[and c k w k i m k i m c k w j i i⎨⎧≥≥=111and ],,1[c k w j v k j m j j j i i ⎩<<11or 0c k w j 5W (n )= O (nWV )55.合并数组问题0n-1i j k k+110i jn -16递推公式X {合并问题含有整数个数⎧={x 0,x 1,…, x n －1}，X ij 表示{x i ,…,x j }合并问题，含有整数个数是n ij ，完成这些合并所需要最少的比较次数记作m [i ,j ]⎪⎪<+++∑=<≤j i a j k m k i m j i l l j k i ]},1[],[{max ⎪⎪⎨>++++=∑∑=−=−≤≤j i a a j n k m k i m j i m j l n l n k i 11]},mod )1[(],[{max ],[⎩<≤l i l jk 00m [i,i ]= 0i=0,2,…,n -1]}mod )1(,[{max 10n n i i m m n i −+=−≤≤7T (n )=O (n 3)标记函数s [i ,j ]记录使m [i ,j ] 取得最小值的k。

第6章课后作业结题报告第一题：给定n种物品和一个背包，物品i(1≤i≤n)的重量是wi，其价值为vi，背包的容量为C，对每种物品只有两种选择：装入背包或者不装入背包。

如何选择装入背包的物品，使得装入背包中物品的总价值最大？这是一道老生常谈的背包问题，属于入门dp（Dynamic Programming动态规划）, 首先给出状态转移方程，设dp[i][j]表示用大小为j的背包去装前i个所能获得的最大价值, w[i]表示第i个物品的体积，v[i]表示第i个物品的价值。

关于第i个物品的决策，就是间单的”取与不取”，我们很容易得到如下的状态转移方程:dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);这边dp[i-1][j]表示第i个物品不取，dp[i-1][j-w[i]]+v[i]表示第i个物品取因为每次推导只用的到i-1维，我们其实可以只用一维的滚动数组就可以来求解。

这时候要逆序求解，这边不多做介绍接下来是打印路径问题，这个需要逆序贪心打印。

第i个背包是否选取应该用dp[i][V]与dp[i-1][V]来比较，从而求解，dp[i][V]>dp[i-1][V]，V表示当前可存在的最大容量。

根据贪心，容量V越大价值同样装前i个一定更优，后面的推导的正解一定是基于dp[i][V]的，所以可以这么选标程如下：#include <stdio.h>#include <algorithm>using namespace std;int dp[110][1010];int n, c, ans[110];int w[110], v[110];void print(){int i, j, k;k=c;for(i=n; i>=1; i--){if(dp[i][k]!=dp[i-1][k]){ans[i]=1;k=k-w[i];}else{}}return;}int main(){int i, j, k;scanf("%d%d", &n, &c);for(i=1; i<=n; i++){scanf("%d%d", &w[i], &v[i]);}for(i=1; i<=n; i++){for(j=1; j<=c; j++){dp[i][j]=dp[i-1][j];if(j>=w[i]){dp[i][j]=max(dp[i-1][j-w[i]]+v[i], dp[i][j]);}}}printf("%d\n", dp[n][c]);print();for(i=1; i<=n; i++) {printf("%d\n", ans[i]);}return 0;}第二题：设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。

《算法设计与分析实用教程》习题参考解答《算法设计与分析实用教程》参考解答1-1 加减得1的数学游戏西西很喜欢数字游戏，今天他看到两个数，就想能否通过简单的加减，使最终答案等于1。

而他又比较厌烦计算，所以他还想知道最少经过多少次才能得到1。

例如，给出16,9：16-9+16-9+16-9-9-9+16-9-9=1，需要做10次加减法计算。

设计算法，输入两个不同的正整数，输出得到1的最少计算次数。

（如果无法得到1，则输出-1）。

（1）若输入两个不同的正整数a,b均为偶数，显然不可能得到1。

设x*a与y*b之差为“1”或“-1”,则对于正整数a,b经n=x+y-1次加减可得到1。

为了求n的最小值，令n从1开始递增，x在1——n中取值，y=n+1-x：检测d=x*a+y*b，若d=1或-1，则n=x+y-1为所求的最少次数。

（2）算法描述// 两数若干次加减结果为1的数学游戏#includevoid main(){long a,b,d,n,x,y;printf(" 请输入整数a,b: ");scanf("%ld,%ld",&a,&b);if(a%2==0 && b%2==0){ printf(" -1\n");return;}n=0;while(1){ n++;for(x=1;x<=n;x++){ y=n+1-x;d=x*a-y*b;if(d==1 || d==-1) // 满足加减结果为1{ printf(" n=%ld\n",n);return;}}}}请输入整数a,b: 2012,19961请输入整数a,b: 101,20136061-2 埃及分数式算法描述分母为整数分子为“1”的分数称埃及分数，试把真分数a/b 分解为若干个分母不为b 的埃及分数之和。

（1）寻找并输出小于a/b 的最大埃及分数1/c ；（2）若c>900000000，则退出；（3）若c ≤900000000，把差a/b-1/c 整理为分数a/b ，若a/b 为埃及分数，则输出后结束。

算法设计与分析复习题目及答案一、算法的基本概念1、什么是算法？算法是指解决特定问题的一系列明确步骤，它具有确定性、可行性、有穷性、输入和输出等特性。

例如，计算两个数的最大公约数的欧几里得算法，就是通过反复用较小数去除较大数，然后将余数作为新的较小数，直到余数为 0，此时的除数就是最大公约数。

2、算法的复杂度包括哪些？它们的含义是什么？算法的复杂度主要包括时间复杂度和空间复杂度。

时间复杂度是指算法执行所需要的时间量，通常用大 O 记号来表示。

例如，一个算法的时间复杂度为 O(n)，表示其执行时间与输入规模 n成正比。

空间复杂度则是算法在运行过程中所需要的额外存储空间的大小。

比如说，一个算法需要创建一个大小为 n 的数组来存储数据，那么其空间复杂度就是 O(n)。

二、分治法1、分治法的基本思想是什么？分治法的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题相互独立且与原问题结构相同。

然后分别求解这些子问题，最后将子问题的解合并得到原问题的解。

2、请举例说明分治法的应用。

例如归并排序算法。

将一个未排序的数组分成两半，对每一半分别进行排序，然后将排好序的两部分合并起来。

其时间复杂度为 O(nlogn)，空间复杂度为 O(n)。

三、动态规划1、动态规划的基本步骤有哪些？动态规划的基本步骤包括：（1）定义问题的状态。

（2）找出状态转移方程。

（3）确定初始状态。

（4）计算最终的解。

2、解释最长公共子序列问题，并给出其动态规划解法。

最长公共子序列问题是指找出两个序列的最长公共子序列的长度。

假设我们有两个序列 X 和 Y，用 dpij 表示 X 的前 i 个字符和 Y 的前 j 个字符的最长公共子序列长度。

状态转移方程为：如果 Xi 1 ＝＝ Yj 1，则 dpij ＝ dpi 1j 1 ＋ 1否则 dpij ＝ max(dpi 1j, dpij 1)四、贪心算法1、贪心算法的特点是什么？贪心算法在每一步都做出当前看起来最优的选择，希望通过这种局部最优选择达到全局最优解。

算法设计与分析：期中试卷+实验题目文字解析期中试卷：算法设计与分析实验题目简单解析：P39-P43：2-1众数问题；2-7集合划分问题；2-10标准二维表问题；2-11整数因子分解问题P79-P80：3-1独立任务最有调度；3-2编辑距离问题；3-3石子合并问题；3-4数字三角形问题P109：4-2最优合并问题；4-4 磁盘文件最优存储问题P151-P152：5-1子集和问题；5-3最小重量机器设计问题2-1众数问题给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。

多重集S 中重数最大的元素称为众数。

例如，S={1，2，2，2，3，5}。

多重集S的众数是2，其重数为3。

数据输入输入包括多组数据，请处理到EOF结束。

每组数据，以一个n(1<=n<=100,000)开始，接下n 行，每行有一个数字(-231~231)。

数据输出对于每组输入数据，输出一行一个数字，表示众数。

如果存在多个解，只需输出值最小的众数即可。

算法思路：首先用快速排序算法排序数组，找到当前数组的中位数及其位置，然后把在数组中与中位数相同的数字向它靠拢，就可以统计中位数的个数。

现在数组已经被中间这些相等的数字分开了。

那么递归条件就有了。

如果中位数的个数比它左边这段短，那么说明左边有可能找到更多的，所以递归继续。

反之，如果左边这段数的长度比较短，那么就没必要继续递归。

对右边那段数据使用同样的策略。

2-7集合划分问题n个元素的集合{1,2,.,n }可以划分为若干个非空子集。

例如，当n=4 时，集合{1,2,3,4}可以划分为15个不同的非空子集如下：{1}，{2}，{3}，{4}}，{{1，2}，{3}，{4}}，{{1，3}，{2}，{4}}，{{1，4}，{2}，{3}}，{{2，3}，{1}，{4}}，{{2，4}，{1}，{3}}，{{3，4}，{1}，{2}}，{{1，2}，{3，4}}，{{1，3}，{2，4}}，{{1，4}，{2，3}}，{{1，2，3}，{4}}，{{1，2，4}，{3}}，{{1，3，4}，{2}}，{{2，3，4}，{1}}，{{1，2，3，4}}编程任务：给定正整数n 和m，计算出n 个元素的集合{1,2,., n }可以划分为多少个不同的由m 个非空子集组成的集合。

在线编程班学生算法设计训练【算法设计】算法设计专项练习背景算法设计是计算机科学中非常重要的一部分，它涉及解决问题和编写高效代码的能力。

为了提高在线编程班学生的算法设计技能，我们计划推出专项练课程。

目标本专项训练旨在帮助在线编程班学生提高他们的算法设计能力。

通过这个训练，学生将研究和掌握常见的算法设计技巧，并能够正确应用这些技巧来解决实际问题。

内容这个专项训练将包括以下内容：1. 算法基础知识：学生将研究算法的基本概念和常见的算法思想，例如贪心算法、动态规划等。

2. 算法设计技巧：学生将研究一些常见的算法设计技巧，例如分治法、回溯法等。

他们将了解这些技巧的原理，并通过实践练来掌握它们的应用。

3. 算法优化方法：学生将研究一些优化算法的方法，例如剪枝、动态规划优化等。

他们将学会如何通过优化算法来提高程序的效率。

4. 算法实战练：学生将参与一系列算法实战练，通过解决实际问题来巩固和应用所学的算法设计技巧。

训练形式本专项训练将以在线编程方式进行。

学生将通过在线研究平台获得讲义材料和练题，并通过编写代码来实践所学的算法设计技巧。

他们可以根据自己的研究进度自由选择合适的时间进行训练。

评估和认证学生完成训练后，将参加一次综合性的考试，评估他们在算法设计方面的掌握程度。

合格的学生将获得在线编程班算法设计专项训练的认证。

总结通过这个在线编程班学生算法设计训练，我们期望能够帮助学生提高他们的算法设计能力。

这将使他们在解决实际问题和编写高效代码时更加自信和熟练。

我们相信，通过不断练习和实践，学生们将成为优秀的算法设计师。

实验五程序设计常用算法5.1实验要求与目的1．熟悉和掌握算法以及算法的特性2．熟练掌握结构化程序设计的三种基本结构3. 掌握常用的数值算法（求最大公约数，迭代法、牛顿迭代法和二分法等）4. 培养解决实际问题的能力5.2实验指导算法（Algorithm）是计算机解题的基本思想方法和步骤，算法被称为程序设计的灵魂，也是学习编程的必备知识。

学习和掌握算法，必须要十分清楚，输入什么数据，输出什么结果，采用什么结构以及如何合理安排语句等。

通常使用自然语言、结构化流程图、伪代码等来描述算法。

利用计算机解决问题，首先要设计出适合计算机执行的算法，此算法包含的步骤必须是有限的，每一步都必须是明确的，最终能被计算机执行，而得到结果。

算法可分为两类：1.数值运算算法。

对问题求数值解，通过运算得出一个具体值，如求方程的根等，此类算法一般有现成的模型，算法较成熟。

2.非数值运算算法。

如用于事务管理领域，图书检索等。

根据实际问题设计算法时，还要尽量考虑用重复的步骤去实现，使算法简明扼要，通用性强，不仅能减少编写程序的时间，减少上机输入和调试程序的时间，还能减少程序本身所占用的内存空间。

算法应具有以下的特性：1.有穷性：一个算法应包含有限的操作步骤而不能是无限的。

2.确定性：算法中每一个步骤应当是确定的，而不能具有二义性。

3.有零个或多个输入：通常，处理的数据对象需要从外界通过输入来获得数据。

4.有一个或多个输出：算法的目的就是得到结果，将其结果输出。

没有输出的算法是无意义的。

5.有效性：算法中每一个步骤应当能有效地执行，并得到确定的结果。

【5.1】编程实现，求两个正整数的最大公约数和最小公倍数。

程序文件名ex5_1.c。

分析：利用欧几里德辗转相除法求最大公约数。

算法思想，假定两个整数m,n（m>n），用较小的数n（除数）除较大的数m（被除数），得到余数r1；若余数r1不为零，则除数作为被除数，余数r1作为除数，相除得到余数r2；若余数r2还不为零，仍是将除数作为被除数，余数r2作为除数，相除得到余数r3，这样辗转相除，直到余数是零为止。