下载文档原格式
第六章动态规划法• P137 2 ,3, 4•2.解答:cost[i]表示从顶点i 到终点n-1 的最短路径，path[i]表示从顶点i 到终点n-1 的路径上顶点i 的下一个顶点。
cost[i]=min{cij+cost[j]}3 有5 个物品，其重量分别是{3, 2, 1, 4,5}，价值分别为{25, 20, 15, 40, 50}，背包的容量为6。
V[i][j]表示把前i 个物品装入容量为j 的背包中获得的最大价值。
最优解为（0，0，1，0，1）最优值为65. 4.序列A =(x, z , y , z , z , y,x )，B =(z , x , y , y , z , x , z )，建立两个(m+1)×(n+1)的二 维表L 和表S ，分别存放搜索过程中得到的子序列的长度和状态。
z , x , y , y , z,x , z )path[i]= 使 cij+cost[j] 最小的 j i 012345678 9 10 11 12 13 14 15 Cost[i] 18 13 16 13 10 9 12 7 6875943Path[i]145778911 11 11 13 14 14 15 15 0得到最短路径 0->1->4->7->11->14->15 , 长度为 18(a)长度矩阵L(b)状态矩阵S 。
第七章贪心算法2.背包问题:有7 个物品，背包容量W=15。
将给定物品按单位重量价值从大到小排序，结果如下：个物品，物品重量存放在数组w[n]中，价值存放在数组放在数组x[n]中。
按算法7.6——背包问题1．改变数组w 和v 的排列顺序，使其按单位重量价值v[i]/w[i]降序排列；2．将数组x[n]初始化为0；//初始化解向量3．i=1;4．循环直到( w[i]>C )4.1 x[i]=1; //将第i个物品放入背包4.2 C=C-w[i];4.3 i++;5. x[i]=C/w[i];得出,该背包问题的求解过程为:: x[1]=1;c=15-1=14 v=6 x[2]=1; c=14-2=12V=6+10=10 x[3]=1; c=12-4=8V=16+18=34 x[4]=1; c=8-5=3V=34+15=49 x[5]=1; c=3-1=2 V=49+3=52x[6]=2/3 ; c=0; V=52+5*2/3=156/3 最优值为156/3 最优解为(1,1,1,1,1,2/3,0)) (x[i]按排序后物品的顺序构造)5.可以将该问题抽象为图的着色问题,活动抽象为顶点,不相容的活动用边相连(也可以将该问题理解为最大相容子集问题,重复查找剩余活动的最大相容子集,子集个数为所求).具体参见算法7.3 算法7.3——图着色问题1．color[1]=1; //顶点1着颜色12．for (i=2; i<=n; i++) //其他所有顶点置未着色状态color[i]=0;3．k=0;4．循环直到所有顶点均着色4.1k++; //取下一个颜色4.2for (i=2; i<=n; i++) //用颜色k 为尽量多的顶点着色4.2.1 若顶点i已着色，则转步骤4.2，考虑下一个顶点;4.2.2 若图中与顶点i邻接的顶点着色与顶点i着颜色k 不冲突，则color[i]=k;5．输出k;第八章回溯法4.搜索空间(a) 一个无向图(b) 回溯法搜索空间最优解为（1，2，1，2，3）5.0-1 背包问题n∑w i x i≤c 1• 可行性约束函数：i =1• 上界函数：nr =∑Vi5 = 3A B *CD8 ** * 131 =12 =23 = 14 = 2 34215课后答案网（）i=k+1 1第九章分支限界法5，解：应用贪心法求得近似解：(1,4,2,3)，其路径代价为：3+5+7+6=21，这可以作为该问题的上界。
4.1：在我们所了解的早期排序算法之中有一种叫做Maxsort 的算法。
它的工作流程如下：首先在未排序序列（初始时为整个序列）中选择其中最大的元素max ，然后将该元素同未排序序列中的最后一个元素交换。
这时，max 元素就包含在由每次的最大元素组成的已排序序列之中了，也就说这时的max 已经不在未排序序列之中了。
重复上述过程直到完成整个序列的排序。
(a) 写出Maxsort 算法。
其中待排序序列为E ，含有n 个元素，脚标为范围为0,,1n -K 。
void Maxsort(Element[] E) { int maxID = 0;for (int i=E.length; i>1; i--) { for (int j=0; j<i; j++) {if (E[j] > E[maxID]) maxID = k; E[i] <--> E[maxID];(b) 说明在最坏情况下和平均情况下上述算法的比较次数。
最坏情况同平均情况是相同的都是11(1)()2n i n n C n i -=-==∑。
4.2：在以下的几个练习中我们研究一种叫做“冒泡排序”的排序算法。
该算法通过连续几遍浏览序列实现。
排序策略是顺序比较相邻元素，如果这两个元素未排序则交换这两个元素的位置。
也就说，首先比较第一个元素和第二个元素，如果第一个元素大于第二个元素，这交换这两个元素的位置；然后比较第二个元素与第三个元素，按照需要交换两个元素的位置；以此类推。
(a)起泡排序的最坏情况为逆序输入，比较次数为11(1)()2n i n n C n i -=-==∑。
(b) 最好情况为已排序，需要(n-1)次比较。
4.3： (a)归纳法：当n=1时显然成立，当n=2时经过一次起泡后，也显然最大元素位于末尾；现假设当n=k-1是，命题也成立，则当n=k 时，对前k-1个元素经过一次起泡后，根据假设显然第k-1个元素是前k-1个元素中最大的，现在根据起泡定义它要同第k 个元素进行比较，当k 元素大于k-1元素时，它为k 个元素中最大的，命题成立；当k 元素小于k-1元素时，它要同k-1交换，这时处于队列末尾的显然时队列中最大的元素。
算法设计与分析智慧树知到课后章节答案2023年下山东交通学院山东交通学院第一章测试1.解决一个问题通常有多种方法。
若说一个算法“有效”是指( )A:这个算法能在一定的时间和空间资源限制内将问题解决B:这个算法能在人的反应时间内将问题解决C:这个算法比其他已知算法都更快地将问题解决D:（这个算法能在一定的时间和空间资源限制内将问题解决）和（这个算法比其他已知算法都更快地将问题解决）答案:（这个算法能在一定的时间和空间资源限制内将问题解决）和（这个算法比其他已知算法都更快地将问题解决）2.农夫带着狼、羊、白菜从河的左岸到河的右岸，农夫每次只能带一样东西过河，而且，没有农夫看管，狼会吃羊，羊会吃白菜。
请问农夫能不能过去？（）A:不一定B:不能过去 C:能过去答案:能过去3.下述（）不是是算法的描述方式。
A:自然语言 B:E-R图 C:程序设计语言 D:伪代码答案:E-R图4.有一个国家只有6元和7元两种纸币，如果你是央行行长，你会设置（）为自动取款机的取款最低限额。
A:40 B:29 C:30 D:42答案:305.算法是一系列解决问题的明确指令。
（）A:对 B:错答案:对6.程序=数据结构+算法（）A:对 B:错答案:对7.同一个问题可以用不同的算法解决，同一个算法也可以解决不同的问题。
（）A:错 B:对答案:对8.算法中的每一条指令不需有确切的含义，对于相同的输入不一定得到相同的输出。
( )A:错 B:对答案:错9.可以用同样的方法证明算法的正确性与错误性 ( )A:错 B:对答案:错10.求解2个数的最大公约数至少有3种方法。
( )A:对 B:错答案:错11.没有好的算法，就编不出好的程序。
（）A:对 B:错答案:对12.算法与程序没有关系。
( )A:错 B:对答案:错13.我将来不进行软件开发，所以学习算法没什么用。
( )A:错 B:对答案:错14.gcd(m,n)=gcd(n,m m od n)并不是对每一对正整数(m,n)都成立。
算法分析与设计教程习题解答第1章 算法引论1. 解：算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列计算方法。
频率计数是指计算机执行程序中的某一条语句的执行次数。
多项式时间算法是指可用多项式函数对某算法进行计算时间限界的算法。
指数时间算法是指某算法的计算时间只能使用指数函数限界的算法。
2. 解：算法分析的目的是使算法设计者知道为完成一项任务所设计的算法的优劣，进而促使人们想方设法地设计出一些效率更高效的算法，以便达到少花钱、多办事、办好事的经济效果。
3. 解：事前分析是指求出某个算法的一个时间限界函数（它是一些有关参数的函数）；事后测试指收集计算机对于某个算法的执行时间和占用空间的统计资料。
4. 解：评价一个算法应从事前分析和事后测试这两个阶段进行，事前分析主要应从时间复杂度和空间复杂度这两个维度进行分析；事后测试主要应对所评价的算法作时空性能分布图。
5. 解：①n=11； ②n=12； ③n=982； ④n=39。
第2章 递归算法与分治算法1． 解：递归算法是将归纳法的思想应用于算法设计之中，递归算法充分地利用了计算机系统内部机能，自动实现调用过程中对于相关且必要的信息的保存与恢复；分治算法是把一个问题划分为一个或多个子问题，每个子问题与原问题具有完全相同的解决思路，进而可以按照递归的思路进行求解。
2． 解：通过分治算法的一般设计步骤进行说明。
3． 解：int fibonacci(int n) {if(n<=1) return 1;return fibonacci(n-1)+fibonacci(n-2); }4. 解：void hanoi(int n,int a,int b,int c) {if(n>0) {hanoi(n-1,a,c,b); move(a,b);hanoi(n-1,c,b,a); } } 5. 解：①22*2)(−−=n n f n② )log *()(n n n f O =6． 解：算法略。
习题4.13(b)元素最大交换次数：A9~A5 各1次；A4~A3 各2次；A2最多3次；A1最多4次Þ最多共需16次元素交换4.13另解：考虑第i个节点，其子节点为2i，则最多可交换1次；若子节点有子节点22i, 则最多可交换2次；若…..有子节点i×2k, 则最多可交换k次；因此有i×2k≤ 19求出满足上述不等式的最大的k值即可。
i=1时, k=4;i=2时, k=3;i=3或4时, k=2;i=5~9时, k=1;因此最多交换4+3+2×2+1×5=16次6.5 用分治法求数组A[1…n]元素和，算法的工作空间是多少？输入：数组A[1…n]输出：数组的所有元素之和∑A[i] {i=1…n}SUM(low, high)1.if high = low then2. return A[low]3.else4.mid←ë(low+high)/2û5.s1←SUM(low,mid)6.s2←SUM(mid+1, high)7. return s1+s28.end if工作空间：mid~Q(logn), s1&s2~Q(1)（后序遍历树，不断释放空间，故为常数Q(1)），总的工作空间为Q(logn).6.6 用分治法求元素x在数组A中出现的频次。
freq(A[low, high], x)1.if high=low then2. if A[low]=x then3. return 14. else5. return 06. end if7.else8. mid ←ë(low+high)/2û9. f1 ←freq(A[low, mid])10. f2 ← freq(A[mid+1, high])11. return f1+f212.end if复杂度:T(n)=T(ën/2û)+ T(én/2ù)≈2T(n/2) (设2k≤n<2k+1) =…=2k T(n/2k) =2k T(1) = n6.16修改后的MERGESORT算法最大比较次数(1)/2()2(/2)1n n if n m T nT n n if n m-≤⎧=⎨+->⎩最小比较次数1()2(/2)/2n if n m C nC n n if n m-≤⎧=⎨+>⎩令n/2k=m≥2，展开可知：T(n)= 2k T(n/2k) + kn - (2k-1)= n/m×m(m-1)/2 + nlog(n/m)- n/m+1= n(m-1)/2 + nlog(n/m) -n/m+1若T(n)=Q(nlogn), 其中表达式有nm, nlogn, nlogm, n/m等.有n/m < nlogm < nm 且须有nm=O(nlogn), i.e., nm ≤c·nlogn,则须有m≤c·logn. 可令c=1,则m≤logn. 另一方面，C(n) = 2k C(n/2k)+kn/2 = n/m×(m-1) + (n/2)log(n/m)= Q(nlogn)6.35split(A[low,...high])1. x←A[low] //备份为x2. while (low<high){3. while (low<high && A[high]>0) --high;4. A[low] ←A[high]5. while (low<high && A[low]≤0) ++low;6.A[high] ←A[low]7.}8.A[low] ← x //这时, low=highC，并分析其时间复杂度。
算法设计技巧与分析课后答案吴永昶习题1-2 方法头签名方法签名由方法的名称和它的每一个形参（按从左到右的顺序）的类型和种类（值、引用或输出）组成。
需注意的是，方法签名既不包含返回类型，也不包含params 修饰符（它可用于最右边的参数）。
实例构造函数签名由它的每一个形参（按从左到右的顺序）的类型和种类（值、引用或输出）组成。
具体说来，实例构造函数的签名不包含可为最右边的参数指定的params 修饰符。
索引器签名由它的每一个形参（按从左到右的顺序）的类型组成。
具体说来，索引器的签名不包含元素类型。
运算符签名由运算符的名称和它的每一个形参（按从左到右的顺序）的类型组成。
具体说来，运算符的签名不包含结果类型。
签名是对类、结构和接口的成员实施重载的机制：方法重载允许类、结构或接口用同一个名称声明多个方法，条件是它们的签名在该类、结构或接口中是唯一的。
实例构造函数重载允许类或结构声明多个实例构造函数，条件是它们的签名在该类或结构中是唯一的。
索引器重载允许类、结构或接口声明多个索引器，条件是它们的签名在该类、结构或接口中是唯一的。
运算符重载允许类或结构用同一名称声明多个运算符，条件是它们的签名在该类或结构中是唯一的。
习题1-10 函数渐进阶大写O符号（上界，最坏）f(n)=O(g(n))，这里f(n)是分析出来算法的执行次数的函数，O的定义:当且仅当存在正的常数c和n0，使得对于所有的n>=n0，有f(n)<=cg(n)。
这里cg(n)就是函数f(n)的上限。
几种函数的例子:1.线性函数f(n)=3n+2，当n>=2时，3n+2<=3n+n=4n。
所以f(n)=O(n)，这里c 就是4，n0=2。
2.平方函数f(n)=2n^2+3n+3，当n>=3时，3n+3<=4n，当n>=4时，4n<n^2，f(n)=2n^2+n^2=3n^2。
f(n)=O(n^2)，这里c是3，n0=4。
