算法设计技巧与分析习题答案

算法设计技巧与分析参考答案第1章算法分析基本概念(a)6 (b)5 (c)6 (d)6算法执行了7+6+5+4+3+2+1=28次比较(a)算法MODSELECTIONSORT执行的元素赋值的最少次数是0,元素已按非降序排列的时候达到最小值。

(b) 算法MODSELECTIONSORT执行的元素赋值的最多次数是3(1)2n n ,元素已按非升序排列的时候达到最小值。

由上图可以看到执行的比较次数为1+1+2+2+2+6+2=16次。

由上图可以得出比较次数为5+6+6+9=26次。

FTF,TTT,FTF,TFF,FTF(a) 执行该算法，元素比较的最少次数是n-1。

元素已按非降序排列时候达到最小值。

(b) 执行该算法，元素比较的最多次数是(1)2n n -。

元素已按非升序排列时候达到最大值。

(c) 执行该算法，元素赋值的最少次数是0。

元素已按非降序排列时候达到最小值。

(d) 执行该算法，元素赋值的最多次数是3(1)2n n -。

元素已按非升序排列时候达到最大值。

(e)n 用O 符号和Ω符号表示算法BUBBLESORT 的运行时间：2()t O n =，()t n =Ω(f)不可以用Θ符号来表示算法的运行时间：Θ是用来表示算法的精确阶的，而本算法运行时间由线性到平方排列，因此不能用这一符号表示。

不能用p 关系来比较2n 和2100n 增长的阶。

∵221lim0100100n n n →∞=≠ 2n ∴不是2(100)o n 的，即不能用p 关系来比较2n 和2100n 增长的阶。

(a)当n 为2的幂时，第六步执行的最大次数是：12,2k k n j -==时，11[log ]log n ni i k n n n ====∑∑(b)由(a)可以得到：当每一次循环j 都为2的幂时，第六步执行的次数最大，则当33,22k kmn j ===（其中32k 取整）时，11[log(31)]log(1)n nkii i m n n ===-=-∑∑(c)用O 符号表示的算法的时间复杂性是(log )O n n 已证明n=2k 的情况，下面证明n=2k +1的情况：因为有⎥⎦⎥⎢⎣⎢+=⎥⎦⎥⎢⎣⎢21222k k所以n=2k +1时，第六步执行的最大次数仍是n log n 。

《算法与程序实践》习题解答7——枚举枚举是基于已有的知识进行答案猜测的一种问题求解策略。

在求解一个问题时，通常先建立一个数学模型，包括一组变量，以及这些变量需要满足的条件。

问题求解的目标就是确定这些变量的值。

根据问题的描述和相关的知识，能为这些变量分别确定一个大概的取值范围。

在这个范围内对变量依次取值，判断所取的值是否满足数学模型中的条件，直到找到（全部）符合条件的值为止。

这种解决问题的方法称作“枚举”。

例如“求小于N的最大素数”。

其数学模型是：一个整型变量n，满足：（1）n不能够被[2，n）中的任意一个素数整除；（2）n与N之间没有素数。

利用已有的知识，能确定n 的大概取值范围{2}{2*i+1|1<=i,2*i+1<N}。

在这个范围内从小到大依次取值，如果n不能够被[2，n）中的任意一个素数整除，则满足条件(1)。

在这个范围内找到的最后一个素数也一定满足条件(2)，即为问题的解。

枚举是用计算机求解问题最常用的方法之一，常用来解决那些通过公式推导、规则演绎的方法不能解决的问题。

而且，枚举也是现代科学研究和工程计算的重要手段，因为科学研究是在发现问题的规律之前解决问题，然后再寻找不同问题之间的共同规律。

在采用枚举的方法进行问题求解时，要注意3个方面的问题。

●建立简洁的数学模型。

数学模型中变量的数量要尽量少，它们之间相互独立。

这样问题解的搜索空间的维度就小。

反应到程序代码中，循环嵌套的层次少。

模型中的每个条件要反应问题的本质特征。

“求小于N 的最大素数”中的条件（1）是“n不能够被[2，n）中的任意一个素数整除”，而不是“n不能够被[2，n）中的任意一个整数整除”。

这个条件极大的降低了判断n是否是素数的计算开销。

●减小搜索的空间。

利用已有的知识缩小数学模型中各个变量的取值范围，避免不必要的计算。

反应到程序代码中，循环体被执行的次数就少。

除2 之外的其它素数都是奇数，因此“小于N 的最大素数”一定在集合{2，2*i+1|1<=i，2*i+1<N}中。

1.利用数组实现原始信息与处理结果的对应存储。

2.二维趣味矩阵的应用主对角线元素i=j；副对角线元素: 下标下界为1时i+j=n+1，下标下界为0时i+j=n-1；主上三角◥元素: i <=j；主下三角◣元素: i >=j；次上三角◤元素：下标下界为1时i +j<=n+1，下标下界为0时i+j<=n-1；次下三角◢元素：下标下界为1时i +j>=n+1，下标下界为0时i+j>=n-1；3.算法优化技巧中算术运算的妙用。

4.非数值问题的处理练习：警察局抓了a，b，c，d四名偷窃嫌疑犯，其中只有一人是小偷。

审问中的描述如下：a说：“我不是小偷。

”b说：“c是小偷。

”c 说：“小偷肯定是d 。

”d 说：“c 在冤枉人。

”现在已经知道四个人中三人说的是真话，一人说的是假话，问到底谁是小偷？提示：将以上信息数字化，用变量x 存放小偷的编号，则x 的取值范围从1取到4，就假设了他们中的某人是小偷的所有情况。

四个人所说的话就可以分别写成：a 说的话：x<>1b 说的话：x=3c 说的话：x=4d 说的话：x<>4或not(x=4)#include <stdio.h>int main(){ int x;for(x=1;x<=4;x++){if((x!=1)+(x==3)+(x==4)+(x!=4)==3)printf("%c is a thief. \n",x+64);}return 0;}运行结果：c is a thief .5. 数学模型的应用练习2：求n 次二项式各项的系数：已知二项式的展开式为：n n n n n n n n n n b C b a C b a C a C b a ++++=+-- 222110)(，要求利用杨辉三角形的规律来求解此问题。

各阶多项式的系数呈杨辉三角形的规律，因此可利用杨辉三角形的规律来编程实现。

计算机算法设计与分析第4版(王晓东著)课后答
案下载
计算机算法设计与分析第4版内容简介
第1章算法概述
1.1 算法与程序
1.2 算法复杂性分析
1.3 NP完全性理论
算法分析题1
算法实现题1
第2章递归与分治策略
2.1 递归的概念
2.2 分治法的基本思想
2.3 二分搜索技术
2.4 大整数的乘法
2.5 Strassen矩阵乘法
2.6 棋盘覆盖
2.7 合并排序
2.8 快速排序
2.9 线性时间选择
2.10 最接近点对问题
第3章动态规划
第4章贪心算法
第5章回溯法
第6章分支限界法
第7章随机化算法
第8章线性规划与网络流
附录A C++概要
参考文献
计算机算法设计与分析第4版目录
本书是普通高等教育“十一五”__规划教材和国家精品课程教材。

全书以算法设计策略为知识单元，系统介绍计算机算法的设计方法与分析技巧。

主要内容包括：算法概述、递归与分治策略、动态规划、贪心算法、回溯法、分支限界法、__化算法、线性规划与网络流等。

书中既涉及经典与实用算法及实例分析，又包括算法热点领域追踪。

为突出教材的`可读性和可用性，章首增加了学习要点提示，章末配有难易适度的算法分析题和算法实现题;配套出版了《计算机算法设计与分析习题解答(第2版)》;并免费提供电子课件和教学服务。

第⼀部分习题答案第⼀部分习题⼀、选择1、下列叙述中关于好的编程风格，正确的描述是：CA、程序中的注释是可有可⽆的为了增强可读性我们要在必要语句之后加注释B、对递归定义的数据结构不要使⽤递归过程递归的可读性强C、递归应是封闭的，尽量少使⽤全局变量D、多采⽤⼀些技巧以提⾼程序运⾏效率2、通常从正确性、易读性、健壮性、⾼效性等四个⽅⾯评价算法(包括程序)的质量。

以下解释错误的是 ( C )A、正确性算法应能正确地实现预定的功能(即处理要求)B、易读性算法应易于阅读和理解以便于调试修改和扩充C、健壮性当环境发⽣变化时，算法能适当地做出反应或进⾏处理，不会产⽣不需要的运⾏结果见课本14页D、⾼效性即达到所需要的时间性能3、以下说法正确的是 ( D )A、数据元素是数据的最⼩单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、数据结构是带有结构的数据元素的集合4、对于顺序表，以下说法错误的是（ A ）A、顺序表是⽤⼀维数组实现的线性表，数组的下标可以看成是元素的绝对地址B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中5、对顺序表上的插⼊、删除算法的时间复杂性分析来说，通常以（B ）为标准操作A、条件判断B、结点移动C、算术表达式D、赋值语句6、对于顺序表的优缺点，以下说法错误的是（ C ）A、⽆需为表⽰结点间的逻辑关系⽽增加额外的存储空间B、可以⽅便地随机存取表中的任⼀结点C、插⼊和删除运算较⽅便D、容易造成⼀部分空间长期闲置⽽得不到充分利⽤7、链表不具有的特点是：AA、可随机访问任⼀个元素B、插⼊删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表长度成正⽐8、若线性表最常⽤的操作是存取第i个元素及其前驱的值，则采⽤（D ）存储⽅式节省时间A单链表B、双向链表C、单循环链表D、顺序表9、有时为了叙述⽅便，可以对⼀些概念进⾏简称，以下说法错误的是（D ）A将“指针型变量”简称为“指针”B将“头指针变量”称为“头指针”C将“修改某指针型变量的值”称为“修改某指针”D将“p中指针所指结点”称为“P值”10．设指针P指向双链表的某⼀结点，则双链表结构的对称性可⽤（C ）式来刻画A p->prior->next->==p->next->nextB p->prior->prior->==p->next->priorC p->prior->next->==p->next->priorD p->next->next==p->prior->prior11.以下说错误的是（ A ）A对循环来说，从表中任⼀结点出发都能通过前后操作⽽扫描整个循环链表B对单链表来说，只有从头结点开始才能扫描表中全部结点C双链表的特点是找结点的前趋和后继都很容易D对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。

Algorithm Design Techniques and Analysis: English VersionExercise with AnswersIntroductionAlgorithms are an essential aspect of computer science. As such, students who are part of this field must master the art of algorithm design and analysis. Algorithm design refers to the process of creating algorithms that solve computational problems. Algorithm analysis, on the other hand, focuses on evaluating the resources required to execute those algorithms. This includes computational time and memory consumption.This document provides students with helpful algorithm design and analysis exercises. The exercises are in the formof questions with step-by-step solutions. The document is suitable for students who have completed the English versionof the Algorithm Design Techniques and Analysis textbook. The exercises cover various algorithm design techniques, such as divide-and-conquer, dynamic programming, and greedy approaches.InstructionEach exercise comes with a question and its solution. Read the question carefully and try to find a solution withoutlooking at the answer first. If you get stuck, look at the solution. Lastly, try the exercise agn without referring to the answer.Exercise 1: Divide and ConquerQuestion:Given an array of integers, find the maximum possible sum of a contiguous subarray.Example:Input: [-2, -3, 4, -1, -2, 1, 5, -3]Output: 7 (the contiguous subarray [4, -1, -2, 1, 5]) Solution:def max_subarray_sum(arr):if len(arr) ==1:return arr[0]mid =len(arr) //2left_arr = arr[:mid]right_arr = arr[mid:]max_left_sum = max_subarray_sum(left_arr)max_right_sum = max_subarray_sum(right_arr)max_left_border_sum =0left_border_sum =0for i in range(mid-1, -1, -1):left_border_sum += arr[i]max_left_border_sum =max(max_left_border_sum, left_b order_sum)max_right_border_sum =0right_border_sum =0for i in range(mid, len(arr)):right_border_sum += arr[i]max_right_border_sum =max(max_right_border_sum, righ t_border_sum)return max(max_left_sum, max_right_sum, max_left_border_s um+max_right_border_sum)Exercise 2: Dynamic ProgrammingQuestion:Given a list of lengths of steel rods and a corresponding list of prices, determine the maximum revenue you can get by cutting these rods into smaller pieces and selling them. Assume the cost of each cut is 0.Lengths: [1, 2, 3, 4, 5, 6, 7, 8]Prices: [1, 5, 8, 9, 10, 17, 17, 20]If the rod length is 4, the maximum revenue is 10.Solution:def max_revenue(lengths, prices, n):if n ==0:return0max_val =float('-inf')for i in range(n):max_val =max(max_val, prices[i] + max_revenue(length s, prices, n-i-1))return max_valExercise 3: Greedy AlgorithmQuestion:Given a set of jobs with start times and end times, find the maximum number of non-overlapping jobs that can be scheduled.Start times: [1, 3, 0, 5, 8, 5]End times: [2, 4, 6, 7, 9, 9]Output: 4Solution:def maximum_jobs(start_times, end_times):job_list =sorted(zip(end_times, start_times))count =0end_time =float('-inf')for e, s in job_list:if s >= end_time:count +=1end_time = ereturn countConclusionThe exercises presented in this document provide a practical way to master essential algorithm design and analysis techniques. Solving the problems without looking at the answers will expose students to the type of problems they might encounter in real life. The document’s solutionsprovide step-by-step instructions to ensure that students can approach the problems with confidence.。

算法设计技巧与分析课后答案吴永昶习题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。