《算法分析与设计》实验指导书(8学时)

《《算法分析与设计》实验指导书(8学时)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机科学与技术学院算法分析与设计实验指导书2011年8月于洪编写2015年9月周应华修订目录实验一分治策略排序…………………………..…..………3实验二减治策略查找顺序表…………………..…………..5实验三动态规划求解0/1背包问题……………………….8实验四贪心算法求解最短路径问题……………………..10附录1关于文件的操作……………………………….….12附录2关于如何统计运算时间…………………………..13实验一分治策略排序实验目的1）以排序问题为例，掌握分治法的基本设计策略；2）熟练掌握合并排序算法的实现；3）熟

2、练掌握快速排序算法的实现；4)理解常见的算法经验分析方法。实验环境计算机、C语言程序设计环境实验学时2学时实验内容与步骤1.准备实验数据要求：编写一个函数data-generate，生成2000个在区间[1,10000]上的随机整数，并将这些数输出到外部文件data.txt中。这些数作为本算法实验的输入数据。2.实现合并排序算法要求：实现mergesort算法。输入：待排数据文件data.txt；输出：有序数据文件resultsMS.txt（注：建议将此排好序的数据作为实验二的算法输入）；程序运行时间TimeMS。合并排序算法

3、（类C语言）：/*数组A[]中包含待排元素；arrayB[]isaworkarray*/TopDownMergeSort(A[],B[],n){TopDownSplitMerge(A,0,n,B);}//iBeginisinclusive;iEndisexclusive(即：A[iEnd]不是待排元素)TopDownSplitMerge(A[],iBegin,iEnd,B[]){if(iEnd-iBegin<2)//如果只有1个待排元素，返回。return;//recursivelysplitrunsintotwohalves

4、untilrunsize==1,//thenmergethemiMiddle=(iEnd+iBegin)/2;//划分TopDownSplitMerge(A,iBegin,iMiddle,B);TopDownSplitMerge(A,iMiddle,iEnd,B);TopDownMerge(A,iBegin,iMiddle,iEnd,B);//合并；元素放到数组B中。CopyArray(B,iBegin,iEnd,A);//copythemergedrunsbacktoA}//lefthalfisA[iBegin:iMiddl

5、e-1]//righthalfisA[iMiddle:iEnd-1]TopDownMerge(A[],iBegin,iMiddle,iEnd,B[]){i0=iBegin,i1=iMiddle;//Whilethereareelementsintheleftorrightrunsfor(j=iBegin;j=iEnd

6、

7、A[i0]<=A[i1])){B[j]=A[i0];

8、i0=i0+1;}else{B[j]=A[i1];i1=i1+1;}}}CopyArray(B[],iBegin,iEnd,A[]){for(k=iBegin;k

9、ifp=vrepeatloopp=p-1untilA(p)<=vrepeatifI

10、henA(i)«A(p)elseexitendifrepeatA(m)=A(p);A(p)=v;endpartition实验报告：实验报告应包括以下内容：（1）题目；（2）2个算法的基本思想描述；（3）程序流程图；（4）给出data.txt、resultsMS.txt、res