递归与分治策略

第2章递归与分治策略实验2分治算法的递归程序实现与时间复杂度测试1.实验目的编程实现合并排序和快速排序算法，理解分治算法设计的基本思想、递归程序实现的基本方法，加深对分治算法设计与分析思想的理解。通过程序的执行时间测试结果，与理论上的时间复杂度结论进行对比、分析和验证。2.原理解析分治算法的基本思想分治算法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。分治算法设计的一般步骤包括：(1)分解，将要解决的问题划分成若干规模较小的同类问题；(2)求解，当子问题划分得足够小时，用较简单的方法解决；(3)合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。分治法的基本设计范式如下：DivideAndConquer(data,n,solution)if(n≤SizeLimit)thenDirectSolution(data,n,solution)elseDivideInput(data,n,smallerSets,smallerSizes,numberSmaller)fori=1tonumberSmallerdoDivideAndConquer(smallerSets[i],smallerSizes[i],smallerSolution[i])endforCombineSolutions(smallerSolution,numberSmaller,solution)endif测试算法不同问题的分治算法在分解与合并步骤可能有所不同，例如合并排序和快速排序这两个有代表性的分治算法中，合并排序算法没有分解、只有合并，快速排序算法没有合并、只有分解；这两个算法的计算时间分别取决于合并与分解步骤。这两个算法分别如下：1、MergeSort(list,first,last)iffirstlastthenmiddle=(first+last)/2MergeSort(list,first,middle)MergeSort(list,middle+1,last)MergeLists(list,first,middle,middle+1,last)endifMergeLists(list,start1,end1,start2,end2)while(start1≤end1)and(start2≤end2)doiflist[start1]list[start2]thenresult[indexC]=list[start1]start1=start1+1elseresult[indexC]=list[start2]start2=start2+1endifindexC=indexC+1endwhileifstart1≤end1thenfori=start1toend1doresult[indexC]=list[i]indexC=indexC+1endforelsefori=start2toend2doresult[indexC]=list[i]indexC=indexC+1endforindexC=1fori=finalStarttofinalEnddolist[i]=result[indexC]indexC=indexC+1endfor2、QuickSort(list,first,last)iffirstlastthenpivot=PivotList(list,first,last)QuickSort(list,first,pivot-1)QuickSort(list,pivot+1,last)endifPivotList(list,first,last)PivotValue=list[first]PivotPoint=firstforindex=first+1tolastdoiflist[index]PivotValuethenPivotPoint=PivotPoint+1Swap(list[PivotPoint],list[index])endifendforSwap(list[first],list[PivotPoint]returnPivotPoint以上两个算法具有O(nlogn)的时间复杂度。3.实验内容(1)编程实现以上两个用于排序的分治算法，使用生成的随机数作为测试数据。对每个算法，记录随着测试数据增加算法基本操作执行次数，分析并以图形方式展现增长率；对于两个理论上均为最优的排序算法，对比随着测试数据增加算法增长率变化趋势；测试、验证、对比算法的时间复杂度。4.实验步骤和要求(1)“比较”是以上两个排序算法的基本操作，在算法中设置比较操作执行的全局计数器，编程实现算法（输出最终的计数值）。快速排序packagecom.ntz.text;importjava.util.Scanner;publicclassText{publicstaticvoidmain(String[]args){quicksortqs=newquicksort();inti,N;Scannerscanner=newScanner(System.in);N=scanner.nextInt();int[]A=newint[N];for(i=0;iN;i++){A[i]=(int)(Math.random()*100);}qs.data=A;//将该数组赋值给快速排序的数组qs.sort(0,qs.data.length-1);//调用排序方法qs.display();//显示排序后的记录}}classquicksort{intm=0;publicintdata[];privateintpartition(intsortArray[],intlow,inthigh){intkey=sortArray[low];//关键字通常设置为序列的第一项while(lowhigh){while(lowhigh&&sortArray[high]=key)//判断记录右侧是否有小于关键字的记录high--;//如果没有，则移动右侧的指针sortArray[low]=sortArray[high];//如果有则交换while(lowhigh&&sortArray[low]=key)//判断记录左侧是否有大于关键字的记录low++;//如果没有，则移动左侧的指针sortArray[high]=sortArray[low];//如果有则交换}sortArray[low]=key;//排序的终止条件是左侧指针和右侧指针重合，即low=highreturnlow;}publicvoidsort(intlow,inthigh){if(lowhigh){intresult=partition(data,low,high);sort(low,result-1);sort(result+1,high);}m++;}publicvoiddisplay(){for(inti=0;idata.length;i++)//利用循环，输出排列后的序列{System.out.print(data[i]);System.out.print();}System.out.println();System.out.println(次数为：+m);}}归并排序packagecom.ntz.text;importjava.util.Arrays;importjava.util.Scanner;publicclassText{privatestaticintm=0;publicstaticvoidmerge(int[]a,intlow,intmid,inthigh){int[]temp=newint[high-low+1];inti=low;//左指针intj=mid+1;//右指针intk=0;//把较小的数先移到新数组中while(i=mid&&j=high){if(a[i]a[j]){temp[k++]=a[i++];}else{temp[k++]=a[j++];}}while(i=mid){temp[k++]=a[i++];}while(j=high){temp[k++]=a[j++];}for(intk2=0;k2temp.length;k2++){a[k2+low]=temp[k2];}}publicstaticvoidmergeSort(int[]a,intlow,inthigh){intmid=(low+high)/2;if(lowhigh){//左边mergeSort(a,low,mid);//右边mergeSort(a,mid+1,high);//左右归并merge(a,low,mid,high);}m++;}publicstaticvoidmain(String[]args){intN;Scannerscanner=newScanner(System.in);N=scanner.nextInt();int[]a=newint[N];for(inti=0;iN;i++){a[i]=(int)(Math.random()*100);}mergeSort(a,0,a.length-1);System.out.println(排序结果：+Arrays.toString(a));System.out.println(次数为+m);}}设置记录每次递归调用时描述问题规模的变量，程序结束时输出其值。通过测试保证程序正确无误。注意递归程序的实现、调试和测试。随机生成10个数据的快速排序归并排序(2)使用实验1中的随机数生成方法生成不同规模的测试数据（10个，100个，1000个，2000个，5000个，10000个，100000个，……）。1010010002000500010000100000归并排序67083217134382886689031快速排序87282317354375878588763对于每种规模的测试数据，分别记录以上两个算法执行中各子问题的规模，并用表格方式记录所有情形各子问题的规模值。对于每种规模的测试数据，分别记录MergeSort和QuickSort算法执行中比较操作的次数，使用MSExcel图表绘制工具生成随着输入数据增加、以上两个算法比较操作执行次数增加的对比曲线图（折线）。5.实验总结此次实验通过编程实现合并排序和快速排序算法，理解分治算法设计的基本思想、递归程序实现的基本方法，加深对分治算法设计与分析思想的理解，其本质就是将难以直接解决的大问题，分割成若干规模较小的相同问题，在计算机处理当中，问题的规模越小越容易直接求解，解题所需的计算时间也越少，所以分治法在合适的问题中能大大提高效率！