算法设计与分析实验报告.doc

算法设计与分析实验报告指导老师:沙莎学院:信息科学与工程学院班级:计科0508姓名:戚婕学号:10完成日期:2007年12月目录实验一分治法…………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………8实验二贪心法…………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………18实验三动态规划……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………24实验四深度优先搜索………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………28实验五回溯法…………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………:当要求解一个输入规模为n,且n的取值相当大的问题时,如果问题可以分成k个不同子集合,得到k个不同的可独立求解的子问题,其中1<k≤n,而且子问题与原问题性质相同,原问题的解可由这些子问题的解合并得出。那末,对于这类问题分治法是十分有效的。掌握分治法的一般控制流程。DanC(p,q)globaln,A[1:n];integerm,p,q;//1£p£q£nifSmall(p,q)thenreturnG(p,q);elsem=Divide(p,q);//p£m<bine(DanC(p,m),DanC(m+1,q));,验证算法的时间复杂性函数。,程序中加入比较次数的计数功能,输出排序结果和比较次数。输入10组相同的数据,验证排序结果和完成排序的比较次数。与复杂性函数所计算的比较次数比较。用表格列出比较结果。给出文字分析。(low,high)//A(low;high)是一个全程数组,它含有high-low+1≥0个待排序的元素//integerlow,high;iflow<high;thenmid←,//求这个集合的分割点//callMERGESORT(low,mid)//将一个子集合排序//callMERGESORT(mid+1,high)//将另一个子集合排序callMERGE(low,mid,high)//归并两个已排序的子集合//endifendMERGESORT归并两个已排序的集合procedureMERGE(low,mid,high)//A(low:high)是一个全程数组////辅助数组B(low;high)//integerh,i,j,k;h←low;i←low;j←mid+1;whileh≤midandj≤highdo//当两个集合都没取尽时//ifA(h)≤A(j)thenB(i)←A(h);h←h+1elseB(i)←A(j)