算法设计技巧与分析第八章课后答案

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交换，这时处于队列末尾的显然时队列中最大的元素。

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

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

1.71次由上图可以看到执行的比较次数为1+1+2+2+2+6+2=16次1.11由上图可以得出比较次数为5+6+6+9=26次1.13FTF,TTT,FTF,TFF,FTF 1.16⑻ 执行该算法，元素比较的最少次数是 n-1。

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

(b)执行该算法，元素比较的最多次数是 吨严。

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

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

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

(d) 执行该算法，元素赋值的最多次数是 空严。

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

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

1.27不能用「关系来比较n 2和100n 2增长的阶2 .. n lim 2n ::100n 2n 2不是o(100n 2)的，即不能用•关系来比较n 2和100n 2增长 的阶。

1.321 100=0(a) 当n 为2的幕时，第六步执行的最大次数是：^2k , j =2kJ 时，nn、k _、［log n ］二 n log ni 4i 4(b) 由⑻可以得到：当每一次循环j 都为2的幕时，第六步 执行的次数最大，n n m — [log(3k -1)H nlog( n-1)i 4i 4(c)用0符号表示的算法的时间复杂性是 O(nlog n) 已证明n=2k的情况，下面证明 n=2k+1的情况:所以n=2kn log n 。

算法实现题3-7 数字三角形问题问题描述：给定一个由n行数字组成的数字三角形，如图所示。

试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

编程任务：对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。

数据输入：有文件input.txt提供输入数据。

文件的第1行是数字三角形的行数n，1<=n<=100。

接下来的n行是数字三角形各行的数字。

所有数字在0-99之间。

结果输出：程序运行结束时，将计算结果输出到文件output.txt中。

文件第1行中的数是计算出的最大值。

输入文件示例输出文件示例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5源程序：#include "stdio.h" voidmain(){ intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量in=fopen("input.txt","r");fscanf(in,"%d",&n);//将行数n读入到变量n中for(i=0;i<n;i++)//将各行数值读入到数组triangle中for(j=0;j<=i;j++)fscanf(in,"%d",&triangle[i][j]);for(int row=n-2;row>=0;row--)//从上往下递归计算for(int col=0;col<=row;col++)if(triangle[row+1][col]>triangle[row+1][col+1])triangle[row][col]+=triangle[row+1][col];elsetriangle[row][col]+=triangle[row+1][col+1];out=fopen("output.txt","w");fprintf(out,"%d",triangle[0][0]);//将最终结果输出到output.txt中 }算法实现题4-9 汽车加油问题问题描述：一辆汽车加满油后可行驶nkm。

第8 章排序技术课后习题讲解1. 填空题⑴排序的主要目的是为了以后对已排序的数据元素进行（）。

【解答】查找【分析】对已排序的记录序列进行查找通常能提高查找效率。

⑵对n个元素进行起泡排序，在（）情况下比较的次数最少，其比较次数为（）。

在（）情况下比较次数最多，其比较次数为（）。

【解答】正序，n-1，反序，n(n-1)/2⑶对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（）次。

【解答】3【分析】当把第7个记录60插入到有序表时，该有序表中有2个记录大于60。

⑷对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行快速排序，在递归调用中使用的栈所能达到的最大深度为（）。

【解答】3⑸对n个待排序记录序列进行快速排序，所需要的最好时间是（），最坏时间是（）。

【解答】O(nlog2n)，O(n2)⑹利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为（）。

【解答】n-1⑺如果要将序列（50，16，23，68，94，70，73）建成堆，只需把16与（）交换。

【解答】50⑻对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为（）的结点开始。

【解答】60【分析】60是该键值序列对应的完全二叉树中最后一个分支结点。

2. 选择题⑴下述排序方法中，比较次数与待排序记录的初始状态无关的是（）。

A插入排序和快速排序B归并排序和快速排序C选择排序和归并排序D插入排序和归并排序【解答】C【分析】选择排序在最好、最坏、平均情况下的时间性能均为O(n2)，归并排序在最好、最坏、平均情况下的时间性能均为O(nlog2n)。

⑵下列序列中，（）是执行第一趟快速排序的结果。

A [da，ax，eb，de，bb] ff [ha，gc]B [cd，eb，ax，da] ff [ha，gc，bb]C [gc，ax，eb，cd，bb] ff [da，ha]D [ax，bb，cd，da] ff [eb，gc，ha]【解答】A【分析】此题需要按字典序比较，前半区间中的所有元素都应小于ff，后半区间中的所有元素都应大于ff。

算法设计与分析智慧树知到课后章节答案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． 解：算法略。

参考答案第1章一、选择题1. C2. A3. C4. C A D B5. B6. B7. D 8. B 9. B 10. B 11. D 12. B二、填空题1. 输入；输出；确定性；可行性；有穷性2. 程序；有穷性3. 算法复杂度4. 时间复杂度；空间复杂度5. 正确性；简明性；高效性；最优性6. 精确算法；启发式算法7. 复杂性尽可能低的算法；其中复杂性最低者8. 最好性态；最坏性态；平均性态9. 基本运算10. 原地工作三、简答题1. 高级程序设计语言的主要好处是：（l）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可移植性好、重用率高；（4）把复杂琐碎的事务交给编译程序，所以自动化程度高，发用周期短，程序员可以集中集中时间和精力从事更重要的创造性劳动，提高程序质量。

2. 使用抽象数据类型带给算法设计的好处主要有：（1）算法顶层设计与底层实现分离，使得在进行顶层设计时不考虑它所用到的数据，运算表示和实现；反过来，在表示数据和实现底层运算时，只要定义清楚抽象数据类型而不必考虑在什么场合引用它。

这样做使算法设计的复杂性降低了，条理性增强了，既有助于迅速开发出程序原型，又使开发过程少出差错，程序可靠性高。

（2）算法设计与数据结构设计隔开，允许数据结构自由选择，从中比较，优化算法效率。

（3）数据模型和该模型上的运算统一在抽象数据类型中，反映它们之间内在的互相依赖和互相制约的关系，便于空间和时间耗费的折衷，灵活地满足用户要求。

（4）由于顶层设计和底层实现局部化，在设计中出现的差错也是局部的，因而容易查找也容易纠正，在设计中常常要做的增、删、改也都是局部的，因而也都容易进行。

第8 章排序技术课后习题讲解1. 填空题⑴排序的主要目的是为了以后对已排序的数据元素进行（）。

【解答】查找【分析】对已排序的记录序列进行查找通常能提高查找效率。

⑵对n个元素进行起泡排序，在（）情况下比较的次数最少，其比较次数为（）。

在（）情况下比较次数最多，其比较次数为（）。

【解答】正序，n-1，反序，n(n-1)/2⑶对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（）次。

【解答】3【分析】当把第7个记录60插入到有序表时，该有序表中有2个记录大于60。

⑷对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行快速排序，在递归调用中使用的栈所能达到的最大深度为（）。

【解答】3⑸对n个待排序记录序列进行快速排序，所需要的最好时间是（），最坏时间是（）。

【解答】O(nlog2n)，O(n2)⑹利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为（）。

【解答】n-1⑺如果要将序列（50，16，23，68，94，70，73）建成堆，只需把16与（）交换。

【解答】50⑻对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为（）的结点开始。

【解答】60【分析】60是该键值序列对应的完全二叉树中最后一个分支结点。

2. 选择题⑴下述排序方法中，比较次数与待排序记录的初始状态无关的是（）。

A插入排序和快速排序B归并排序和快速排序C选择排序和归并排序D插入排序和归并排序【解答】C【分析】选择排序在最好、最坏、平均情况下的时间性能均为O(n2)，归并排序在最好、最坏、平均情况下的时间性能均为O(nlog2n)。

⑵下列序列中，（）是执行第一趟快速排序的结果。

A [da，ax，eb，de，bb] ff [ha，gc]B [cd，eb，ax，da] ff [ha，gc，bb]C [gc，ax，eb，cd，bb] ff [da，ha]D [ax，bb，cd，da] ff [eb，gc，ha]【解答】A【分析】此题需要按字典序比较，前半区间中的所有元素都应小于ff，后半区间中的所有元素都应大于ff。

5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:●如果d整除u和v, 那么d一定能整除u±v;●如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。

故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—山羊C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5.描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法DectoBin(n)//将十进制整数n转换为二进制整数的算法//输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.31.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表‖60,35,81,98,14,47‖排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表‖60,35,81,98,14,47‖排序的过程如下所示:b.该算法不稳定.比如对列表‖2,2*‖排序c.该算法不在位.额外空间for S and Count[]4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i 个元素(1<=i<=n)b.删除有序数组的第i 个元素(依然有序) hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array ’s element(e.g., 0 for an array of positive numbers ) to mark the i th position is empty. (―lazy deletion ‖)第2章 习题2.17.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n )∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。

算法分析技巧与分析习题答案-标准化文件发布号：（9556-EUATWK-MWUB-WUNN-INNUL-DDQTY-KIIPage 54（a）The minimum number of element comparisons performed by the algorithm is n－1.This minimum is achieved when the input A[1..n] is already sorted in nondecreasing order.（b）The maximum number of element comparisons performed by the algorithm is(n－1)+( n－2)+…+2+1=n(n－1)/2.This maximum is achieved when the input A[1..n] is already sorted in decreasing order.（c）The minimum number of element assignments performed by the algorithm is 0.This minimum is achieved when the input A[1..n] is already sorted in nondecreasing order.（d）The maximum number of element assignments performed by the algorithm is 3[(n－1)+( n－2)+…+2+1]=3n(n－1)/2.This maximum is achieved when the input A[1..n] is already sorted in decreasing order.（e） The running time of Algorithm BUBBLESORT is (n2) in terms of the -notation, and (n) in terms of the -notation.（f）The running time cannot be expressed in terms of -notation, because the running time ranges from the linear to quadratic.Page 99（a）On the one hand，∑j=1n j log j≤∑j=1n n log n≤n2 log n.On the other hand，∑j=1n j log j≥∑j=n/2n n/2log n/2≥n/2n/2log n/2≥(n-1)n/4·log(n/2).Hence，∑j=1n j log j= (n2log n).（b）Let f(x)=x log x (x≥1). Since f(x) is an increasing function，we have ∑j=1n j log j≤∫1n+1 x log x d x≤(2(n+1)2 ln(n+1)-(n+1)2+1) / (4ln2).Also,∑j=1n j log j=∑j=2n j log j≥∫1n x log x d x≥(2n2 ln n-n2+1) / (4ln2).Thus，∑j=1n j log j= (n2ln n)= (n2log n).(a)The characteristic equation isx=3.Thus, f(n)=c·3n（n≥0），where c is determined by the initial value of the sequence : f(0).Solving the equation f(0)=5=c, we obtain c=5.It follows thatf(n)=5·3n（n≥0）.(b)The characteristic equation isx=2.Thus，f(n)=c·2n（n≥0），where c is determined by the initial value of the sequence : f(0).Solving the equation f(0)=2=c, we obtain c=2.It follows thatf(n)=2n+1（n≥0）.(a) The characteristic equation is x2-5x +6=0, and hence x1=2 and x2=, the solution to the recurrence is f(n)= c1·2n + c2·3n （n≥0）.To find the values of c1 and c2, we solve the two simultaneous equations:f(0)=1= c1 + c2 and f(1)=0=2c1 +3c2.Solving the two simultaneous equations, we obtain c1=3 and c2 = -2. It follows that f(n)=3·2n-2·3n （n≥0）.(b) The characteristic equation is x2-4x +4=0, and hence x1=x2=, the solution to the recurrence is f(n)= c1·2n + c2·n 2n （n≥0）.To find the values of c1 and c2, we solve the two simultaneous equations:f(0)=6= c1 and f(1)=8=2c1 +2c2.Solving the two simultaneous equations, we obtain c1=6 and c2 = -2. It follows that f(n)=3·2n+1-n·2n+1（n≥0）.(a) f(n)= f(n-1)+ n2= f(n-2)+(n-1)2+n2=……= f(0)+12+22+…+(n-1)2+n2=0+12+22+…+(n-1)2+n2=n(n+1)(2n+1)/6 （n≥0）.(b) Let f(n)=2n g(n)（g(0)=f(0)=1）. Then,2n g(n)= 2·2n-1g(n-1)+n，which simplifies tog(n)=g(n-1)+n·2-n ,whose solution isg(n) =∑i=1n i·2-i +1= 2-(n+2)/2n+1=3-(n+2)/2n（n≥0）.Hence, f(n)=3·2n-n-2 （n≥0）.(c) Let f(n)=3n g(n)（g(0)=f(0)=3）. Then,3n g(n)=3·3n-1g(n-1)+ 2n，which simplifies tog(n)=g(n-1)+(2/3)n ,whose solution isg(n) = g(0)+∑i=1n(2/3) i=3+∑i=1n(2/3) i=5-2(2/3) n（n≥0）.Hence, f(n)=5·3n-2n+1（n≥0）.Page 156-158solution:First, we note that the time complexity of RADIX is (kn), where n is the number of elements in array A, and k is the maximum size among elements in A. Thus,(1)when array A consists of n positive integers in the interval [1..n], we can concludethat k=O(log n) and the time complexity can be expressed as O(n log n) in terms of n.(2)when array A consists of n positive integers in the interval [1.. n2], we canconclude that k=O(log n) and the time complexity can be expressed as O(n log n) in terms of n.(3)when array A consists of n positive integers in the interval [1..2n], we canconclude that k=O(n) and the time complexity can be expressed as O(n2) in terms of n.solution:Since A[1..n] is an array of positive integers in the interval [1.. n!], it follows thatk=O(n log n) and the time complexity of RADIX is O(n2log n). Considering the time complexity of BOTTOMUPSORT is (n log n), it is very likely that BOTTOMUPSORT is faster.solution:The only modification is to change “for j←1 to n” to “for j←n to 1 step -1” in Step 3 of Procedure perm2 in Algorithm PERMUTATIONS2 .disproof:Take the following instance as a counterexample: n=4, A[1..n]={1,2,3,4}. Obviously, if we run Algorithm MAJORITY on this instance, then in step 7 of Procedure candidate j=n and count=0, but c=4 isn’t the majority element.Exercise 6解答：当序列中的元素都相同时，每次执行算法SPLIT，仅出现一次元素交换，即将序列的第一个元素与最后一个元素交换，且划分元素的新位置为该序列的最后一个位置。

习题4.13A1A2 A3A4~A3 各2 次；A2各1次; (b)元素最大交换次数：A9〜A5最多3次；A1最多4次最多共需16次元素交换4.13另解：考虑第i个节点，其子节点为2i，则最多可交换1次; 若子节点有子节点22i, 则最多可交换2 次；若….•有子节点i疋k,则最多可交换k 次；因此有i 泌 < 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 J (low+high)/25.s1 J SUM(low,mid)6.s2J SUM(mid+1, high)7.return s1+s28.end if工作空间：mid~ (logn), s1&s2~ (1)(后序遍历树，不断释放空间，故为常数(1))，总的工作空间为(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 J (low+high)/29.fl J freq(A[low, mid])10.f2 J freq(A[mid+1, high])11.return f1+f212.end if复杂度:T(n)=T( n/2 )+ T( n/2 )〜2T(n/2)(设2k《＜2k+1) =-=2k T(n/2k) =2k T(1) = n6.16 修改后的 MERGESORT 算法n 1 if n m 最小比较次数 C(n) 2C(n/2) n/2 if n m令n/2k =m ^2,展开可知：T(n)= 2k T(n/2k ) + kn - (2 k -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)= (nlogn), 其中表达式有 nm, nlogn, nlogm, n/m 等. 有 n/m < nlogm < nm 且须有 nm=O(nlogn), i.e., nm <c nlogn, 则须有 mlogn.可令c=1,贝U m W ogn.另一方面，最大比较次数 T(n) n(n 1)/2 if n m 2T(n/2) n 1 if n mC(n) = 2k C(n/2k)+kn/2 = n/m (惦-1) + (n/2)log(n/m)= (nlogn)6.35 split(A[low,...high])1.x J A[low] // 备份为x2.while (low<high){3.while (low<high && A[high]>0)4.A[low] J A[high]5.while (lowvhigh && A[low ] O)6.A[high] J A[low]7.}8.A[low] J x //这时, low=high --high; ++low;k7.3动态规划法计算二项式系数C n，并分析其时间复杂度。

算法导论第八章答案8.2-4 :在O(1)的时间内，回答出输入的整数中有多少个落在区间[a...b]内。

给出的算法的预处理时间为O(n+k)算法思想：利用计数排序，由于在计数排序中有一个存储数值个数的临时存储区C[0...k]，利用这个数组即可。

#includeusing namespace std;//通过改编计数排序而来，因为有些部分需要注释掉void counting_sort(int*&a, int length, int k, int*&b, int*&c);int main(){ const int LEN =100;int*a =newint[LEN];for(int i =0; i < LEN; i++)a[i] = (i -50)*(i -50) +4;int* b =new int[LEN];const int k =2504;int* c =new int[k +1];counting_sort(a, LEN, k, b, c);//这里需要注释掉//for(int i = 0; i < LEN; i++)//cout<<b[i]<<endl;< p="">int m; int n;while(cin>>m>>n){ if(m >n)cout<<"区间输入不对"<<endl;< p="">else { if(n <0) cout<<"个数为"<<0<<endl;< p="">else if(m <=0&& n <= k) cout<<"个数为"<<c[n]<<endl;< p="">else if(n > k && m >0) cout<<"个数为"<<<endl;<="" c[m=""p="">else if(n > k && m <=0) cout<<"个数为"<<c[k]<<endl;< p="">else cout<<"个数为"<<<endl;<="" c[m="" p="">}} return 0; }void counting_sort(int*&a, int length, int k, int*&b, int*&c){ for(int i =0; i < k +1; i++) c[i] =0;for(int i =0; i < length; i++) c[a[i]]++;for(int i =1; i < k +1; i++) c[i] = c[i] + c[i-1];//这里需注释，因为对c数组内的元素进行减减操作会使其改变/*for(int i = length - 1; i >= 0; i--){b[c[a[i]] - 1] = a[i];c[a[i]]--;}*/ }PS:计数排序的总时间为O(k+n)，在实践中，如果当k = O(n)时，我们常常采用计数排序，这时其运行时间为O(n)8.3-4 :说明如何在O(n)时间内，对0到n^2 - 1之间的n个整数进行排序。

1．二元可满足性问题 2SAT例：给定布尔变量的一个有限集合{}n u u u U ,,,21 =及定义其上的子句{}m c c c C ,,,21 =，其中m k c k ,,2,1,2|| ==。

问：是否存在U 的一个真赋值，使得C 中所有的子句均被满足？证明： 2SAT 是P －类问题。

为叙述方便，采用数理逻辑中的“合取式”表达逻辑命题，于是∏∏==+==∧∧∧=mk k k m k k m y x c c c c C 1121)(其中j i c c ⋅表示逻辑“与”，k k y x +表示逻辑“或”，k k y x ,是某个j u 或i u 。

考虑表达式∏=+=mk k k y x C 1)(，如果有某个i i k k u u y x +=+，则在乘积式中可以去掉该子句：)(\'i i u u C C +=，可见C 与'C 的可满足性是等价的。

所以我们可以假定C 中不含有形如i i u u +的子句。

注意到此时C 中的子句个数不会超过)1(-n n 。

如果逻辑变量n u 或它的非n u 在C 的某个子句中出现，我们将C 表示成)())(()(11h n n k n n z u z u y u y u G C ++++⋅= （1） 其中G 是C 的一部分子句，而且不出现逻辑变量i u 或它的非i u 。

令∏≤≤≤≤+⋅=h j k i j i z y G C 1,1)(' （2）(2)式中不再含有变量n u 和它的非n u 。

记{}121,,,'-=n u u u U 。

如果存在U 的真赋值，使得C 满足，在'U 也一定满足。

因为如果n u 取真值，则所有的j z 必然取真值；n u 取假值，所有的i y 必然都取真值，不管那中情况，'C 的乘积部分必然取真值。

反之，假设存在'U 的真赋值，使得'C 满足。

若有某个i y 取假值，则所有的j z 必然取真值，此时令n u 取真值，得到U 的真赋值，使得C 满足。