算法与程序设计课件

算法与程序设计第1章算法基础学习要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用伪代码描述算法的方法。第1章算法基础1.1算法（Algorithm）1.2算法分析1.3算法的运行时间1.1算法(Algorithm)1.算法的定义2.算法的性质3.算法的表示4.算法举例5.程序6.冒泡排序算法7.算法正确性证明算法通常指可以用来解决的某一类问题的步骤，这些步骤必须是明确的和有效的，而且能够在有限步之内完成的。1.算法的定义一般来说，“用算法解决问题”可以利用计算机帮助完成。1.1算法(Algorithm)“算法”的大陆中文名称出自公元前1世纪成书的《周髀算经》；英文名称Algorithm来自于9世纪波斯数学家al-Khwarizmi；欧几里得算法被人们认为是史上第一个算法。1.算法的定义1.1算法(Algorithm)2.算法的性质1）可行性2）确定性3）有穷性4）有输入信息的说明5）有输出结果的说明3.算法的表示

描述算法可以有不同的方式,常用的有自然语言、程序框图、程序设计语言、伪代码等.1.1算法(Algorithm)可行性：算法中描述的操作都可通过有限次的基本运算来实现。确定性：算法中每个步骤含义明确，无二义性。有穷性：一个算法必须保证在有限个操作步骤执行后终止。输入：一个算法应具有零个或多个输入。输出：一个算法应具有一个或多个输出。2.算法的性质1.1算法(Algorithm)自然语言就是人们日常使用的语言，可以是汉语或英语或其它语言。除了那些很简单的问题外，一般不用自然语言描述算法。（1）自然语言3.算法的表示1.1算法(Algorithm)1.1算法(Algorithm)概念：伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。特点：它如同一篇文章一样，自上而下地写下来。每一行(或几行)表示一个基本操作。用处：适用于设计过程中需要反复修改时的流程描述。（2）伪代码3.算法的表示1.1算法(Algorithm)伪代码规则说明：见教材P3a）缩进形式表示块结构，主要体现在循环和条件控制结构上。b）while,do-while,for循环结构，以及if-then-else条件结构采用类似高级语言中相应表示。c）符号“//”后是注释部分。d）多重赋值表达为i←j←e。e）所有变量不经显式说明均为局部变量。f）通过数组名后跟下标访问数组元素；符号“..”表示数组中元素的范围。A[i]A[i..j]3.算法的表示1.1算法(Algorithm)g）复合数据可以组织成由属性或域组成的对象，通过域名后跟方括号括住的对象名访问某个特定域。Length[A]h）通过传值将参数传给一个过程；当传递一个对象时，只拷贝指向表示对象的数据的指针，不拷贝它的各个域。i）“and”和“or”是布尔运算符。j）break语句表示将控制转移到含有break的最内层循环语句后面的第一条语句。3.算法的表示令士兵从1～3报数，结果最后一个士兵报2；令士兵从1～5报数，结果最后一个士兵报3；令士兵从1～7报数，结果最后一个士兵报2；【例1】韩信点兵你能算出韩信至少有多少兵吗？1.1算法(Algorithm)4.算法举例【例1】韩信点兵1.列出除以3余2的数：2，5，8，11，14，17，20，23，26…2.列出除以5余3的数：3，8，13，18，23，28…3.这两列数中，首先出现的公共数是8，3与5的最小公倍数是15。两个条件合并成一个就是8＋15×整数，列出这一串数是8，23，38，…，4.列出除以7余2的数

：9，16，23，30…5.得出符合题目条件的最小数是23。6.我们已把题目中三个条件合并成一个：被105除余23的数。1.1算法(Algorithm)4.算法举例【例1】韩信点兵算法描述三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。

这首诗的意思是：用3除所得的余数乘上70，加上用5除所得余数乘以21，再加上用7除所得的余数乘上15，结果大于105就减去105的倍数，这样就知道所求的数了。1.1算法(Algorithm)4.算法举例最初记述这类算法的是一本名叫《孙子算经》的书。这类算法的名称也很多，宋朝周密叫它“鬼谷算”，又名“隔墙算”；杨辉叫它“剪管术”；而比较通行的名称是“韩信点兵”。这在数学史上是极有名的问题，外国人一般把它称为“中国剩余定理”。【例1】韩信点兵1.1算法(Algorithm)4.算法举例【点评】了解一些经典算法是我们的学习目标。

【例2】

求1+2+3+4+5+6累加和算法1.按照逐一相加的算法进行.第一步:计算1+2,得3;第二步:将第一步中的运算结果3与3相加得6;第三步:将第二步中的运算结果6与4相加得10;第四步:将第三步中的运算结果10与5相加得15;第五步:将第四步中的运算结果15与6相加得21.4.算法举例太繁琐1.1算法(Algorithm)算法2.可以运用下面公式直接计算.第一步:取n=6;第二步:计算;第三步:输出计算结果.【点评】算法1繁琐,步骤较多;算法2简单，步骤较少。找出好的算法是我们的学习目标。4.算法举例

【例2】

求1+2+3+4+5+6累加和1.1算法(Algorithm)4.算法举例【例3】

求1×2×3×4×5S1：先求1×2，得到结果2S2：将步骤1得到的乘积2再乘以3，得到结果6S3：将6再乘以4，得24S4：将24再乘以5，得120如果要求1×2×…×1000，则要写999个步骤太繁琐1.1算法(Algorithm)

S1：令p=1S2：令i=2S3：计算p×i，乘积仍放在变量p中，可表示为：p=p×iS4：i的值加1，即i=i+1。S5：如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是结果。4.算法举例【例3】

求1×2×3×4×51.1算法(Algorithm)

如果题目改为：求1×3×5×……×1000：S1：p=1S2：i=3S3：p=p×iS4：i=i+2S5：若i≤1000，返回S3。否则，结束。算法简练4.算法举例1.1算法(Algorithm)Jiechen(n)p←1i←2whilei<=ndop←p*ii=i+1returnpLianchen(n)p←1i←3whilei<=ndop←p*ii=i+2returnp*n4.算法举例1.1算法(Algorithm)5.程序（program）程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(3)。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。史上第一次编写程序是AdaByron于1842年为巴贝奇分析机编写求解伯努利方程的程序，因此AdaByron被大多数人认为是世界上第一位程序员。1.1算法(Algorithm)6.冒泡排序（bubblesort）（1）自然语言描述将相邻的两个元素进行比较，如果左边的元素大于右边元素值，则将这两个元素进行交换，否则不改变位置，重复这个过程，直到比较到最后一个元素为止。1.1算法(Algorithm)6.冒泡排序（bubblesort）（2）伪代码描述BUBBLE-SORT(A)1fori←1tolength[A]2doforj←lenth[A]downtoi+13doifA[j]<A[j-1]4thenexchangeA[j]↔A[j-1]1.1算法(Algorithm)6.冒泡排序（bubblesort）【例】已知序列A={5，2，4，6，1，3}1524

631253

461235

4612345

612345

6用程序如何描述冒泡排序算法？1.1算法(Algorithm)6.冒泡排序（bubblesort）voidbubblesort(intA[],intn){inti,j,temp;for(i=0;i<n;i++)for(j=n-1;j>i;j--)if(A[j]<A[j-1]){temp=A[j];A[j]=A[j-1];A[j-1]=temp;}}1.1算法(Algorithm)（3）程序描述7.算法正确性证明循环中始终为真值的部分被称为循环不变式。利用循环不变式的结果可以证明算法的正确性。循环不变式1.1算法(Algorithm)1.2算法分析

算法分析是对一个算法所需的计算资源进行预测。最重要的计算资源是时间和空间资源。时间和空间资源=算法复杂度算法的时间复杂度T(n)；（所需时间资源）算法的空间复杂度S(n)。（所需空间资源）其中n是问题的规模（输入大小）。[注]不特别说明情况下，对算法只分析时间复杂度。1.2算法分析1.算法分析的基本法则2.

冒泡排序算法分析3.不同情况下的算法时间复杂度1.算法分析的基本法则（1）for/while循环循环体内计算时间*循环次数；（2）嵌套循环循环体内计算时间*所有循环次数；（3）顺序语句各语句计算时间相加；（4）if-else语句if语句计算时间和else语句计算时间的较大者。1.2算法分析2.

冒泡排序算法分析BUBBLE-SORT(A)cost

1fori←1tolength[A]c12doforj←lenth[A]downtoi+1c13doifA[j]<A[j-1]c24thenexchangeA[j]↔A[j-1]c31.2算法分析timesn+1sum(n-i+1)sum(n-i)ti3.不同情况下的算法时间复杂度（1）最坏情况下的时间复杂度Tmax(n)=max{T(I)|size(I)=n}（2）最好情况下的时间复杂度

Tmin(n)=min{T(I)|size(I)=n}（3）平均情况下的时间复杂度

Tavg(n)=

其中I是问题的规模为n的实例，p(I)是实例I出现的概率。1.2算法分析3.不同情况下的算法时间复杂度BUBBLE-SORT(A)cost

1fori←1tolength[A]c12doforj←lenth[A]downtoi+1c13doifA[j]<A[j-1]c24thenexchangeA[j]↔A[j-1]c31.2算法分析timesn+1sum(n-i+1)sum(n-i)ti算法最坏情况下的运行时间是任一输入运行时间的上界并且经常出现，所以对一个算法我们关心的是最坏情况下的时间复杂度。3.不同情况下的算法时间复杂度1.2算法分析1.3算法的运行时间1.算法渐近复杂性2.渐近表示3.算法分析中常见的复杂性函数4.算法分类1.3算法的运行时间T(n)

,asn

;(T(n)-t(n))/T(n)0

，asn;称t(n)是T(n)的渐近性态，为算法的渐近复杂度。在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。1.算法渐近复杂性1.算法渐近复杂性举例：T（N）=3N2+4NlogN+7t（N）=3N21.3算法的运行时间2.渐近表示在下面的讨论中，对所有n，f(n)

0，g(n)

0。（1）渐近上界记号OO(g(n))={f(n)|存在正常数c和n0使得对所有n

n0有：0

f(n)

cg(n)}（2）渐近下界记号

(g(n))={f(n)|存在正常数c和n0使得对所有n

n0有：0

cg(n)

f(n)}1.3算法的运行时间（3）紧渐近界记号

(g(n))={f(n)|存在正常数c1,c2和n0使得对所有n

n0有：c1g(n)

f(n)

c2g(n)}

2.渐近表示1.3算法的运行时间3.算法分析中常见的复杂性函数1.3算法的运行时间小规模数据大规模数据4.算法分类多项式时间算法（polynomialtimealgorithm)：用多项式来对计算时间限界的算法。O(1)<O(lbn)<O(n)<O(nlbn)<O(n2)<O(n3)指数时间算法（exponentialtimealgorithm)：计算时间用指数函数限界的算法。O(2n)<O(n!)<O(nn)1.3算法的运行时间第1章算法基础学习要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用伪代码描述算法的方法。练习1.下面的程序段违反了算法的()原则。

voidsam()

{intn=2;

while(!odd(n))n+=2;

printf(n);

}A.有穷性B.确定性C.可行性D.健壮性练习2.下面函数中渐进时间最小的是()。A.T1(n)=n+nlogn

B.T2(n)=2n+nlogn

C.T3(n)=n2-logn

D.T4(n)=n+100logn3.下述函数中渐进时间最小的是()。A.T1(n)=nlog2n+100log2n

B.T2(n)=2nlog2n-100log2n

C.T3(n)=n2-100log2n

D.T4(n)=4nlog2n-100log2n51第2章分治法2.1递归2.2分治法2.3分治法应用实例递推与递归报数问题一队士兵从排头向排尾报数是一个递推问题an=an-1+1如果要求从排尾向排头报数呢？要求排头报数为1是一个递归问题an=an-1+1a1=1德罗斯特效应德罗斯特效应（Drosteeffect）是指一张图片的某个部分与整张图片相同，如此产生无限循环。它是递归的一种视觉形式。2.1递归

2.1.1递归的概念【定义】若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。2.1.1递归的概念2.1.1递归的概念二叉树：二叉树是数据元素的有穷集合，它或者为空集（空二叉树），或者由一个根元素和其下的两棵互不相交的二叉左子树和右子树构成。单链表结点：

typedefstructnode {datatypedata

structnode*Link; }slnode2.1.2递归的应用能采用递归解决的问题通常有这样的特征：为求解规模为N的问题，设法将它分解成一些规模较小的问题，这些规模较小的问题也能采用同样的分解和综合方法，分解为规模更小的问题，当N=1时，能直接得到解。下面来看几个实例。582.1.2递归的应用【例1】阶乘函数

阶乘函数可递归地定义为：边界条件递归方程边界条件与递归方程是递归的二个要素59【例1】阶乘函数Factorial(n)ifn=0thenreturn1returnn*Factorial(n-1)Factorial(n)fn=f1=1fori←2tondofn=i*f1f1=fnreturnfn2.1.2递归的应用2.1.2递归的应用【例2】Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为：边界条件递归方程第n个Fibonacci数可递归地计算如下：

fibonacci(n)if(n<=1)thenreturn1returnfibonacci(n-1)+fibonacci(n-2)

斐波那契数列的递归调用树Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)2.1.2递归的应用递归算法的一般形式：p(参数表)if（递归结束条件）可直接求解步骤；-----边界条件

elsep（较小的参数）；------递归方程2.1.2递归的应用【例3】整数划分问题将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种表示称为正整数n的划分。例如，正整数6有如下不同的划分：

6；

5+1；

4+2，4+1+1；

3+3，3+2+1，3+1+1+1；

2+2+2，2+2+1+1，2+1+1+1+1；

1+1+1+1+1+1。整数划分问题：求正整数n的不同划分个数。

64(2)q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。因此，q(1,m)=1。(1)q(n,1)=1,n1;当最大加数n1不大于1时，任何正整数n只有一种划分形式，即

(4)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1≤m-1的划分组成。(3)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1≤n-1的划分组成。2.1.2递归的应用【例3】整数划分问题如果设p(n)为正整数n的划分数，难以找到递归关系。因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。2.1.2递归的应用【例3】整数划分问题如果设p(n)为正整数n的划分数，难以找到递归关系。因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。正整数n的划分数p(n)=q(n,n)。

2.1.2递归的应用【例4】Hanoi塔问题

设A,B,C是3个塔座。开始时，在塔座A上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座A上的这一叠圆盘移到塔座C上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至A,B,C中任一塔座上。2.1.2递归的应用【例4】Hanoi塔问题hanoi(n,A,B,C)ifn=1thenmove(A,1,C)elsehanoi(n-1,A,C,B)move(A,n,C)hanoi(n-1,B,A,C)

2.1.2递归的应用当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座A直接移至塔座C上即可。当n＞1时，①借C塔将A上的n-1盘子移到B塔座上；②将A上的第n个盘子移到C塔座上；③借A塔将B上的n-1盘子移到C塔座上。由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。69运行过程：⑴只有一个盘子的情况：(最简1步)⒈A---->C⑵有二个盘子的情况：(最简3步)⒈A---->B⒉A---->C⒊B---->C⑶有三个盘子的情况：(最简7步)⒈A---->C⒌B---->A⒉A---->B⒍B---->C⒊C---->B⒎A---->C⒋A---->C

2.1.2递归的应用⑶有四个盘子的情况：(最简15步)

不同的盘子数运行步骤是不一样的，它是以一种2N-1的规律来递增的。于是所以我们得出h(n)=2N-1，当n=64时，需要的时间为18446744073709551615=5849亿年2.1.2递归的应用2.1.2递归的应用

汉诺塔算法的时间复杂度计算公式如下：【例4】Hanoi塔问题该递归方程的解为O(2n)。递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。将要求解的较大规模的问题分割成k个更小规模的子问题。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=2.2分治法2.2.1分治法的基本思想2.2.1分治法的基本思想对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2.2.1分治法的基本思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2.2.1分治法的基本思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

凡治众如治寡，分数是也。

----孙子兵法2.2.2分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题；利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。DIVIDE&CONQUER(P)if(|P|<=c)thenreturnDSOLVE(P)//解决小规模的问题

elsedividePintoksmallersubinstancesP1,P2,...,Pk

//分解问题

fori←1tokdosi←DIVIDE&CONQUER(Pi)//递归的解各子问题

S←COMBINE(s1,...,sk)//将各子问题的解合并为原问题的解

returnS}2.2.3分治法的基本步骤将一个问题分成大小相等的k个子问题的处理方法出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。792.2.4分治法的复杂性分析用分治法求解一个问题，所需的时间是由四部分组成：（1）子问题的个数k；（2）子问题的大小n/m；（3）把这个问题分解为子问题所需时间f(n)；（4）子问题合并为原问题所需时间f(n)。

当n等于m的幂时，通过迭代法求得该递归方程的解：2.2.4分治法的复杂性分析2.2.4分治法的复杂性分析对于T(n)=a*T(n/b)+c*nk;T(1)=c这样的递归关系，有这样的结论：当(a>bk)

T(n)=O(n^(logb(a)));

当(a=bk)

T(n)=O(nk*logn);

当(a<bk)

T(n)=O(nk);2.3分治法应用实例由分治法产生的子问题往往是原问题的较小模式，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。下面来看几个实例。83【例1】二叉查找算法给定已按升序排好序的n个元素a[1:n]，现要在这n个元素中找出一特定元素v。若找到了返回在表中的位置；否则返回NIL表示查找不成功。分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。2.3.1二叉查找算法842.3.1二叉查找算法【实例】已知序列A={5，7，12，25，34，37，43，46，58，80，92，105}，要求查找v=46。第一步：设定i=1，j=12mid=└(i+j)/2┘=6v=46>A[mid]=37第二步：设定i=7,j=12mid=└(i+j)/2┘=9v=46<A[mid]=58第三步:设定i=7,j=8mid=└(i+j)/2┘=7v=46>A[mid]=43第四步：设定i=8,j=8mid=└(i+j)/2┘=8v=46=A[mid]=46返回8，找到。下取整若要查找35呢？【例1】二叉查找算法伪代码BinarySearch描述算法：BinarySearch(A,v,low,high)whilelow<=highdomid←(low+high)/2ifv=A[mid]thenreturnmidelseifv>A[mid]thenlow←mid+1elsehigh←mid-1returnNIL算法复杂度分析86【例1】二叉查找算法A={5，7，12，25，34，37，43，46，58，80，92，105}二叉查找算法的运行过程可以形成是一棵二叉判定树。试一下运行过程，查找v=25v=5763124597128101158374392468010512572534在含有n个不同元素的集合中同时找出最大值和最小值。MAXMIN(A)max←min←A[1]fori←2tondoifA[i]>maxthenmax←A[i]elseifA[i]<minthenmin←A[i]returnmax&min2.3.2找最大值与最小值【例2】【问题】最好情况下，最坏情况下，时间复杂度是？【例2】找最大值与最小值将分治策略应用于此问题，每次将问题分解为大致相等的两部分，分别找出最大最小值，再将这两个子问题的解组合成原问题的解。当每个子序列只含有1个或2个元素时，视为分解结束。子序列依次两两合并找出较长序列的最大最小值，直到合并成原始序列。【例2】找最大值与最小值给定元素集A={5，4，6，3，8}用分治算法找出最大值和最小值。第一步：i=1,j=5mid=(1+5)/2=3第二步：i=1,j=3mid=(1+3)/2=2第三步：i=1,j=2

比较一次得到gmax=5,gmin=4第四步：i=3,j=3得到hmax=hmin=6边界第五步：i=1,j=3

比较gmax和hmax

比较gmin和hmin

得到fmax=6，fmin=4第六步：i=4，j=5

比较一次，得到hmax=8,hmin=3第七步：i=1，j=5

比较得到全序列fmax=8，fmin=3【例2】找最大值与最小值合并【例2】找最大值与最小值Rec_MAXMIN(i,j,fmax,fmin)ifi=jthenfmax←fmin←A[i]ifi=(j-1)thenif(A[i]>A[j])thenfmax←A[i]fmin←A[j]elsefmax←A[j]fmin←A[i]【例2】找最大值与最小值elsemid←(i+j)/2Rec_MAXMIN(i,mid,gmax,gmin)Rec_MAXMIN(mid+1,j,hmax,hmin)fmax←max(gmax,hmax)fmin←min(gmin,hmin)【例2】找最大值与最小值该算法元素比较次数即时间复杂度递归方程为：2.3.3Strassen矩阵乘法【例3】两个n×n的矩阵A和B的乘积矩阵C中的元素C[i,j]定义为:

依此定义来计算矩阵A和B的乘积矩阵C，则每计算C的一个元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩阵C的n2个元素所需的计算时间为O(n3)。矩阵相乘传统方法：O(n3)【例3】Strassen矩阵乘法使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：传统方法：O(n3)分治法:由此可得：复杂度分析T(n)=O(n3)【例3】Strassen矩阵乘法传统方法：O(n3)分治法:为了降低时间复杂度，必须减少乘法的次数。复杂度分析T(n)=O(nlb7)=O(n2.81)较大的改进【例3】Strassen矩阵乘法【例3】Strassen矩阵乘法传统方法：O(n3)分治法:O(n2.81)更快的方法??在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是O(n2.376)是否能找到O(n2)的算法？992.3.4整数相乘【例4】请设计一个有效的算法，可以进行两个n位整数的乘法运算小学的方法：O(n2)

效率太低分治法:X=Y=X=a10n/2+bY=c10n/2+d

XY=ac10n+(ad+bc)10n/2+bd

abcd复杂度分析T(n)=O(n2)

没有改进【例4】整数相乘请设计一个有效的算法，可以进行两个n位大整数的乘法运算小学的方法：O(n2)

效率太低分治法:XY=ac10n+(ad+bc)10n/2+bd

为了降低时间复杂度，必须减少乘法的次数。XY=ac10n+((a-b)(d-c)+ac+bd)10n/2+bdXY=ac10n+((a+b)(c+d)-ac-bd)10n/2+bd复杂度分析T(n)=O(nlb3)=O(n1.59)

较大的改进细节问题：两个XY的复杂度都是O(nlb3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。101【例4】整数相乘【例4】整数相乘请设计一个有效的算法，可以进行两个n位大整数的乘法运算小学的方法：O(n2)

效率太低分治法:O(n1.59)

较大的改进更快的方法??如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换(FastFourierTransform)的产生。该方法也可以看作是一个复杂的分治算法。在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。覆盖一个2k×2k棋盘要用到多少个L型骨牌？怎么放置骨牌？2.3.5棋盘覆盖【例5】当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1子棋盘(a)所示。递归地使用这种分割，直至棋盘简化为棋盘1×1。

【例5】棋盘覆盖2.3.6归并排序【例6】基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。【例】已知初始序列如下：（49，38，65，97，76，13，27）请利用归并排序让其升序有序。【例6】归并排序归并的递归过程可以消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]107【例6】归并排序基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。

MergeSort(A,p,r)if(p<r)//至少有2个元素

thenq←(p+r)/2//取中点

MergeSort(A,p,q)MergeSort(A,q+1,r)Merge(A,p,q,r)复杂度分析T(n)=O(nlbn)渐进意义下的最优算法归并两个已排好序的子序列Merge(A,p,q,r)n1←q-p+1n2←r-qcreatearraysL[1..n1+1]andR[1..n2+1]fori←1ton1doL[i]←A[p+i-1]forj←1ton2doR[j]←A[q+j]L[n1+1]←∞R[n2+1]←∞i←1j←1归并两个已排好序的子序列fork←ptordoifL[i]<R[j]thenA[k]←L[i]i←i+1elseA[k]←R[j]j←j+1时间复杂度分析：Merge过程的运行时间O(n)归并排序复杂性最坏时间复杂度：O(nlbn)平均时间复杂度：O(nlbn)辅助空间：O(n)【基本思想】对给定的初始数组a通常存在多个长度大于1的已自然排好序的子数组段，将这些自然有序子数组段找出来，然后将相邻的排好序的子数组段两两合并，构成更大的排好序的子数组段；继续合并相邻排好序的子数组段，直至整个数组已排好序。自然归并排序【例6】归并排序【练习】利用归并排序使序列A={5,2,4,7,1,3,2,6}升序有序。排序过程演示：S1:{5，2，4，7}{1，3，2，6}S2:{5，2}{4，7}{1，3}{2，6}S3:{5}{2}{4}{7}{1}{3}{2}{6}S4:{2，5}{4，7}{1，3}{2，6}S5:{2,4,5,7}{1,2,3,6}S6:{1,2,2,3,4,5,6,7}2.3.7快速排序【例7】【基本思想】对输入的数组a[p:r]，按以下三个步骤进行排序：（2）递归求解：通过递归调用快速排序算法分别对A[p:q-1]和A[q+1:r]进行排序。（3）合并：由于对A[p:q-1]和A[q+1:r]的排序是就地进行的，所以在A[p:q-1]和A[q+1:r]都已排好的序后不需要执行任何计算，A[p:r]就已排好序。（1）划分：以A[r]（或A[p]）为基准元素将A[p:r]划分为3段A[p:q-1],A[q]和A[q+1:r]，使得A[p:q-1]中任何一个元素小于等于A[q],A[q+1:r]中任何一个元素大于等于A[q]。下标q在划分过程中确定。【例7】快速排序【例】初始序列｛38，14，58，26，31｝，请利用快速排序使其升序有序。【例7】快速排序在快速排序中，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。QuickSort(A，p,r)if(p<r)q←Partition(A,p,r)QuickSort(A,p,q-1)//对左半段排序

QuickSort(A,q+1,r)//对右半段排序

【例7】快速排序

Partition(A，p,r)x←A[r]//基准元素i←p-1forj←ptor-1doifA[j]<=xtheni←i+1exchangeA[i]↔A[j]exchangeA[i+1]↔A[r]returni+1快速排序示例初始

[722657884280724860]1：[26574248]60[80728872]2：[2642]48[57]60[80728872]3：[26]42485760[80728872]4：2642485760[72]72[8088]5：2642485760[72]72[80]886：[264248576072728088]快速排序可能会对相等值的记录改变相对顺序，所以是不稳定排序算法。【例7】快速排序快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。最坏时间复杂度：O(n2)平均时间复杂度：O(nlbn)辅助空间：O(n)或O(lbn)RANDOMIZED-PARTITION(A,p,r)i←RANDOM(p,r)exchangeA[r]↔A[i]returnPARTITION(A,p,r)【例7】快速排序【练习】已知初始序列如下：（49，38，65，97，76，13，27）请利用快速排序让其升序有序。2.3.8线性时间选择【例8】【元素选择问题】给定线性序集中n个互不相同元素和一个整数i，1≤i≤n，要求找出这n个元素中第i小的元素。【例】已知序列A={2,8,9,10,1,5,3,20,6,12,35,14,18},要求找出第8小元素。2.3.8线性时间选择【例8】【元素选择问题】给定线性序集中n个互不相同元素和一个整数i，1≤i≤n，要求找出这n个元素中第i小的元素。

RandomizedSelect(A,p,r,i)if(p==r)thenreturnA[p]q←RandomizedPartition(A,p,r)k=q-p+1ifi=kthenreturnA[q]elseif(i<k)thenreturnRandomizedSelect(A,p,q-1,i)elsereturnRandomizedSelect(A,q+1,r,i-k)在最坏情况下，算法RandomizedSelect需要O(n2)计算时间但可以证明，算法RandomizedSelect可以在O(n)平均时间内找出n个输入元素中的第i小元素。方法一将n个输入元素划分成

n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。递归调用select来找出这n/5

个元素的中位数。如果

n/5

是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。【例8】线性时间选择方法二122

Select(A,p,r,i)1.将n个元素分成

n/5个组，每组5个元素，另一组由剩余的nmod5个元素组成。2.利用任一种排序算法对

n/5个组进行排序，并找出每组元素的中值。

3.对第2步找出的

n/5个中值，利用select递归找出这

n/5个中值的中值x4.利用修改的partition过程，以中值的中值作为划分元素，对输入数组进行划分。设k是划分后左半部分元素数再加上1。因此，x是第k小元素，且右半部分有n-k个元素。

5如果i=k，则返回x；如果i<k，则利用select在划分的左半部分找第i个最小元素；如果i>k，则在右半部分找第i-k个最小元素。复杂度分析T(n)=O(n)【例8】线性时间选择【例】已知序列A={2,8,9,10,1,5,3,20,6,12,35,14,18},要求找出第8小元素。2.3.9最接近点对问题【例9】【最接近点对问题】给定n(n≥2)个点的集合Q，找集合Q中一对点p1，p2，使得它们的距离在欧氏距离意义下最小。集合中的两个点有可能重合，在这种情况下，这两个点的欧氏距离为0。应用在交通控制系统中，来检测可能发生的碰撞。【例9】最接近点对问题先来考虑一维的情形：S中n个点化为x轴上的n个实数x1,x2,…,xn。最接近点对即为这n个实数中相差最小的2个实数。假设我们用x轴上某个点m将S划分为2个子集S1和S2，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并设d=min{|p1-p2|,|q1-q2|}，S中的最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2。能否在线性时间内找到p3,q3？S1={x∈S|x≤m}；S2={x∈S|x>m}【例9】最接近点对问题如果S的最接近点对是{p3,q3}，即|p3-q3|<d，则p3和q3两者与m的距离不超过d，即p3∈(m-d,m]，q3∈(m,m+d]。复杂度分析T(n)=O(nlbn)【例10】循环赛日程表有n=2k个运动员进行网球循环赛，设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用z这种对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。1234567821436587341278564321876556781234658721437856341287654321学习要点理解递归的概念。掌握设计有效算法的分治策略。通过下面的范例学习分治策略设计技巧。（1）二分搜索技术；（2）找最大值与最小值；（3）Strassen矩阵乘法；（4）整数相乘；（5）归并排序和快速排序；（6）线性时间选择；（7）最接近点对问题；（8）循环赛日程表。练习1.若总是以待排序列的最后一个元素作为基准元素进行快速排序，那么最好情况下的时间复杂度是（）

A.O(lbn)B.O(n)C.O(nlbn)D.O(n2)2.若对27个元素只进行三趟多路归并排序，则选取的归并路数是（）

A.2B.3C.4D.53.某算法的计算时间可以用递推式T(n)=2T(n/2)+n表示，则该算法的时间复杂度为

A.O(lbn)B.O(nlbn)C.O(n)D.O(n2)练习4.算法的有穷性指的是（）。

A.算法程序的运行时间是有限的

B.算法程序所处理的数据是有限的

C.算法程序的长度是有限的

D.算法只能被有限的用户使用练习对于给定的一组关键字（18，2，16，30，8，28，4，10，20，6，12），按照下列算法进行递增排序，写出每种算法第一趟排序后得到的结果：快速排序（选最后一个记录为基准元素）得到__5__，二路归并排序得到__6__。(5)A.10,6,18,8,4,2,12,20,16,30,28

B.4,2,6,10,8,12,28,30,20,16,18

C.2,8,4,10,612,16,30,20,18,28

D.6,10,8,28,20,18,2,4,12,30,16(6)A.2,12,16,8,28,30,4,6,10,18,20

B.2,12,16,30,8,28,4,10,6,20,18

C.12,2,16,8,28,30,4,6,10,28,18

D.12,2.10,20,6,18,4,16,30,8,28

7.将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较()次。A.i

B.n-1

C.n

D.2n8.对n个元素进行快速排序时，最坏情况下的时间复杂度为()。A．O(1og2n)

B．O(n)

C．O(nlog2n)

D．O(n2)练习练习9.根据Hanoi问题的分治解决算法，将下列程序补充完整。#include<iostream.h>(1);voidmain(){intm;cout<<"ThisApplicationistoHanoiproblem"<<endl;cout<<"Inputthenumberofplates"<<endl;

(2);cout<<"Thestepofmovingis:"<<endl;hanoi(m,'A','B','C');}练习voidhanoi(intn,charone,chartwo,charthree){if((3))cout<<"from"<<one<<"to"<<three;else{(4);cout<<"from"<<one<<"to"<<three;

(5);}}练习10.设A[0..n-1]是一个已经排好序的数组。请改写二分查找算法，使得当查找元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当查找元素在数组中时，i和j相同，均为x在数组中的位置。作业2-11，2-121.求整数5的划分个数2.A={12，2，16，30，8，28，4，10，20，6}用分治法找出A中的最大和最小值。3.分别使用归并排序和快速排序使下述序列升序有序A={12，2，16，30，8，28，4，10，20，6}。4.利用线性时间选择算法，求下列序列中的第8小元素。A={2,6,18,1,4,10,20,6,22,13,9,5,24,3,7,12,16,11,20,28,23,14,15,21,125,34,19}5.阅读下面C代码，回答问题1至3。【说明】采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排好序的子数组得到排序结果。下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下：arr:待排序数组p,q,r：一个子数组的位置从p到q，另一个子数组的位置从q+1到r作业begin，end：待排序数组的起止位置left，right：临时存放待合并的两个子数组n1，n2：两个子数组的长度i,j,k：循环变量mid：临时变量作业【C代码】#include<stdio.h>#include<stdlib.h>#defineMAX655536voidmerge(intarr[],intp,intq,intr){int*left,*right;intn1,n2,I,j,k;n1=q-p+1;n2=r-q;作业for(i=0;i<n1;i++){left[i]=arr[p+i];}left[i]=MAX;for(i=0;i<n2;i++){right[i]=arr[q+i+1];}right[i]=MAX;作业i=0;j=0;for(k=p;(1);k++){if(left[i]>right[j]){(2);j++;}作业else{arr[k]=left[i];i++;}}}voidmergesort(intarr[],intbegin,intend){intmid;if((3)){作业mid=(begin+end)/2;mergesort(arr,begin,mid);(4);merge(arr,begin,mid,end);}}【问题一】根据以上说明和C代码，填充1-4。作业144通过应用范例学习动态规划算法设计策略（1）斐波那契数列；（2）0-1背包问题；（3）矩阵连乘问题；（4）最长公共子序列；（5）最优二分检索树；（6）装配线调度问题；（7）凸多边形最优三角剖分；（8）最大子段和问题。145动态规划（DynamicProgramming）1957年，RichardBellman创造了这个名字该方法利用表格技术，用多项式复杂度代替指数复杂度。典型应用是组合优化问题，求解最优值和最优解。146动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=147但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)148如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)149学习内容3.1用表代替递归3.2

0-1背包问题3.3矩阵链乘问题3.4动态规划算法的基本要素3.5备忘录方法3.6装配线调度问题3.7最长公共子序列问题3.8最优二分检索树3.9凸多边形的最优三角剖分1503.1用表代替递归1.动态规划与分治法比较2.动态规划基本步骤1513.1用表代替递归【例1】有一对兔子，从第三个月起每个月都生一对小兔子，然后小兔子长到三个月时也生一对小兔子，假设所有兔子都成活。问每个月的兔子总数有多少对