高中信息技术 全国青少年奥林匹克联赛教案 分治法二VIP免费

分治法课题：分治法目标：知识目标：分治的原理与分治的实现能力目标：分治的原理重点：分治的应用难点：分治的理解板书示意：1）分治的引入（例29）2）分治的应用（例30）授课过程：所谓分治法就是将问题分而治之。有将问题一分为二，也有将问题一分为三或一分为N等份。对每一等份分别进行解决后，原问题就可以很快得以解决。因此一个问题能否用分治法解决，关键是看该问题是否能将原问题分成n个规模较小而结构与原问题相似的子问题。递归的解决这些子问题，然后合并其结果就得到原问题的解。当n=2时的分治法又称二分法。使用分治策略的问题常常要借助递归的结构，逐层求解，当问题规模达到某个简单情况时，解容易直接得出，而不必继续分解。其过程大致如下：if问题不可分thenbegin直接求解；返回问题的解；endelsebegin从原问题中划出含1/n运算对象的子问题1；递归调用分治法过程，求出解1；从原问题中划出含1/n运算对象的子问题2；递归调用分治法过程，求出解2；…………从原问题中划出含1/n运算对象的子问题n；递归调用分治法过程，求出解n；将解1、解2、……、解n组合成整个问题的解；end;根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？大量实践发现：在用分治法设计算法时，最好是子问题的规模大致相同。通常可以采取二分法，因为这么划分即简单而且均匀。使子问题规模相等的做法是出自平衡子问题的思想，一般情况下总是比子问题规模不等的做法要有效。例29：归并排序某数列存储在对序列A[1]，A[2]，……，A[n]，现采用归并思想进行排序。分析：这里我们采用二分法。先将n个元素分成两个各含或（）个元素的子序列；再用归并排序法对两个子序列递归的排序；最后合并两个已排序的子序列以得到排序结果。在对子序列排序时，当其长度为1时递归结束。单个元素被视为是已经排好的序列。下面我们来分析一下对两个已排好序的子序列A[P．．Q]和A[Q+1．．R]，将它们合并成一个已排好的子序列[P．．R]。引入一个辅助过程merge（A，P，Q，R）来完成这一合并工作，其中A是数组，P，Q，R是下标。其方法是：每次选两个子序列中较小的一个元素加入到目标序列中，直到某一个子序列为空，最后把另一子序列中剩下的元素加入到目标序列中。procedureMerge(varA:ListType;P,Q,R:Integer);{将A[P．．Q]和A[Q+1．．R]，合并到序列A[P．．R]}varI,{左子序列指针}J,{右子序列指针}T:Integer;{合并后的序列的指针}Lt:ListType;{暂存合并的序列}beginT:=P;I:=P;J:=Q+1;whileT<=Rdobegin{合并未完成}{若左序列剩有元素并且右序列元素全部合并或左序列的首元素小于等于右序列的首元素，则左序列的首元素进入合并序列}if(I<=Q)and((J>R)or(A[I]<=A[J]))thenbeginLt[t]:=A[I];Inc(I);endelsebegin{否则右序列的首元素进入合并序列}Lt[t]:=A[J];Inc(J);end;Inc(T);{合并后的序列的指针右移}end;A:=Lt;{合并后的序列赋给A}end;下面我们来看看分治过程。利用merge_sort（A，P，R）对数组A[P．．R]进行排序。若P=R,则子序列只有一个元素，分解完毕。否则，计算出中间下标Q,将A[P．．R]分成A[P．．Q]和A[Q+1．．R]。若数组A[P．．R]的元素个数K=R-P+1为偶数，则两个数组各含K/2个元素；否则A[P．．Q]含个元素，A[Q+1．．R]含个元素。procedureMerge_Sort(varA:ListType;P,R:Integer);varQ:Integer;beginifP<>Rthenbegin{若子序列A中不止一个元素}Q:=(P+R-1)div2;{计算中间下标Q}Merge_Sort(A,P,Q);{继续对左子序列A[P．．Q]递归排序}Merge_Sort(A,Q+1,R);{继续对左子序列A[Q+1．．R]递归排序}Merge(A,P,Q,R){对左子序列和右子序列归并排序}end;end;用Merge_sort（A，1，N）便可对整个序列进行归并排序。如果我们自底向上来看这个过程的操作时，算法将两个长度为1的序列合并成排好序的长度为2的序列，继而合并成长度为4的序列……，依次类推。随着算法自底向上执行，被合并的排序序列长度逐渐增加，一直进行到将两个长度为n/2的序列合并成最终排好序的长度为n的序列。图25列出了对序列（5，2，4，6，2，3，2，6）进行归并排序的过程。图25二分法归并示例图例30：剔除多余括号（CTSC94-1）键盘输入一...