《算法设计与分析教学资料》第2章

第2章递归与分治策略编辑ppt

学习要点:理解递归的概念。掌握设计有效算法的分治策略。通过下面的范例学习分治策略设计技巧。（1）二分搜索技术；（2）大整数乘法；（3）Strassen矩阵乘法；（4）棋盘覆盖；（5）合并排序和快速排序；（6）线性时间选择；（7）最接近点对问题；（8）循环赛日程表。编辑ppt分治法概述分治法是一种非常有用的算法技术，它可以用于求解许多算法问题.什么是分治法?编辑ppt算法总体思想

计算机求解的复杂度与问题的规模有关，回忆：1、2、3……n个元素的排序问题；1、2、3……n个元素的查找问题；结论：多个元素的排序和查找比较少元素的排序和查找复杂和困难的多！想法：能否将“多个元素的排序和查找”变成数个“较少元素的排序和查找”，分别进行？？？编辑ppt算法总体思想

分治法的可行性：如果原问题可以分成k个子问题且子问题都可解并可利用子问题的解求出原问题的解编辑ppt算法总体思想

问题分解是求解复杂问题时很自然的做法。求解一个复杂问题可以将其分解成若干个子问题，子问题还可以进一步分解成更小的问题，直到分解所得的小问题是一些基本问题，并且其求解方法是已知的，可以直接求解为止。编辑ppt将要求解的较大规模的问题分割成k个更小规模的子问题。算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=

对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。编辑ppt算法总体思想对这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)

将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。编辑ppt算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。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)编辑ppt算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。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)

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

----孙子兵法

编辑ppt算法总体思想

通常，由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。由此可知，分治法求解很自然地可用一个递归过程来表示。分治法作为一种算法设计策略，要求分解所得的子问题是同类问题，并要求原问题的解可以通过组合子问题的解来获取。编辑ppt2.1递归的概念直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。编辑ppt2.1递归的概念递归的使用场合：数据结构本身是递归定义的，其实现算法往往是递归算法，比如二叉树和图等；求解过程需要递归，算法描述简捷其易于理解及分析，比如阶乘计算下面来看几个实例。在算法设计中使用递归技术，往往使算法的描述简单明了、易于理解、容易编程和验证。在计算机软件领域，递归算法是一种非常重要并且不可或缺的算法。编辑ppt2.1递归的概念例1阶乘函数

阶乘函数可递归地定义为：边界条件：非递归定义的初始值递归方程：递归定义式边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。较小自变量的函数值表示较大自变量的函数值编辑ppt2.1递归的概念例1阶乘函数

第n个阶乘可递归地计算如下：intfactorial(intn){if(n==0)return1;returnn*factorial(n-1);}编辑ppt2.1递归的概念例2Fibonacci数列（斐波那契数列）无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为：边界条件递归方程第n个Fibonacci数可递归地计算如下：intfibonacci(intn){

if(n<=1)return1;

return

fibonacci(n-1)+fibonacci(n-2);}数列的第n项的值是它前面两项之和编辑ppt2.1递归的概念例3Ackerman函数（阿克曼函数）当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman函数A(n，m)定义如下--有两个独立的整型变量m、n：编辑ppt2.1递归的概念例3Ackerman函数前2例中的函数都可以找到相应的非递归方式定义：本例中的Ackerman函数却无法找到非递归的定义。编辑ppt2.1递归的概念例3Ackerman函数A(n，m)的自变量m的每一个值都定义了一个单变量函数（根据m的不同可得到基于n的不同函数！）：m=0时，A(n,0)=n+2m=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*nm=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)=2^n。m=3时，类似的可以推出m=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。编辑ppt2.1递归的概念例3Ackerman函数定义单变量的Ackerman函数A(n)为，A(n)=A(n，n)。定义其拟逆函数α(n)为：α(n)=min{k｜A(k)≥n}。即α(n)是使n≤A(k)成立的最小的k值。因为：A(0)=1,A(1)=2,A(2)=4,A(3)=16所以：α(1)=0，α(2)=1，α(3)=α(4)=2α(5)=…α(16)=3α(n)在复杂度分析中常遇到。对于通常所见到的正整数n，有α(n)≤4。但在理论上α(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。编辑ppt2.1递归的概念例3Ackerman函数作业1：采用递归方式实现Ackerman函数编辑ppt2.1递归的概念例4排列问题设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。从n个不同元素中任取m(m≤n)个元素，按照一定的顺序排列起叫做从n个不同元素中取出m个元素的一个排列，当m=n时所有的排列情况叫全排列。如1,2,3三个元素的全排列为：

1，2，3 1，3，2

2，1，3 2，3，1 3，1，2 3，2，1集合X中元素的全排列记为perm(X)。(r)perm(X)表示在全排列perm(X)的每一个排列前加上前缀r得到的排列。编辑ppt2.1递归的概念例4排列问题设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。集合X中元素的全排列记为perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：

当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。

编辑ppt2.1递归的概念例4排列问题(/view/1710135.htm)n=2perm(R):(r1)perm(R1)(r2)perm(R2)

即：(r1)(r2)(r2)(r1)当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。

n=3perm(R):(r1)perm(R1)(r2)perm(R2)(r3)perm(R3)即：(r1)perm(R2R3)(r2)perm(R1R3)(r3)perm(R1R2)最终：(r1)(r2)（r3)(r1)(r3)(r2)(r2)(r1)(r3)(r2)(r3)(r1)(r3)(r1)(r2)(r3)(r2)(r1)

编辑ppt2.1递归的概念例4排列问题//perm函数：perm(Object[]list,intk,intm)//作用：输出数组list中，前缀为顺序的前k个元素，后缀为后m-k个元素的全排列，所组成的排列//参数：list数组，要进行排列的元素//k，数组下标0-（k-1）为前缀//m，数组下标0-m为要进行排列的元素//说明：若要对list中的所有元素进行排列，k应为0，m应为数组上界

编辑ppt2.1递归的概念例4排列问题 publicstaticvoidperm(Object[]list,intk,intm) { //若所有要排列元素都为前缀，则依次输出

if(k==m){ for(inti=0;i<=m;i++) System.out.print(list[i]+""); System.out.println(); }//否则，前缀增1，后缀减1 else{//依次将原后缀中任一个元素放入到前缀中，得到新的前后缀，进行递归

for(inti=k;i<=m;i++){ swap(list,k,i); perm(list,k+1,m); swap(list,k,i); } } }编辑ppt2.1递归的概念例4排列问题 publicstaticvoidswap(Object[]list,intk,intm) { Objectt; t=list[k]; list[k]=list[m]; list[m]=t; }intmain(){intlist[]={1,2,3};perm(list,0,2);return0;}编辑ppt2.1递归的概念例4排列问题作业2：采用递归方式实现排列问题编辑ppt2.1递归的概念例5整数划分问题将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。例如正整数6有如下11种不同的划分：

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。编辑ppt2.1递归的概念例5整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。注意：m的取值范围为[1,∞)，我们可分段讨论。①m=1②1<m<n③m=n④m>n编辑ppt(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递归的概念例5整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。编辑ppt2.1递归的概念例5整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。

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。例：q(6,3)=q(3,3)+q(6,2)编辑ppt2.1递归的概念例5整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。正整数n的划分数p(n)=q(n,n)。

编辑ppt2.1递归的概念例5整数划分问题//函数：q(intn,intm)//作用：用来得到正整数n，最大加数不大于m的划分个数publicstaticintq(intn,intm){

//若正整数或最大加数小于1，则返回0 if(n<1||m<1)return0;

//若正整数或最大加数等于1，则划分个数为1（n个1相加）

if(n==1||m==1)return1;

//若最大加数实际上不能大于正整数n，若大于则划分个数等于最大加数为n的划分个数

if(n<m)returnq(n,n);

//若正整数等于最大加数，则划分个数等于

if(n==m)return1+q(n,n-1); returnq(n,m-1)+q(n-m,m);}

编辑ppt2.1递归的概念例5整数划分问题作业3：采用递归方式实现整数划分问题编辑ppt2.1递归的概念例6Hanoi塔问题设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。编辑ppt2.1递归的概念例6Hanoi塔问题一个简单的解法：假设塔座a,b,c排成一个三角形，a→b→c→a构成一顺时针循环。在移动圆盘的过程中，若是奇数次移动，则将最小的圆盘移动到顺时针方向的下一个塔座上；若是偶数次移动，则保持最小的圆盘不动，而在其他两个塔座之间，将较小的圆盘移动到另一个塔座上去。以上算法如何理解？注意：圆盘数目不同，要ab，塔座的顺序也不同。 奇数：a→b→c→a

偶数：a→c→b→a编辑ppt非递归解法若是奇数次移动，则将最小的圆盘移到顺时针方向的下一塔座上；若是偶数次移动，则保持最小的圆盘不动，而在其他两个塔座之间，将较小的圆盘移到另一塔座上去。当n为奇数时，目的塔座是b，按顺时针方向移动；当n为偶数时，目的塔座是c，按逆时针方向移动。编辑ppt在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。当n＞1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。2.1递归的概念例6Hanoi塔问题

publicstaticvoidhanoi(intn,inta,intb,intc)//将塔座a上自下而上，由大到小叠放在一起的n个圆盘依移动规//则移至塔座b上并仍按同样顺序叠放。{

if(n>0){

hanoi(n-1,a,c,b);//在移动过程中，以塔座c作为辅助塔座

move(a,b);//将塔座a上编号为n的圆盘移至塔座b上

hanoi(n-1,c,b,a);}}编辑ppt2.1递归的概念例6Hanoi塔问题作业4：画图表示Hanoi塔问题关键：为算法建立递归调用工作栈编辑ppt2.1递归的概念通常，在一个算法中调用另一算法时，系统需在运行被调用算法之前先完成三件事：（1）将所有实参指针、返回地址等信息传递给被调用算法；（2）为被调用算法的局部变量分配存储区；（3）将控制转移到被调用算法的入口。在从被调用算法返回调用算法时，系统也相应地要完成三件事：（1）保存被调用算法的计算结果；（2）释放分配给被调用算法的数据区；（3）依照被调用算法保存的返回地址将控制转移到调用算法。系统在实现子程序的调用时,要用栈方式管理调用子程序时的返回地址。子程序调用的内部实现为两个方面。编辑ppt2.1递归的概念当有多个算法构成嵌套调用时，按照后调用先返回的原则进行。注意：信息传递和控制转移必须通过栈来实现。重要的是数据栈和工作栈。递归算法的实现类似于多个算法的嵌套调用，只不过调用算法和被调用算法是同一个算法。为了保证递归调用正确执行，系统要建立一个递归调用工作栈，为各层次的调用分配数据存储区。一个递归过程的执行类似于多个子程序的嵌套调用,递归过程是自己调用自己本身代码。如果把每一次的递归调用视为调用自身代码的复制件,则递归实现过程基本上和一般子程序的实现相同。编辑ppt递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。编辑ppt解决方法：在递归算法中消除递归调用，使其转化为非递归算法。1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显（常用方法！）。2、用递推来实现递归函数。3、通过变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。递归小结编辑ppt讨论：找出n个自然数(1,2,...,n)中取r个数的组合。编辑pptinta[100];voidcomb(intm,intk){for(inti=m;i>=k;i--){a[k]=i;if(k>1)comb(i-1,k-1);else{for(intj=a[0];j>0;j--)cout<<a[j]<<'';cout<<endl;}}}intmain(){intn=5,r=3;a[0]=r;comb(n,r);}n=5，r=3时，从大到小排列的组合数为：

543 542 541 532 531 521 432 431 421 321编辑ppt分治法的基本思想基本思想当要求解一个输入规模n相当大的问题时，直接求解往往是非常困难的，甚至没法求出。正确的方法是,首先应仔细分析问题本身所具有的特性，然后根据这些特性选择适当的设计策略来求解。在将这n个输入分成k个不同子集合的情况下，如果能得到k个不同的可独立求解的子问题，而且在求解之后，还可找到适当的方法把它们合并成整个问题的解，那么，可考虑使用分治法来求解。编辑ppt分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。边界条件：非递归定义的初始值递归方程：递归定义式编辑pptdivide-and-conquer(P)—分而治之{

if(|P|<=n0)adhoc(P);//解决小规模的问题

dividePintosmallersubinstancesP1,P2,...,Pk；//分解问题

for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//递归的解各子问题

returnmerge(y1,...,yk);//将各子问题的解合并为原问题的解

}分治法的基本步骤人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。编辑ppt分治法的复杂性分析（了解）一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：通过迭代法求得方程的解：注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当mi≤n<mi+1时，T(mi)≤T(n)<T(mi+1)。

编辑ppt主定理注意：主定理的三种情况并没有覆盖所有f(n)，存在某些f(n)不满足以上任何一种情况的条件，则此时就不能用主方法求解递推试。编辑ppt采用分治法求解问题通常得到一个递归算法，分析相应算法的时间复杂性，往往可得到如下的递归式：T(n)=kT(n/m)+cnb,T(1)=c显然可以直接使用主方法得到如下定理：编辑ppt例：T(n)=16T(n/4)+nT(n)=T(3n/7)+1T(n)=7T(n/2)+n2编辑ppt分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分析：比较x和a的中间元素a[mid]，若x=a[mid]，则x在L中的位置就是mid；如果x<a[mid]，由于a是递增排序的，因此假如x在a中的话，x必然排在a[mid]的前面，所以我们只要在a[mid]的前面查找x即可；如果x>a[i]，同理我们只要在a[mid]的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。

分析：很显然此问题分解出的子问题相互独立，即在a[i]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。二分搜索技术（回忆查找算法）给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。编辑ppt二分搜索技术给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。据此容易设计出二分搜索算法（注意：C++程序！程序有问题吗？？？）：template<classType>intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。编辑pptpublicstaticintbinarySearch(int[]a,intx,intn){//在a[0]<=a[1]<=...<=a[n-1]中搜索x//找到x时返回其在数组中的位置，否则返回-1intleft=0;intright=n-1;

while(left<=right){intmiddle=(left+right)/2;

if(x==a[middle])returnmiddle;

if(x>a[middle])left=middle+1;

elseright=middle-1;}

return-1;//未找到x}二分搜索技术编辑ppt大整数的乘法

考虑《计算机组成原理》课程中关于基本运算的说法：1.加法和乘法是基本运算，Why?2.减法和除法如何实现？3.如果实现加法和乘法的计算数超过了机器表示的范围，Howtodo?4.精确表示运算时，必须用软件来实现！大整数运算面临的问题：（1）直接以整数运算，可能超出硬件整数表示范围。（2）若以浮点数表示，不能精确的表示大整数及其运算结果。所以，采用某种算法来实现大整数运算是非常必要的。编辑ppt大整数（二进制整数）的乘法

请设计一个有效的算法，可以进行两个n位大整数的乘法运算小学的方法：O(n2)效率太低分治法（a、b、c、d分段均为n/2位！并假设n为2的幂数！）:X=Y=X=a2n/2+bY=c2n/2+d(why?)

XY=ac2n+(ad+bc)2n/2+bd

（式1）abcd复杂度分析T(n)=O(n2)没有改进将每2个1位数的乘法或加法看作一步运算关键：减少乘法次数！编辑ppt大整数的乘法

请设计一个有效的算法，可以进行两个n位大整数的乘法运算小学的方法：O(n2)效率太低分治法:一种改进方法XY=ac2n+(ad+bc)2n/2+bd

为了降低时间复杂度，必须减少乘法的次数。XY=ac2n+((a-c)(b-d)+ac+bd)2n/2+bd（式3）XY=ac2n+((a+c)(b+d)-ac-bd)2n/2+bd（式4）复杂度分析T(n)=O(nlog3)=O(n1.59)较大的改进递归方程组解的渐进阶的求法——套用公式法细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。编辑ppt大整数的乘法编辑ppt大整数的乘法编辑ppt大整数的乘法编辑ppt大整数的乘法

请设计一个有效的算法，可以进行两个n位大整数的乘法运算小学的方法：O(n2)效率太低分治法:O(n1.59)较大的改进更快的方法??如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换(FastFourierTransform)的产生。该方法也可以看作是一个复杂的分治算法。/skyivben/archive/2008/07/23/1248413.html编辑pptStrassen矩阵乘法

若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩阵C的个元素所需的计算时间为O(n3)传统方法：O(n3)编辑pptStrassen矩阵乘法使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：传统方法：O(n3)分治法:由此可得：复杂度分析T(n)=O(n3)（式2）（式3）（式4）（式5）关键：减少乘法次数！编辑pptStrassen矩阵乘法传统方法：O(n3)分治法:为了降低时间复杂度，必须减少乘法的次数。复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改进编辑pptStrassen矩阵乘法编辑pptStrassen矩阵乘法传统方法：O(n3)分治法:O(n2.81)更快的方法??Hopcroft和Kerr已经证明(1971)，计算2个２×２矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究３×３或５×５矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是O(n2.376)是否能找到O(n2)的算法？编辑ppt棋盘覆盖在一个2k×2k

个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。编辑ppt棋盘覆盖在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。问题：在任何一个2k×2k的棋盘覆盖中，用到的L型骨牌个数是多少？（4k-1）/3个！！！编辑ppt棋盘覆盖考虑：使用分治策略，求解棋盘覆盖问题当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1

子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。

编辑ppt下面讨论棋盘覆盖问题中数据结构的设计。（1）棋盘：可以用一个二维数组board[size][size]表示一个棋盘，其中，size=2k。为了在递归处理的过程中使用同一个棋盘，将数组board设为全局变量；（2）子棋盘：整个棋盘用二维数组board[size][size]表示，其中的子棋盘由棋盘左上角的下标tr、tc和棋盘大小s表示；（3）特殊方格：用board[dr][dc]表示特殊方格，dr和dc是该特殊方格在二维数组board中的下标;

（4）L型骨牌：一个2k×2k的棋盘中有一个特殊方格，所以，用到L型骨牌的个数为(4k-1)/3，将所有L型骨牌从1开始连续编号，用一个全局变量t表示。编辑pptdcdrtrtcsize棋盘覆盖问题中的数据结构棋盘覆盖问题编辑pptpublic

classChess{private

int[][]board;//用来表示棋盘private

intboardSize;//表示棋盘的大小为2的多少次方private

intdr,dc;//棋盘中特殊方格的位置（行号、列号）private

inttile;//骨牌标号publicChess(){board=new

int[1][1];dr=0;dc=0;boardSize=0;}编辑pptpublicChess(intr,intc,ints){intn;n=(int)Math.pow(2,s);if(n<=r||n<=c)System.out.println("初始化参数错误！");else{board=new

int[n][n];dr=r;dc=c;boardSize=s;}}编辑pptpublic

voidPrint(){for(inti=0;i<Math.pow(2,this.boardSize);i++){for(intj=0;j<Math.pow(2,this.boardSize);j++)System.out.print(String.format("%3d|",this.board[i][j]));System.out.println();}}public

static

voidmain(String[]args){Chessc1=newChess(3,4,3);c1.chessBoard(0,0,c1.dc,c1.dr,(int)Math.pow(2,c1.boardSize));c1.Print();}编辑ppt//函数参数说明：//tr：棋盘左上角方格的行号；//tc：棋盘左上角方格的列号；//dr：特殊方格所在的行号；//dc：特殊方格所在的列号；//size：2^k,棋盘规格为2^k¡Á2^k。public

voidchessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,s=size/2;//t:L型骨牌号,s分割棋盘//覆盖左上角子棋盘if(dr<tr+s&&dc<tc+s)//

特殊方格在此棋盘中

chessBoard(tr,tc,dr,dc,s);else

//此棋盘中无特殊方格则用t号L型骨牌覆盖右下角{board[tr+s-1][tc+s-1]=t;//覆盖其余方格chessBoard(tr,tc,tr+s-1,tc+s-1,s);}编辑ppt//覆盖右上角子棋盘if(dr<tr+s&&dc>=tc+s)

//特殊方格在此棋盘中

chessBoard(tr,tc+s,dr,dc,s);else

//无特殊方格，用t号骨牌覆盖左下角{board[tr+s-1][tc+s]=t; chessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆盖左下角子棋盘if(dr>=tr+s&&dc<tc+s) chessBoard(tr+s,tc,dr,dc,s);else{ board[tr+s][tc+s-1]=t; chessBoard(tr+s,tc,tr+s,tc+s-1,s);}编辑ppt//覆盖右下角子棋盘if(dr>=tr+s&&dc>=tc+s)

//特殊方格在此棋盘中

chessBoard(tr+s,tc+s,dr,dc,s);else

{ board[tr+s][tc+s]=t; chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}}编辑ppt棋盘覆盖voidchessBoard(inttr,inttc,intdr,intdc,intsize){

if(size==1)return;intt=tile++,//L型骨牌号

s=size/2;//分割棋盘

//覆盖左上角子棋盘

if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盘中

chessBoard(tr,tc,dr,dc,s);

else{//此棋盘中无特殊方格

//用t号L型骨牌覆盖右下角

board[tr+s-1][tc+s-1]=t;//覆盖其余方格

chessBoard(tr,tc,tr+s-1,tc+s-1,s);}//覆盖右上角子棋盘

if(dr<tr+s&&dc>=tc+s)//特殊方格在此棋盘中

chessBoard(tr,tc+s,dr,dc,s);

else{//此棋盘中无特殊方格

//用t号L型骨牌覆盖左下角

board[tr+s-1][tc+s]=t;//覆盖其余方格

chessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆盖左下角子棋盘

if(dr>=tr+s&&dc<tc+s)//特殊方格在此棋盘中

chessBoard(tr+s,tc,dr,dc,s);

else{//用t号L型骨牌覆盖右上角

board[tr+s][tc+s-1]=t;//覆盖其余方格

chessBoard(tr+s,tc,tr+s,tc+s-1,s);}//覆盖右下角子棋盘

if(dr>=tr+s&&dc>=tc+s)//特殊方格在此棋盘中

chessBoard(tr+s,tc+s,dr,dc,s);

else{//用t号L型骨牌覆盖左上角

board[tr+s][tc+s]=t;//覆盖其余方格

chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}复杂度分析T(n)=O(4k)渐进意义下的最优算法编辑ppt棋盘覆盖其中用一个二维整型数组board表示棋盘。Board[0][0]是棋盘的左上角方格。Tile是算法中的一个全局整型变量，用来表示L型骨牌的编号，其初始值为0。算法的输入参数是：tr:棋盘左上角方格的行号tc:棋盘左上角方格的列号dr:特殊方格所在的行号dc:特殊方格所在的列号size:size=2k棋盘规格为2k×2k

编辑ppt棋盘覆盖编辑ppt棋盘覆盖编辑ppt棋盘覆盖编辑ppt棋盘覆盖编辑ppt棋盘覆盖编辑ppt棋盘覆盖编辑ppt棋盘覆盖编辑ppt棋盘覆盖编辑ppt棋盘覆盖编辑ppt合并排序基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。voidMergeSort(Typea[],intleft,intright){

if(left<right){//至少有2个元素

inti=(left+right)/2;//取中点

mergeSort(a,left,i);

mergeSort(a,i+1,right);

merge(a,b,left,i,right);//合并到数组b

copy(a,b,left,right);//复制回数组a}}合并排序算法是用分治策略实现对n个元素进行排序的算法/wiki/%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F复杂度分析T(n)=O(nlogn)渐进意义下的最优算法编辑pptpublicstaticvoidmergeSort(Comparablea[],intleft,intright){

if(left<right){//至少有2个元素

inti=(left+right)/2;//取中点

mergeSort(a,left,i);

mergeSort(a,i+1,right);

merge(a,b,left,i,right);//合并到数组b

copy(a,b,left,right);//复制回数组a}}编辑ppt合并排序voidmergesort(inta[],intleft,intright)

{

intb[100];

if(left<right)

{

inti=(left+right)/2;

mergesort(a,left,i);

mergesort(a,i+1,right);

merge(a,b,left,i,right);//合并两个排好序的数组段到一个新的数组b中

Copy(a,b,left,right);//将合并后的数组段再复制回数组a中

}}编辑ppt合并排序voidmerge(intc[],intd[],intl,intm,intr)

{

inti=l,j=m+1,k=l;

while((i<=m)&&(j<=r))

if(c[i]<=c[j])d[k++]=c[i++];

elsed[k++]=c[j++];

if(i>m)for(intq=j;q<=r;q++)d[k++]=c[q];

elsefor(intq=i;q<=m;q++)d[k++]=c[q];

}//merge可在时间内完成

voidCopy(inta[],intb[],intm,intn)

{

for(inti=m;i<=n;i++)a[i]=b[i];

}//copy可在时间内完成编辑ppt合并排序intmain()

{

intn,m,a[100];

cin>>n;

while(n!=0)

{

cin>>m;

for(inti=0;i<m;i++)cin>>a[i];

mergesort(a,0,m-1);

for(intj=0;j<m;j++)cout<<a[j]<<'';

cout<<endl;

n--;

}

return0;

}编辑ppt合并排序算法mergeSort的递归过程可以消去。（回忆上学期的方法）初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]编辑ppt合并排序编辑ppt合并排序编辑ppt合并排序编辑ppt合并排序编辑ppt//合并排序的非递归算法//对数组a中的所有元素进行合并排序public

static

voidmergeSort(Comparablea[]){Comparable[]b=newComparable[a.length];ints=1; //合并的有序数组段的初始大小//有序数组段的长度小于数组长度继续合并while(s<a.length){//从下界开始将a中的相邻的长度为s的元素合并排序到b中mergePass(a,b,s);s+=s; //待合并的有序数组段的长度增加一倍mergePass(b,a,s);s+=s; //待合并的有序数组段的长度增加一倍

}}编辑ppt//合并大小为s的相邻子数组//从数组下界开始，将数组x中相邻的长度为s的数组段合并排序到y中public

static

voidmergePass(Comparable[]x,Comparable[]y,ints){inti=0;while(i<=x.length-2*s){//合并大小为s的相邻2段子数组x[i:i+s-1]和x[i+s:i+2*s-1]merge(x,y,i,i+s-1,i+2*s-1);i=i+2*s;}编辑ppt//剩下的元素个数小于2s，大于sif(i+s<x.length)//合并数组段x[i:i+s-1]和x[i+s:x.length-1]merge(x,y,i,i+s-1,x.length-1);//剩下的元素的个数小于selse//直接将x[i:x.length-1]复制到yfor(intj=i;j<x.length;j++)y[j]=x[j];}编辑ppt合并排序自然合并排序是合并排序算法的一种改进.一般的合并排序算法中，第一步合并相邻长度为1的子数组段，因为长度为1的子数组段是已经排好序的。自然合并排序:对于初始给定的数组,通常存在多个长度大于1的已自然排好序的子数组段.例如,若数组a中元素为{4,8,3,7,1,5,6,2},则自然排好序的子数组段有{4,8},{3,7},{1,5,6},{2}.用一次对数组a的线性扫描就足以找出所有这些排好序的子数组段.然后将相邻的排好序的子数组段两两合并,构成更大的排好序的子数组段({3,4,7,8},{1,2,5,6}).继续合并相邻排好序的子数组段,直至整个数组已排好序.考虑：合并排序、自然合并排序的时间复杂度？编辑ppt合并排序最坏时间复杂度：O(nlogn)平均时间复杂度：O(nlogn)辅助空间：O(n)编辑ppt快速排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。template<classType>voidQuickSort(Typea[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);//对左半段排序

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

}}快速排序算法是基于分治策略的另一排序算法（回忆上学期的方法）/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F#Java/view/19016.htm?fromId=115472/tjsinor2008/article/details/5617866对含有n个元素的数组a[0:n-1]进行快速排序只要调用QuickSort(a,0,n-1)即可编辑ppt快速排序template<classType>intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];//将<x的元素交换到左边区域

//将>x的元素交换到右边区域

while(true){while(a[++i]<x);while(a[--j]>x);if(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}初始序列{6,7,5,2,5,8}j--;{5,7,5,2,6,8}i++;{5,6,5,2,7,8}j--;{5,2,5,6,7,8}i++;完成{6,7,5,2,5,8}{5,2,5}6{7,8}Partition以一个确定的基准元素a[p]对子数组a[p:r]进行划分编辑ppt快速排序快速排序算法基本思想是：对输入的子数组a[p:r]，按以下三个步骤进行排序。

（1）分解（Divide）：以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在划分过程中确定。（2）递归求解（Conquer）：通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序。（3）合并（Merge）：由于对a[p:q-1]和a[q+1:r]的排序是就地进行，所以在a[p:q-1]和a[q+1:r]都已排好的序后，不需要执行任何计算，a[p:r]就已排好序。编辑ppt//qSort函数：对数组a[p:r]进行快速排序private

static

voidqSort(Comparable[]a,intp,intr){if(p<r){intq=partition(a,p,r);qSort(a,p,q-1);qSort(a,q+1,r);}}//对a[p:r]以a[p]的值为基准进行分割，得到基准元素的位置q//对分割以后的前半部分进行快速排序//对分割以后的后半部分进行快速排序编辑ppt上述算法的关键是使用partition对数组进行划分，其主要代码为：private

static

intpartition(Comparable[]a,intp,intr){inti=p,j=r+1;Comparablex=a[p];while(true){while(a[++i].compareTo(x)<0&&i<r);while(a[--j].compareTo(x)>0);if(i>=j)break;swap(a,i,j);}a[p]=a[j];a[j]=x;returnj;}编辑ppt例如：以下序列的划分过程{5，2，6，4，9，2，10，4} 0{5，2，6，4，9，2，10，4} 1{5，2，4，4，9，2，10，6} 1{5，2，4，4，9，2，10，6} 2{5，2，4，4，2，9，10，6} 2{5，2，4，4，2，9，10，6} 3{2，2，4，4}5{9，10，6} 3编辑pptpartition算法需要注意的细节：（1）保证i，j不出现下标越界

i不断增加，j不断减小，所以i可能超出数组段上界，j可能超出数组段下界，而由于比较元素处于数组段下界位置，可作为哨兵保证j不超出下界，所以对于i增加i<r条件保证其不超出上界。（2）选中基准和移动i，j是相关联的 若要以上界为基准，相应i,j移动及越界条件要进行修改编辑ppt快速排序快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程产生的两个区域分别包含n-1个元素和1个元素的时候。T(n)=T(n-1)+0(n)n>1;T(n)=0(1)

n<=1;

T（n）=O(n2)；

最好情况下，每次划分所取的基准都恰好为中值，即每次划分都产生两个大小为n/2的区域。T(n)=O(1)

n<=1;T(n)=2T(n/2)+O(n)

n>1T（n）=O(nlogn)。

可证：快排在平均情况下的时间复杂度也是O(nlogn)。编辑ppttemplate<classType>intRandomizedPartition(Typea[],intp,intr){inti=Random(p,r);Swap(a[i],a[p]);returnPartition(a,p,r);}快速排序

快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在a[p:r]中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。编辑ppt快速排序template

<class

Type>

void

RandomizedQuickSort(Type

a[],int

p,int

r)

{

if(p

<

r)

{

int

q=

RandomizedPartition(a,p,r);

RandomizedQuickSort(a,p,q-1);//对左半段排序

RandomizedQuickSort(a,q+1