分治算法word版本.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,分治法,1,分治算法,1,排序问题,2,分治算法框架,3,二分法,4,二分法变异,5,同题异策,2,1,例,6.1,排序问题,例：关键字序列：,49,38,65,97,76,13,27,49,调整为：,13,27,38,49,49,65,76,97(,从小到大,),如何实现？,A,茫然，瞬间短路；,B,从外存调入几个排序算法名称，思路也未必记得清楚，如“冒泡”，“快速”；,C,冒出某一种排序算法,(,当时就这种学得扎实,),；,D DS,课的第十章内容刷刷往外冒，像在看课件。,看懂,理解,/,背过,吃透,设计,知道,无版权的原创,3,1,例,6.1,排序问题,已学过的主要算法策略,(,思想,),枚举,贪婪,动态规划,枚举,贪婪,列出所有可行解，检验之；,理论上，攻无不克，“必杀技”；,通过一系列的局部选择来得到一个问题的解；,将问题分阶段；,贪婪策略应用于每阶段的选择；,“只顾眼前，不顾将来”。,49,38,65,97,76,13,27,49,效率低，应用效果差。,4,1,例,6.1,排序问题,-,贪婪,1,分阶段,贪婪选择性质,最优子结构性质,贪婪策略,每阶段多排一个数；,先随便选一种实现方式,49,38,65,97,76,13,27,49,第,i,阶段：将原序列的前,i,个数由小到大排列，,in,。,将第,i,个数按大小顺序插入前,(i-1),个数组成的序列中；,从前面开始排；,5,初始状态,49,38,65,97,76,13,27,49,R,0,R,1,R,2,R,3,R,4,R,5,R,6,R,7,R,8,i,=2,i,=3,38,49,65,97,76,13,27,49,i,=4,38,49,65,97,76,13,27,49,i,=5,38,49,65,76,97,13,27,49,76,i,=6,38,49,65,76,97,13,27,49,13,i,=7,38,49,65,76,97,13,27,49,27,i,=8,38,49,65,76,97,13,27,49,49,49,38,65,97,76,13,27,49,38,38,49,38,7,趟,排序,1,趟,排序,2,趟,排序,6,1,例,6.1,排序问题,-,贪婪,2,分阶段,贪婪选择性质,最优子结构性质,贪婪策略,每阶段多排一个数；,再随便选一种实现方式,49,38,65,97,76,13,27,49,第,i,阶段：序列的前,i,个数是从小到大排列的原序列中最小的,i,个数；,in,。,从剩下的,(n-i+1),个数中找出最小的数，将它与第,i,个记录交换；,先把最小的挑出来；,7,初始：,49 38 65 97 76 13 27,j,j,j,j,j,j,k,i,=1,13,49,一趟：,13,38 65 97 76 49 27,i,=2,二趟：,13 27,65 97 76 49 38,三趟：,13 27 38,97 76 49 65,四趟：,13 27 38 49,76 97 65,五趟：,13 27 38 49 65,97 76,六趟：,13 27 38 49 65 76,97,排序结束：六趟：,13 27 38 49 65 76 97,k,k,i,=6,i,=3,i,=4,i,=5,比较次数,n,-1,n,-2,n,-6,8,可以，但与贪婪,2,相似,1,例,6.1,排序问题,-,贪婪,3,分阶段,贪婪选择性质,最优子结构性质,贪婪策略,每阶段多排一个数；,第,i,阶段：将原序列中第,i,大的数，放到第,n-i+1,位置上；,a,将第,i,个数按大小顺序插入后,(i-1),个数组成的序列中；,b,比较第,1,个数与第,2,个数，若为逆序则交换；然后比较第,2,个数与第,3,个数；依次类推，直至第,i-1,个数和第,i,个数比较为止；,把大数先向下沉；,9,排序过程,1,、比较第一个记录与第二个,记录，若,关键字,为逆序,则交换；然,后比较第二个记录与第三个记录；,依次类推，直至第,n,-1,个记录和第,n,个记录比较为止,第一趟冒泡,排序,，结果关键字最大的记录被安,置在最后一个记录上。,2,、,对前,n,-1,个记录进行第二,趟冒泡排序，结果使关键字次大的,记录被安置在第,n,-1,个记录位置。,3,、,重复上述过程，直到,“在,一趟排序过程中没有进行过交换记,录的操作”,为止。,初,始,关,键,字,49,38,65,97,76,13,27,49,第,一,趟,排,序,49,38,49,97,76,97,97,13,97,97,27,97,97,49,97,38,49,65,76,13,27,49,97,38,49,65,13,27,49,76,第,二,趟,排,序,38,49,13,27,49,65,第,三,趟,排,序,38,13,27,49,49,第,四,趟,排,序,13,27,38,49,第,五,趟,排,序,13,27,38,第,六,趟,排,序,for(,j,=1;,j,n,;,j,+),if (r,j,+1,r,j,),r,j,r,j,+1 ;,for(,j,=1;,j,n,-1,;,j,+),if (r,j,+1 1;,i,-),i,;,while(,i,1),/while,i,=,n,;,i,=,k,;,Void BubbleSort(SqList&L),冒泡排序算法,初,始,关,键,字,49,38,65,97,76,13,27,49,k,=,j,;/,交换的位置,k,=1;,10,1,例,6.1,排序问题,-,贪婪,-,总结,直接插入排序,简单选择排序,冒泡排序,含“折半插入排序”,按排序依据原则：,1),插入排序：直接插入排序、折半插入排序、希尔排序,2),交换排序：冒泡排序、快速排序,3),选择排序：简单选择排序、堆排序,4),归并排序：,2-,路归并排序,5),基数排序,将无序子序列中的一,个或几个记录“,插入,”到有,序序列中，从而增加记录,的有序子序列的长度。,比较特殊,通过“,交换,”无序序列中的记录从而,得到其中,关键字最小,或,最大,的记录，并,将它,加入到有序子序列,中，以此方法增,加记录的有序子序列的长度。,从记录的无序子序列中“,选择,”,关键字最小,或,最大,的记录，并将它,加入到有序子序列,中，以此方法增,加记录的有序子序列的长度。,通过“,归并,”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。,基数排序是一种基于多关键字排序的思想，将单关键字按基数分成“多关键字”进行排序的方法。,11,1,例,6.1,排序问题,-,贪婪,-,总结,直接插入排序,简单选择排序,冒泡排序,排序方法按工作量分类：,简单的排序方法：,T(n)=O(n),插入排序，冒泡排序，直接选择排序,先进的排序方法：,T(n)=O(nlogn),快速排序，堆排序，归并排序,基数排序：,T(n)=O(d(n+rd)=O(n),含“折半插入排序”,希尔,(shell),排序比较特殊,12,1,例,6.1,排序问题,-,先进的排序方法,快速排序,堆排序,(,略,),归并排序,13,一般取第一个记录,基本思想：,任选,一个记录，以它的关键字作为“,枢轴,”，凡关键字小于枢轴的记录均移至枢轴之前，凡关键字大于枢轴的记录均移至枢轴之后。,一趟快速排序,(,一次划分,),low,high,设,Rs=52,为枢轴,例：,52,52,49,80,36,14,58,61,97,23,75,s,t,附设两个指针,low,和,high,，从,high,所指位置起向前搜索找到第一个关键字小于枢轴的关键字的记录与枢轴记录交换，然后从,low,所指位置起向后搜索找到第一个关键字大于枢轴的关键字的记录与枢轴记录交换，重复这两步直至,low=high,为止。,high,23,low,low,80,high,high,high,high,14,low,low,52,14,快速排序过程：,快速排序,首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行一趟快速排序。,无 序 的 记 录 序 列,无序记录子序列,(1),无序子序列,(2),枢轴,一次划分,分别进行一趟快速排序,有 序 的 记 录 序 列,分解,解决,合并,15,void QSort(SqList&L,int low,int high),/,对顺序表,L,中的子序列,L.rlow.high,进行快速排序,if(low high)/,长度大于,1,/QSort,pivotloc=Partition(L,low,high);,/,对,L.rlow.high,进行一次划分,QSort(L,low,pivotloc-1);,/,对低子序列递归排序，,pivotloc,是枢轴位置,QSort(L,pivotloc+1,high);/,对高子序列递归排序,第一次调用函数,Qsort,时，待排序记录序列的上、,下界分别为,1,和,L.length,。,void QuickSort(SqList&L),/,对顺序表进行快速排序,QSort(L,1,L.length);,/QuickSort,16,1,例,6.1-,快速排序,快速排序,(,复杂度,O,(,n,log,n,),),：,平均速度最大的一种排序方法；,快速排序是一种不稳定的排序；,在递归调用时需要占据一定的存储空间用来保存每一层递归调用时的必要信息。,优化：当快速排序的子数组小于某个长度时，不继续递归，直接进行插入排序。有人经验得到：最好的组合方式是当子数组长度小于,16,时，就使用插入排序。,与冒泡相似，但反应激烈。,例：设排序前的关键字序列为：,52,49,80,36,14,58,36,23,若排序后的关键字序列为：,14,23,36,36,49,52,58,80,，,则,排序方法是稳定的,。,若排序后的关键字序列为：,14,23,36,36,49,52,58,80,，,则,排序方法是不稳定的,。,17,1,例,6.1-,归并,(,合并,),排序,-,递归思路,将原始序列划分为两个子序列；,分别对每个子序列递归排序；,最后将排好序的子序列合并为一个有序序列。,分解,解决,合并,18,归并排序,-,非递归思路,归并：将两个或两个以上的有序表组合成一个新的有序表。,在内部排序中，通常采用,2-,路归并排序,。即：将两个位置相邻的记录有序子序列归并为一个记录有序序列。,初始关键字：,49 38 65 97 76 13 27,一趟归并后：,38 49 65 97 13 76 27,二趟归并后：,38 49 65 97 13 27 76,三趟归并后：,13 27 38 49 65 76 97,看成是,n,个有序的子序,列,(,长度为,1),，然后两两,归并。,得到,n,/2,个长度为,2,或,1,的有序子序列。,空间复杂度为：,O,(,n,),时间复杂度为：,O,(,n,log,2,n,),稳定,19,2,分治算法框架,-1,算法设计思想：,将整个问题分解成若干个小问题后分而治之。,如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。,分治法的基本步骤在每一层递归上都有三个步骤：,1),分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；,2),解决：若子问题规模较小而容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；,3),合并：将已求解的各个子问题的解，逐步合并为原问题的解。,20,2,分治算法框架,-2,有时问题分解后，不必求解所有的子问题，也就不必作第三步的操作。比如折半查找，在判别出问题的解在某一个子问题中后，其它的子问题就不必求解了，问题的解就是最后,(,最小,),的子问题的解。分治法的这类应用，又称为,“减治法”,。,多数问题需要所有子问题的解，并由子问题的解，使用恰当的方法合并成为整个问题的解，比如归并排序，就是不断将子问题中已排好序的解合并成较大规模的有序子集。,21,2,分治算法框架,-3,适合用分治法策略的问题：,当求解一个输入规模为,n,且取值又相当大的问题时，用蛮力策略效率一般得不到保证。若问题能满足以下几个条件，就能用分治法来提高解决问题的效率。,1),能将这,n,个数据分解成,k,个不同子集合，且得到,k,个子集合是可以独立求解的子问题，其中,1,kn,；,2),分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制；,3),求出这些子问题的解之后，就可推解出原问题的解；,22,2,分治算法框架,-4,分治法的一般递归算法设计模式如下：,Divide-and-Conquer(int n)/n,为问题规模,if,(nn,0,)/n,0,为可解子问题的规模 解子问题；,return,(,子问题的解,),；,for,(i=1;i=k;i+)/,分解为较小子问题,p,1,p,2,p,k,y,i,=Divide-and-Conquer(|P,i,|);/,递归解决,P,i,T=MERGE(y,1,y,2,.,y,k,);/,合并子问题,return,(T);,23,3,二分法,分治思想：,在算法设计中每次一个问题分解成的子问题个数一般是固定的，每个子问题的规模也是平均分配的。,二分法,当每次都将问题分解为原问题规模的一半时，称为,二分法。,二分法是分治法较常用的分解策略，数据结构课程中的折半查找、归并排序等算法都是采用此策略实现的。,24,3,例,6.2,金块问题,金块问题：老板有一袋金块,(,共,n,块,),，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。,25,算法设计,1,：,比较简单的方法是逐个进行比较查找。先拿两块比较重量，留下重的一个与下一块比较，直到全部比较完毕，就找到了最重的金子。,算法类似于一趟选择排序，算法如下：,maxmin(float a,int n),max=a1;min=a1;for(i=2 i=n i+)if(max ai)min=ai;,3,例,6.2,金块问题,-,算法设计,1,26,算法分析,1,：,算法需要,n-1,次比较才能得到,max,。最好情况是金块由小到大取出，不需要进行与,min,比较，共,n-1,次比较。最坏情况是由大到小取出，需要再经过,n-1,次比较得到,min,共,2*n-2,次比较。在平均情况下，,A(i),将有一半的时间比,max,大，因此平均比较次数是,3(n-1)/2,。,3,例,6.2,金块问题,-,算法分析,1,maxmin(float a,int n),max=a1;min=a1;for(i=2 i=n i+)if(max ai)min=ai;,27,3,例,6.2,金块问题,-,算法设计,2,算法设计,2,：,问题可简化为：在含,n,个元素的集合中寻找最大值和最小值。,用分治法（二分法）可用较少比较次数解决上述问题：,1),将数据等分为两组（两组数据可能差,1,），目的是分别选取其中的最大（小）值。,2),递归分解直到每组元素的个数,2,，可简单地找到最大（小）值。,3),回溯时，在分解的两组解中大者取大，小者取小，合并为当前问题的解。,28,算法,2,递归求取最大和最小元素,float an;,maxmin(int i,int j,float&fmax,float&fmin),int mid;float lmax,lmin,rmax,rmin;,if(i=j)fmax=ai;fmin=ai;,else if(i=j-1),if(airmax)fmax=lmax;,else fmax=rmax;if(lminrmin)fmin=rmin;,else fmin=lmin;,29,算法分析,2,：,算法,2,需要的元素比较次数是多少？,如果用,T(n),表示这个数，则导出的递归关系式是,:,当,n,是,2,的幂时，即对于某个正整数,k,，,n=2,k,，有,可以证明，任何以元素比较为基础的找最大和最小元素的算法，其元素比较下界均为 次。,因此，算法,2,在这种意义上是最优的。,30,3,例,6.3,残缺棋盘,残缺棋盘是一个有,2,k,2,k,(k1),个方格的棋盘，其中恰有,一个,方格残缺。,下图给出,k=1,时各种可能的残缺棋盘，其中残缺的方格用阴影表示。,这样的棋盘称作“三格板”，残缺棋盘问题,就是用这四种三格板覆盖更大的残缺棋盘,。在覆盖中要求：,1),两个三格板不能重叠,2),三格板不能覆盖残缺方格，但必须覆盖其他所有方格,14,号,31,3-,分析,在这种限制条件下，所需要的三格板总数为？,1),被覆盖板面积,(,除去残缺方格,),为,2,k,2,k,-1(k1),；,2),三格板之间不能重叠；,3),三格板不能覆盖残缺方格，但必须覆盖其他所有方格。,2,k,2,k,-1,3,一定是整数吗？,条件一定可以被满足吗？,32,3-k=2,时分解,分而治之,但这四个棋盘，并不都是与原问题相似且独立的子问题。,分解,以,k=2,时的问题为例，用二分法进行分解得到用双线划分的四个,k=1,的棋盘。,分治算法适用问题特点：子问题与原问题具有相似结构。,第,1,个子问题与原问题相似,(,因为残缺方格在原图的左上部，使得第一个子图中有一个残缺方格,),而右上角、左下角和右下角三个子棋盘,(,也就是图中标识为,2,、,3,、,4,号子棋盘,),，并不是原问题的相似子问题，自然也就不能独立求解。,先假设残在左上角,33,3-,使子问题相似原,构造：,把覆盖后的方格，也看作是残缺方格,(,称为“伪”残缺方格,),，这时的,2,、,3,、,4,号子问题就是独立且与原问题相似的子问题了。,使用一个号三格板,(,图中阴影,),覆盖,2,、,3,、,4,号三个子棋盘的各一个方格；,出发点：希望子问题也具有原问题的特点,(,有个残格,),；,34,当残缺方格在第,1,个子棋盘时，用号三格板覆盖其余三个子棋盘的交界方格，可使另外三个子棋盘转化为独立子问题；,当残缺方格在第,2,个子棋盘时，则首先用号三格板进行棋盘覆盖；,当残缺方格在第,3,个子棋盘时，则首先用号三格板进行棋盘覆盖；,当残缺方格在第,4,个子棋盘时，则首先用号三格板进行棋盘覆盖；,3-,推广至,k=2,其它情况,这样就使另外三个子棋盘转化为独立子问题。,35,3-,推广至,k=1,2,3,4,.,将,2,k,2,k,棋盘分割为,4,个,2,k-1,2,k-1,子棋盘,(a),所示。,特殊方格必位于,4,个较小子棋盘之一中，其余,3,个子棋盘中无特殊方格。,为将这,3,个无特殊方格的子棋盘转化为特殊棋盘，可,用一个三格板覆盖这,3,个子棋盘的会合处,，如,(b),所示，从而将原问题转化为,4,个较小规模的棋盘覆盖问题。,36,3-,递归分解终止,&,解决,递归地使用这种分割，直至棋盘简化为,，以方便解决。,b,直至棋盘简化为棋盘,11(2,0,2,0,),。,a,直至棋盘简化为棋盘,2,1,2,1,；,解决：交汇处覆盖,1,块，其它子棋盘分别覆盖,1,块。,解决：交汇处覆盖,1,块，其它子棋盘无须处理。,合并？,37,3-,核心数据结构,棋盘的标识,棋盘的规模是一个必要的信息；,只要知道其左上角的方格所在行、列号就可以标识这个子棋盘了；,残缺方格或“伪”残缺方格直接用行、列号记录。,tr,棋盘中左上角方格所在的行号。,tc,棋盘中左上角方格所在的列号。,dr,残缺方块所在的行号。,dc,残缺方块所在的列号。,size,棋盘的行数或列数。,38,3-,核心数据结构,数据结构设计：用二维数组,board ,，模拟棋盘。覆盖残缺棋盘所需要的三格板数目为：,(size,2,-1)/3,将这些三格板编号为,1,到,(size,2,-1)/3,；,将残缺棋盘三格板编号存储在数组,board ,的对应位置中，这样输出数组内容就是问题的解。,39,int,amount=0,；,int,Board100100;,main(,),int,size=1,x,y;,input(k);,for,(i=1;i=k;i+),size=size*2;,/,输入残缺块所在位置,input(x,y);,Cover(0,0,x,y,size);,Cover(int tr,int tc,int dr,int dc,int size),if,(size2)return;,int,t=+amount,；,/,使用三格板数目,int s=size/2;/,子问题棋盘大小,if,(drtr+s&dc=tr+s&dc=tr+s&dc=tc+s),Cover(tr+s,tc+s,dr,dc,s);/,覆盖,3,号,Boardtr+s-1tc+s-1=t;,Boardtr+s-1tc+s=t;,Boardtr+stc+s-1=t;,Cover(tr,tc,tr+s-1,tc+s-1,s);,Cover(tr,tc+s,tr+s-1,tc+s,s);,Cover(tr+s,tc,tr+s,tc+s-1,s);,O(4,k,)=O(4,log size,)=O(size,2,),Void OutputBoard(int size),for,(int i=0;isize;i+),for,(int j=0;jsize;j+),print(Boardij);,print(“,换行符”,);,41,3,例,6.4,循环赛日程表,设有,n,2,k,个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：,(1),每个选手必须与其他,n-1,个选手各赛一次；,(2),每个选手一天只能赛一次；,(3),循环赛一共进行,n-1,天。,按此要求可将比赛日程表设计成有,n,行和,n-1,列的表，在表中第,i,行和第,j,列处填入第,i,个选手在第,j,天所遇到的选手。,42,3,例,6.4,循环赛日程表,1,2,2,1,如果只有两人参赛，比赛日程表？,若是四个人参赛，比赛日程表？,注：,第一列为参赛运动员编号，第二列为第一天与第一列运,动员比赛的运动员编号。,1,2,3,4,2,1,4,3,3,4,1,2,4,3,2,1,分解为两个规模为,2,的子问题,43,按分治策略，将所有选手分为两组，,n,个选手的比赛日程表就可以通过为,n/2,个选手设计的比赛日程表来决定。递归地用一分为二的策略对选手进行分割，直到只剩下,2,个选手时，日程表制定就很简单。这时只要让这,2,个选手进行比赛即可。,1,2,3,4,5,6,7,8,2,1,4,3,6,5,8,7,3,4,1,2,7,8,5,6,4,3,2,1,8,7,6,5,5,6,7,8,1,2,3,4,6,5,8,7,2,1,4,3,7,8,5,6,3,4,1,2,8,7,6,5,4,3,2,1,3,例,6.4,循环赛日程表,8,个选手的比赛日程表,44,void table(int n),if(n=1)a11=1;return;,table(n/2);,copy(n);,3,例,6.4,循环赛日程表,void copy(int n),int m=n/2;,for(int i=1;i=m;i+),for(int j=1;j=m;j+),aij+m=aij+m;,ai+mj=aij+m;,ai+mj+m=aij;,将左上角递归计算出的小块,中的数字按其相对位置抄到,右下角，将右上角小块中数,字加,n/2,后按相对位置抄到左,下角，再抄到右上角。,45,4,二分法变异,但这四个子棋盘，并不都是与原问题相似且独立的子问题。,分解,以,k=2,时的问题为例，用二分法进行分解得到用双线划分的四个,k=1,的棋盘。,分治算法适用问题特点：子问题与原问题具有相似结构。,构造：,使用一个号三格板,(,图中阴影,),覆盖,2,、,3,、,4,号三个子棋盘的各一个方格；,出发点：希望子问题也具有原问题的特点,(,有个残格,),；,46,4,二分法变异,有些问题分解后，子问题不独立、不相似，而且子问题间具有较强烈的“包含”特征，无法通过简单处理消除。,将二分法惯用思路稍作变异。,47,4,最大子段和,例,5.7,求数列的最大子段和。,给定,n,个元素的整数列,(,可能为负整数,)a,1,，,a,2,，,，,a,n,，求形如,a,i,，,a,i+1,，,a,j,，,i,，,j=1,，,2,，,，,n,，,i0)return(aleft);,else return(0);,else,center=(left+right)/2;,left_sum=max_sub_sum(a,left,center);,right_sum=max_sub_sum(a,center+1,right);,s1=0;/,处理情形,3/,lefts=0;,4,最大子段和,-,算法实现,51,for(i=center;i=left;i-),lefts=lefts+ai;,if(leftss1)s1=lefts;,s2=0;rights=0;,for(i=center+1;is2)s2=rights;,if(s1+s2left_sum and right_sumleft_sum)rturn(left_sum);,if(s1+s2right_sum)return(right_sum);,return(s1+s2);,4,最大子段和,-,算法实现,52,4,例,6.5,大整数乘法,例,6.5,大整数乘法。,请设计一个有效的算法，可以进行两个,n,位大整数的乘法运算。,数据结构设计,：首先用数组存储大整数数据，再将两个乘数和积都按由低位到高位逐位存储到数组元素中。,为简化算法一个数组元素存放一位数。,53,例,6.5,方法,1,算法设计,1,：模拟竖式乘法,存储好两个高精度数据；,让两个高精度数据按位交叉相乘，并逐步累加，即可得到精确的计算结果；,用二重循环就可控制两数各位数字按位交叉相乘的过程。,54,例,6.5,方法,1,只考虑正整数的乘法，算法细节设计如下：,1),对于大整数比较方便的输入方法是，按字符型处理，两个乘数存储在字符串数组,s1,、,s2,中，计算结果存储在整型数组,a,中。,2),通过字符的,ASCII,码，数字字符可以直接参与运算，,k,位数字与,j,位数字相乘的表达式为,(s1k-48)*(s2j-48),。,3),每一次数字相乘的结果位数是不固定的，而结果数组中每个元素只存储一位数字，所以用变量,b,暂存结果，若超过,1,位数则进位，用变量,d,存储。这样每次计算的表达式为：,b=ai+(s1k-48)*(s2j-48)+d,。,55,例,6.5,方法,1,算法说明：,循环变量,j,、,k,分别是两个乘数字符串的下标；,i1:,字符串,str1,由低位到高位的位数，范围,0n1-1,；,i2:,字符串,str2,由低位到高位的位数，范围,0n2-1,；,i:,乘法正在运算的位，也是计算结果存储的位置。,56,main(),long,b,c,d;,int,i,i1,i2,j,k,n,n1,n2,a256;,char,s1256,s2256;,input(s1);input(s2);,for,(i=0;i255;i+)ai=0;,n1=strlen(s1);n2=strlen(s2);d=0;,for,(i1=0,k=n1-1;i1n1;i1+,k-),for,(i2=0,j=n2-1;i20)i=i+1;ai=ai+d mod 10;d=d/10;,n=i;,for,(i=n;i=0;i-)print(ai);,算法分析,1,：算法是以,n1,n2,代表两个乘数的位数，由算法中的循环嵌套知，算法的主要操作是乘法，算法时间复杂度是,O(n1*n2),。,57,例,6.5,方法,2,算法设计,2,：分治策略。设,X,和,Y,都是,n,位的,二进制整数,，计算它们的乘积,X*Y,。,大,整数,X,和,Y,的分段,58,例,6.5,方法,2,将,n,位的二进制整数,X,和,Y,各分为,2,段，每段的长为,n/2,位,(,为简单起见，假设,n,是,2,的幂,),；,记：,X=A*2,n/2,+B,，,Y=C*2,n/2,+D,X,和,Y,的乘积为：,X*Y=(A*2,n/2,+B)(C*2,n/2,+D),=A*C*2,n,+(AD+CB)*2,n/2,+B*D,显然问题的答案并不是,A*C*K1+B*D*K2(K1,、,K2,与,A,、,B,、,C,、,D,无关,),；,这样做并没有将问题分解成两个独立的子问题。,据乘法分配律，分解后的计算过程如下：,算法核心,59,例,6.5,方法,2,T(1)=1,T(n)=4T(n/2)+O(n),模型分析：,如果按上式计算,X*Y,，则主要进行：,4,次,n/2,位整数的乘法,(AC,，,AD,，,BC,和,BD),3,次不超过,n,位的整数加法,2,次移位,X*Y=A*C*2,n,+(AD+CB)*2,n/2,+B*D,与方法,1,相当,由此递归式迭代过程如下：,T(n),=4T(n/2)+cn,=4(4T(n/4)+cn/2)+cn,=16(T(n/8)+cn/4)+3cn/2+cn,=,=4,k,+4,k-1,*2c+4,k-2,*4c+4c2,k-1,+c2,k,=O(4,k,),=O(n,log4,),=O(n,2,),60,例,6.5,方法,2,模型改进：,如何改写,X*Y,生成式？目标？,X*Y=A*C*2,n,+(AD+CB)*2,n/2,+B*D,减少了,1,次乘法,X*Y=A*C*2,n,+(A-B)(D-C)+AC+BD*2,n/2,+B*D,看起来复杂,但它仅需做,3,次,n/2,位整数的乘法：,AC,，,BD,和,(A-B)(D-C),，,6,次加、减法和,2,次移位。由此可得,:,61,例,6.5,方法,2,用解递归方程的迭代公式法，不妨设,n=,2,k,T(n)=3T(n/2)+cn,=3(3T(n/4)+cn/2)+cn,=9(T(n/8)+cn/4)+3cn/2+cn,=,=3,k,+3,k-1,2,1,c+3,k-2,2,2,c+3,1,c2,k-1,+3,0,c2,k,=O(n,log3,),则得到,T(n)=O(n,log3,)=O(n,1.59,),。,62,MULT(X,Y,n),/X,和,Y,为,2,个小于,2,n,的整数,/,返回结果为,X,和,Y,乘积,XY,S=SIGN(X)*SIGN(Y);,/S,为,X,和,Y,的符号乘积,X=ABS(X);,Y=ABS(Y);,/X,和,Y,分别取绝对值,if,(n=1),if,(X=1 and Y=1),return(S),；,else,return(0),；,else,A=X,的左边,n/2,位,;,B=X,的右边,n/2,位,;C=Y,的左边,n/2,位,;,D=Y,的右边,n/2,位,;ml=MULT(A,C,n/2);,m2=MULT(A-B,D-C,n/2);m3=MULT(B,D,n/2);S=S*(m1*2,n,+(m1+m2+m3)*2,n/2,+m3);,return,(S);,63,“,动作成型”,“,动作成型”的障碍,知识方法的熟练和巩固,单项动作练习不足,理论知识的总结、比较,同题异策：在多个技术动作间快速转换,多项动作结合时动作变形,基本练习,5,同题异策学以致用的保障,64,没有刻意区分,策略,一种思想，提出解决问题的思路,算法,对一个,/,类具体问题的解决方法,面向具体实现，可以用任何方式描述,策略对算法有指导性,从战略高度上面向问题,在一种策略的指导下，可以有多种不同的算法实现,如排序问题，使用贪婪策略，列出,3,种有效算法,5,同题异策,“,算法,”,与,“,策略,”,65,迭代,(,递推,),枚举,贪婪,动态规划,分治,5,同题异策,“,算法,”,与,“,策略,”,66,迭代,(,递推,),中心思想：重复使用迭代,(,递推,),公式，根据变量的旧值推出新值；,适用问题：具有明确迭代公式的问题，主要是数值计算等。,5,同题异策,“,算法,”,与,“,策略,”,67,这项要求很高,贪婪,中心思想：通过一系列的局部选择来得到一个问题的解，所作的每一步选择：“只顾眼前最优，不管将来好坏”；,适用问题：,1),贪婪选择性质；,2),最优子结构性质。,动态规划,中心思想：把求解的问题分成许多阶段,/,子问题，然后按顺序求解各阶段,/,子问题；记录每个阶段决策得到的结果序列。最后阶段的解就是初始问题的解。,适用问题,：,1),最优子结构；,(,必须有,),2),无后向性；,3),子问题重叠性质。,(,体现优势,),5,同题异策,“,算法,”,与,“,策略,”,68,分治,中心思想：将整个问题分解成若干个小问题后分而治之；分解，解决，合并。,适用问题：,1),问题的规模缩小到一定程度就可容易解决；,2),问题可以分解为若干个规模较小的相似问题；,3),子问题的解可以合并为原问题的解；,4),子问题相互独立。,枚举,中心思想：枚举出问题的所有可行解，找出其中的最优解；,适用问题：其它策略难以奏效。,5,同题异策,“,算法,”,与,“,策略,”,69,对问题进行分解的策略：“分治法”与“动态规划法”,动态规划的实质：,分治算法思想,+,解决子问题冗余情况,“,分治法”与“动态规划法”都是递归思想的应用之一，是找出大问题与小的子问题之间的关系,直到小的子问题很容易解决，再由小的子问题的解导出大问题的解。,5,同题异策 算法策略的总结,70,多阶段逐步解决问题的策略：“贪婪算法”、“递推法”、“递归法”和“动态规划法”,多阶段过程就是按一定顺序,(,从前向后或从后向前等,),一定的策略,逐步解决问题的方法。,“贪婪算法”每一步根据策略得到一个结果传递到下一步，自顶向下，一步一步地作出贪心选择。,“动态规划法”则根据一定的决策,每一步决策出的不是一个结果，而只是使问题的规模不断的缩小，如果决策比较简单,是一般的算法运算,则可找到不同规模问题间的关系，使算法演变成“递推法”、“递归法”算法。,“递推法”、“递归法”更注重每一步之间的关系,决策的因素较少。,5,同题异策 算法策略的总结,71,3,算法策略的总结,全面逐一尝试：比较“枚举法”、“递归回溯法”,有这样一类问题，问题中不易找到信息间的相互关系，也不能分解为独立的子问题,似乎只有把各种可能情况都考虑到,并把全部解都列出来之后,才能判定和得到最优解。,对于规模不大的问题，这些策略简单方便,;,而当问题的计算复杂度高且计算量很大时,还是考虑“动态规划法”这个更有效的算法策略。,实现,循环次数固定的问题：通过循环嵌套枚举问题中各种可能的情况,如八皇后问题能用八重循环嵌套枚举。,不固定的问题：靠递归回朔法来“枚举”或“遍历”各种可能情况。比如,n,皇后问题只能用“递归回朔法”通过递归实现（当然可以通过栈,而不用递归）。,72,理解分治算法的概念和基本思想；,通过应用范例学习分治策略，掌握分治算法的设计步骤和基本框架；,理解各种问题的具体算法。,小结,73,