算法设计与分析习题第二章分治与递归
- 格式:ppt
- 大小:233.00 KB
- 文档页数:17
算法分析(第二章):递归与分治法一、递归的概念知识再现:等比数列求和公式:1、定义:直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。
2、与分治法的关系:由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。
在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。
分治与递归经常同时应用在算法设计之中,并由此产生许多高效算法。
3、递推方程:(1)定义:设序列01,....na a a简记为{na},把n a与某些个()ia i n<联系起来的等式叫做关于该序列的递推方程。
(2)求解:给定关于序列{n a}的递推方程和若干初值,计算n a。
4、应用:阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序5、优缺点:优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。
缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
二、递归算法改进:1、迭代法:(1)不断用递推方程的右部替代左部(2)每一次替换,随着n的降低在和式中多出一项(3)直到出现初值以后停止迭代(4)将初值代入并对和式求和(5)可用数学归纳法验证解的正确性2、举例:-----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1(1)1T n T nT=−+=()(1)1W n W n nW=−+−(1)=021n-23()2(1)12[2(2)1]12(2)21...2++2 (121)n n n T n T n T n T n T −−=−+=−++=−++==++=−(1)2 ()(1)1((n-2)+11)1(2)(2)(1)...(1)12...(2)(1)(1)/2W n W n n W n n W n n n W n n n n =−+−=−−+−=−+−+−==++++−+−=−3、换元迭代:(1)将对n 的递推式换成对其他变元k 的递推式 (2)对k 进行迭代(3)将解(关于k 的函数)转换成关于n 的函数4、举例:---------------二分归并排序---------------()2(/2)1W n W n n W =+−(1)=0(1)换元:假设2kn =,递推方程如下()2(/2)1W n W n n W =+−(1)=0 → 1(2)2(2)21k k k W W W−=+−(0)=0(2)迭代求解:12122222321332133212()2(2)212(2(2)21)212(2)22212(2)2*2212(2(2)21)2212(2)222212(2)3*2221...2(0)*2(22...21)22k k k k k k k k k k k k k k k k k k k k k k k k W n W W W W W W W W k k −−−−−−−+−+−−−=+−=+−+−=+−+−=+−−=+−+−−=+−+−−=+−−−==+−++++=−1log 1n n n +=−+(3)解的正确性—归纳验证: 证明递推方程的解是()(1)/2W n n n =−()(1)1W n W n n W =−+−(1)=0,(n 1)=n +n=n(n-1)/2+n =n[(n-1)/2+1]=n(n+1)/2n W W +方法:数学归纳法证 n=1,W(1)=1*(1-1)/2=0假设对于解满足方程,则()---------------快速排序--------------------->>>平均工作量:假设首元素排好序在每个位置是等概率的112()()()(1)0n i T n T i O n n T −==+=∑ >>>对于高阶方程应该先化简,然后迭代(1)差消化简:利用两个方程相减,将右边的项尽可能消去,以达到降阶的目的。
《算法设计与分析》实验指导实验一分治与递归一、实验目的:1. 理解递归的概念。
2. 掌握设计有效算法的分治策略。
3. 掌握C++面向对象编程方法。
二、实验指导1. 分治法的总体思想求解一个复杂问题可以将其分解成若干个子问题,子问题还可以进一步分解成更小的问题,直到分解所得的小问题是一些基本问题,并且其求解方法是已知的,可以直接求解为止。
分治法作为一种算法设计策略,要求分解所得的子问题是同类问题,并要求原问题的解可以通过组合子问题的解来获取。
分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效的算法。
2. 分治法的基本步骤divide-and-conquer(P){if ( | P | <= n0) adhoc(P); //解决小规模的问题divide P into smaller subinstances P1,P2,...,Pk;//分解问题for (i=1,i<=k,i++)yi=divide-and-conquer(Pi); //递归的解各子问题return merge(y1,...,yk); //将各子问题的解合并为原问题的解}3. C++类定义例class Complex{public:Complex( ):real(0),imag(0) {} //构造函数Complex(double r,double i):real(r),imag(i) {} //构造函数Complex operator + (Complex c2); //重载“+”运算符operator double( ) //重载类型转换运算符{return real;}friend ostream& operator << (ostream&,Complex&); //重载流插入运算符“<<”private:double real;double imag;};三、实验内容及要求:在程序中创建一个学生对象数组并初始化数据,完成如下编程任务。
计算机算法设计与分析第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版)》;并免费提供电子课件和教学服务。
黄宇《算法设计与分析》课后习题解析(⼆)第2章:从算法的视⾓重新审视数学的概念2.1:(向下取整)题⽬:请计算满⾜下⾯两个条件的实数的区间解析:根据向下取整的含义,令,讨论a的取值范围即可解答:令,则可得:即:故的取值区间为:2.2: (取整函数)题⽬:证明:对于任意整数,(提⽰:将n划分为)。
解析:根据提⽰将n进⾏划分,根据取整函数的定义⽤k表⽰取整函数,即可证明;证明如下:因为对于任意整数,可划分为,则:① ;② ;综上:对于任意整数,, 得证;2.3: (斐波拉契数列)对于斐波拉契数列,请证明:1)题⽬:是偶数当且仅当n能被3整除解析:由斐波拉契数列的递归定义式,容易联想到数学归纳法;证明如下:(采⽤数学归纳法)i)当n = 1,2,3时,依次为1,1,2,符合命题;ii)假设当(k>=1)时命题均成⽴,则:① 当n = 3k+1时,是奇数,成⽴;② 当n = 3k+2时,是奇数,成⽴;③ 当 n = 3(k+1)时,是偶数,成⽴;综上:归纳可得为偶数当且仅当,得证;2)题⽬:x x =1+a (0<a <1)x =1+a (0<a <1)⌊x ⌋=1⇒⌊x ⌋=21⌊x ⌋=2⌊1+a +22a ⌋=1a +22a <1⇒0<a <−21⇒1<a +1<⇒21<x <2x (1,)2n ≥1⌈log (n +1)⌉=⌊logn ⌋+12≤k n ≤2−k +11n ≥12≤k n ≤2−k +11k +1=⌈log (2+k 1)⌉≤⌈log (n +1)⌉≤⌈log (2)⌉=k +1k +1=>⌈log (n +1)⌉=k +1k =⌊log (2)⌋≤k ⌊logn ⌋≤⌊log (2−k +11)⌋=k =>⌊logn ⌋=k n ≥1⌈log (n +1)⌉=k +1=⌊logn ⌋+1F n F n n ≤3k F =n F +n −1F =n −2F +3k F =3k −1>F 3k +1F =n F +3k +1F =3k >F 3k +2F =n F +3k +2F =3k +1>F 3k +3F n 3∣n F −n 2F F =n +1n −1(−1)n +1解析:同1)理,容易联想到数学归纳法证明如下:(采⽤数学归纳法)i)当n = 2时,, 易知成⽴;ii)假设当 n = k 时命题成⽴,① 若k = 2m, 则,当n = k+1 = 2m+1时,要证命题成⽴,即证: => ,代⼊递推式, 得:, 易知是恒等式,故命题成⽴;②当 k=2m+1时,同①理可证命题成⽴;综上:归纳可得,得证;2.4:(完美⼆叉树)给定⼀棵完美⼆叉树,记其节点数为,⾼度为,叶节点数为,内部节点数为1)题⽬:给定上述4个量中的任意⼀个,请推导出其他3个量解析:根据完美⼆叉树的结构特点易得解答:(仅以已知⾼度h推导其他三个量为例,其余同理)已知⾼度为h,可得:节点数:叶节点数:内部节点数:2)题⽬:请计算完美⼆叉树任意⼀层的节点个数:① 如果任意指定深度为的⼀层节点,请计算该层节点个数;② 如果任意指定⾼度为的⼀层节点,请计算该层节点个数;解析:根据完美⼆叉树的结构特点易得(注意节点深度和节点⾼度是互补的,相加为树⾼)解答:① ; ② ;2.5: (⼆叉树的性质)对于⼀棵⾮空的⼆叉树T,记其中叶节点的个数为,有1个⼦节点的节点个数为,有两个⼦节点的节点个数为1)题⽬:如果T是⼀棵2-tree,请证明。
《算法设计与分析》习题第一章算法引论1、算法的定义?答:算法是指在解决问题时,按照某种机械步骤一定可以得到问题结果的处理过程。
通俗讲,算法:就是解决问题的方法或过程。
2、算法的特征?答:1)算法有零个或多个输入;2)算法有一个或多个输出; 3)确定性;4)有穷性3、算法的描述方法有几种?答:自然语言、图形、伪代码、计算机程序设计语言4、衡量算法的优劣从哪几个方面?答:(1) 算法实现所耗费的时间(时间复杂度);(2) 算法实现所所耗费的存储空间(空间复杂度);(3) 算法应易于理解,易于编码,易于调试等等。
5、时间复杂度、空间复杂度定义?答:指的是算法在运行过程中所需要的资源(时间、空间)多少。
6、时间复杂度计算:{i=1;while(i<=n)i=i*2; }答:语句①执行次数1次,语句②③执行次数f(n), 2^f(n)<=n,则f(n) <=log2n;算法执行时间: T(n)= 2log2n +1时间复杂度:记为O(log2n) ;7.递归算法的特点?答:①每个递归函数都必须有非递归定义的初值;否则,递归函数无法计算;(递归终止条件)②递归中用较小自变量函数值来表达较大自变量函数值;(递归方程式)8、算法设计中常用的算法设计策略?答:①蛮力法;②倒推法;③循环与递归;④分治法;⑤动态规划法;⑥贪心法;⑦回溯法;⑧分治限界法9、设计算法:递归法:汉诺塔问题?兔子序列(上楼梯问题)?整数划分问题?蛮力法:百鸡百钱问题?倒推法:穿越沙漠问题?答:算法如下: (1) 递归法● 汉诺塔问题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); } }● 兔子序列(fibonaci 数列 )递归实现:Int F(int n) {if(n<=2) return 1; elsereturn F(n-1)+ F(n-2); }● 上楼梯问题 Int F(int n) {if(n=1) return 1 if(n=2) return 2; elsereturn F(n-1)+ F(n-2); }● 整数划分问题问题描述:将正整数n 表示成一系列正整数之和,n=n1+n1+n3+…将最大加数不大于m 的划分个数,记作q(n,m)。
算法分析与设计习题第一章算法引论一、填空题:1、算法运行所需要的计算机资源的量,称为算法复杂性,主要包括时间复杂度和空间复杂度。
2、多项式10()m m A n a n a n a =+++的上界为O(n m )。
3、算法的基本特征:输入、输出、确定性、有限性。
4、如何从两个方面评价一个算法的优劣:时间复杂度、空间复杂度。
5、计算下面算法的时间复杂度记为: O(n 3) 。
for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]= c[i][j]+a[i][k]*b[k][j];}6、描述算法常用的方法:自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。
7、算法设计的基本要求:正确性 和 可读性。
8、计算下面算法的时间复杂度记为: O(n 2) 。
for (i =1;i<n; i++){ y=y+1;for (j =0;j <=2n ;j++ )x ++;}9、计算机求解问题的步骤:问题分析、数学模型建立、算法设计与选择、算法表示、算法分析、算法实现、程序调试、结果整理文档编制。
10、算法是指解决问题的 方法或过程 。
二、简答题:1、按照时间复杂度从低到高排列:O( 4n 2)、O( logn)、O( 3n )、O( 20n)、O( 2)、O( n 2/3),O( n!)应该排在哪一位?答:O( 2),O( logn),O( n 2/3),O( 20n),O( 4n 2),O( 3n ),O( n!)2、什么是算法?算法的特征有哪些?答:1)算法:指在解决问题时,按照某种机械步骤一定可以得到问题结果的处理过程。
通俗讲,算法:就是解决问题的方法或过程。
2)特征:1)算法有零个或多个输入;2)算法有一个或多个输出; 3)确定性 ; 4)有穷性3、给出算法的定义?何谓算法的复杂性?计算下例在最坏情况下的时间复杂性?for(j=1;j<=n;j++) (1)for(i=1;i<=n;i++) (2) {c[i][j]=0; (3)for(k=1;k<=n;k++) (4)c[i][j]= c[i][j]+a[i][k]*b[k][j]; } (5)答:1)定义:指在解决问题时,按照某种机械步骤一定可以得到问题结果的处理过程。
算法设计与分析第2章递归与分治策略(1)2理解递归的概念。
掌握设计有效算法的分治策略。
通过下面的范例学习分治策略设计技巧。
二分搜索技术; 大整数乘法; Strassen 矩阵乘法; 合并排序和快速排序; 线性时间选择; 最接近点对问题; 重点和难点:递归和分治的概念与基本思想递归方程的求解方法学习要点3引言设计算法有许多方法 排序问题Bubble sort: bubblingInsertion sort: incremental approach (增量靠近) Merge sort: divide-and conquer (分而治之)Quick sort: location (元素定位)……分治算法的最坏运行时间远比插入排序还少4引言分而治之 清·俞樾《群经平议·周官二》“巫马下士二人医四人”:“凡邦之有疾病者,疕疡者造焉,则使医分而治之,是亦不自医也。
” 各个击破集中红军相机应付当前之敌,反对分兵,避免被敌人各个击破。
(毛泽东《中国的红色政权为什么能够存在》)5天下大事,必做于细天下难事,必做于易--------老子《道德经》引言分治法总体思想分治法总体思想分治法总体思想分治法总体思想10¾Divide=整个问题划分为多个子问题¾Conquer=求解每个子问题(递归调用正在设计的算法)¾Combine=合并子问题的解,形成原始问题的解。
分治法总体思想11分治法总体思想分治法的设计思想是:1)将一个难以直接解决的大问题,分割成一些规模较小的子问题;这些子问题互相独立且与原问题相同;2)递归地解子问题;3) 将各个子问题的解合并得到原问题的解.12问题: X 和Y 是两个n 位的二进制整数,分别表示为X=x n-1x n-2...x 0, Y=y n-1y n-2...y 0,其中0 ≤x i , y j ≤1 (i, j=0,1,…n-1) ,设计一个算法求X ×Y ,并分析其计算复杂度。