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

计算机科学与技术学院算法分析与设计实验指导书2011年8月于洪编写2015年9月周应华修订目录实验一分治策略排序…………………………..…..………3实验二减治策略查找顺序表…………………..…………..5实验三动态规划求解0/1背包问题……………………….8实验四贪心算法求解最短路径问题……………………..10附录1关于文件的操作……………………………….….12附录2关于如何统计运算时间…………………………..13实验一分治策略排序实验目的1）以排序问题为例，掌握分治法的基本设计策略；2）熟练掌握合并排序算法的实现；3）熟练掌握快速排序算法的实现；4)理解常见的算法经验分析方法。实验环境计算机、C语言程序设计环境实验学时2学时实验内容与步骤1.准备实验数据要求：编写一个函数data-generate，生成2000个在区间[1,10000]上的随机整数，并将这些数输出到外部文件data.txt中。这些数作为本算法实验的输入数据。2.实现合并排序算法要求：实现mergesort算法。输入：待排数据文件data.txt；输出：有序数据文件resultsMS.txt（注：建议将此排好序的数据作为实验二的算法输入）；程序运行时间TimeMS。合并排序算法（类C语言）：/*数组A[]中包含待排元素；arrayB[]isaworkarray*/TopDownMergeSort(A[],B[],n){TopDownSplitMerge(A,0,n,B);}//iBeginisinclusive;iEndisexclusive(即：A[iEnd]不是待排元素)TopDownSplitMerge(A[],iBegin,iEnd,B[]){if(iEnd-iBegin2)//如果只有1个待排元素，返回。return;//recursivelysplitrunsintotwohalvesuntilrunsize==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:iMiddle-1]//righthalfisA[iMiddle:iEnd-1]TopDownMerge(A[],iBegin,iMiddle,iEnd,B[]){i0=iBegin,i1=iMiddle;//Whilethereareelementsintheleftorrightrunsfor(j=iBegin;jiEnd;j++){//Ifleftrunheadexistsandis=existingrightrunhead.if(i0iMiddle&&(i1=iEnd||A[i0]=A[i1])){B[j]=A[i0];i0=i0+1;}else{B[j]=A[i1];i1=i1+1;}}}CopyArray(B[],iBegin,iEnd,A[]){for(k=iBegin;kiEnd;k++)A[k]=B[k];}3.实现快速排序算法要求：实现QuickSort算法。输入：待排数据文件data.txt；输出：有序数据文件resultsQS.txt（注：建议将此排好序的数据作为实验二的算法输入）；程序运行时间TimeQS。快速排序算法（伪码）：ProcedureQuickSort(p,q)integerp,q；globaln,A(1:n)ifpqthenj←q+1Partition(p,j);//用元素A(p)划分元素表A[p:j-1]；划分后，划分元素下标由参数j带出。QuickSort(p,j-1);QuickSort(j+1,q);endifendQuickSort用元素A(m)划分元素表A[m:p-1]：Procedurepartition(m,p)integerm,p,I;globalA(m:p-1)v=A(m);I=m;looploopI=I+1untilA(I)=vrepeatloopp=p-1untilA(p)=vrepeatifIpthenA(i)A(p)elseexitendifrepeatA(m)=A(p);A(p)=v;endpartition实验报告：实验报告应包括以下内容：（1）题目；（2）2个算法的基本思想描述；（3）程序流程图；（4）给出data.txt、resultsMS.txt、resultsQS.txt三个数据文件；给出TimeMS、TimeQS的数值结果；（5）实验分析；以表或者图的形式给出这两个算法效率的经验分析结果；并和理论分析结论进行对比。（6）说明本次实验的心得体会、经验等。如果程序未通过，应分析其原因。实验二减治策略查找顺序表实验目的1）以顺序表查找问题为例，掌握减治法的基本设计策略；2）熟练掌握折半查找算法的实现；3）掌握插值查找算法的实现；4)分析实验结果。实验环境计算机、C语言程序设计环境实验学时2学时实验内容与步骤1.准备实验数据通过实验一获得的排好序的数据可作为本算法实验的输入数据。2.实现折半查找算法要求：实现binary_search算法。输入：已排序数据序列A、待查找的数据元素key；输出：数据元素key在数据序列A中的位置。折半查找算法（类C语言）：intbinary_search(intA[],intkey,intimin,intimax){while(imin=imax){intimid=midpoint(imin,imax);//找中点if(A[imid]==key)returnimid;elseif(A[imid]key)imin=imid+1;elseimax=imid-1;}//没找到returnNOT_FOUND;}3.实现插值查找算法要求：实现interp_search算法。输入：已排序数据序列A、待查找的数据元素key；输出：数据元素key在数据序列A中的位置。插值查找算法（类C语言）：intinterpolation_search(intA[],intsize,intkey){intlow=0;inthigh=size-1;intmid;while(A[high]!=A[low]&&key=A[low]&&key=A[high]){mid=low+(high-low)*((key-A[low])/(A[high]-A[low]));if(A[mid]key)low=mid+1;elseif(keyA[mid])high=mid-1;elsereturnmid;}if(key==A[low])returnlow;elsereturn-1;}实验报告：实验报告应包括以下内容：（1）题目；（2）2个算法的基本思想描述；（3）程序流程图；（4）程序输入和输出结果；（5）实验分析；以表或者图的形式给出这两个算法效率的经验分析结果；并和理论分析结论进行对比。（6）说明本次实验的心得体会、经验等。如果程序未通过，应分析其原因。实验三动态规划求解0/1背包问题实验目的1）以0/1背包问题为例，掌握动态规划算法的基本设计策略；2）掌握并实现求解0/1背包问题的动态规划算法；3)分析实验结果。实验环境计算机、C语言程序设计环境实验学时2学时实验内容与步骤1.理解0/1背包问题0/1背包问题的描述：已知有n个物品和一个承重为M的背包，物品i的重量为wi、价值为pi。现在的问题是：如果一个物品不能被分割以后部分放进背包，那么该如何装包，才能使背包中物品的价值之和为最大？这个问题可形式化地表述如下：极大化目标函数niixp1i约束条件：Mxwnii1iniwpxiii1,0,0},1,0{2.准备实验数据确定物品数目n的值，确定各物品的重量（取正整数）和价值；确定背包的承重值M（取正整数）。3.实现动态规划算法要求：实现MFKnapsack算法。输入：参数i（初次调用时为物品总数n），j（初次调用时为空包承重M）；全局变量：物品重量Weights[1..n]，价值Values[1..n]；输出：这i个物品的最优子集的价值。算法MFKnapsack(i,j)（伪码）：//另有全局变量V[0..n,0..M]存放已经解决的子问题的结果；V初始化：V[0,*]=0、V[*,0]=0，其他元素值初始化为负数。ifV[i,j]0//此问题还没有解ifjWeights[i]valueMFKnapsack(i-1,j)elsevaluemax{MFKnapsack(i-1,j),Value[i]+MFKnapsack(i-1,j-Weights[i])}V[i,j]valuereturnV[i,j]4.修改以上算法，以输出最大装包价值对应的那些装包物品。实验报告：实验报告应包括以下内容：（1）题目；（2）算法的基本思想描述；（3）程序流程图；（4）给出实验内容4所要求的算法伪码或程序清单；（5）实验分析：分析算法效率；（6）说明本次调试实验的心得体会、经验等。如果程序未通过，应分析其原因。选做实验动态规划求解最短路径问题实验目的：1）以解决最短路径问题为例，掌握动态规划的基本设计策略；2）掌握Floyd动态规划算法求解完全最短路径问题并实现；3）分析实验结果。实验环境计算机、C语言程序设计环境实验学时2学时实验内容与步骤1.准备实验数据假设算法要处理下图，需要把图数据组织存放到相应的数据结构中，如：权值矩阵floatgraph[maxsize][maxsize]。2．实现Floyd算法用Floyd算法求一个图中所有点对之间的最短距离。输入：存储图数据的权值矩阵floatgraph[maxsize][maxsize]；输出：保存到文件floyd-output1.txt。Floyd算法（类C语言）：for(k=0;kn;k++){//graph[i][j]=min{graph[i][j]},graph[i][k]+graph[k][j]for(i=0;in;i++)//每次找到最优的路径代替原来的路径for(j=0;jn;j++)if(graph[i][j]graph[i][k]+graph[k][j]){546312graph[i][j]=graph[i][k]+graph[k][j];}}实验报告实验报告应包括以下内容：（1）题目；（2）写出算法设计思想；（3）程序清单；（4）输入和输出结果；（5）对运行情况所作的分析以及本次调试程序所取的经验。如果程序未通过，应分析其原因。实验四贪心算法求解最短路径问题实验目的：1）以解决最短路径问题为例，掌握贪心算法的基本设计策略；2）掌握Dijkstra贪心法求解单源点最短路径问题并实现；3）分析实验结果。实验环境计算机、C语言程序设计环境实验学时2学时实验内容与步骤1.准备实验数据假设算法要处理下图，需要把图数据组织存放到相应的数据结构中，如：权值矩阵floatgraph[maxsize][maxsize]。2.实现Dijkstra算法以上图作为输入，利用Dijkstra贪心算法获取由结点1到其余各顶点的最短路径及长度。输入：存储图数据的权值矩阵floatgraph[maxsize][maxsize]；输出：保存到文件dijkstra-output1.txt。Dijkstra算法（类C语言）：voiddijkstra(){initialize();546312intcount=0;inti;intu;while(countnum_of_vertices){u=minimum();set[++count]=u;//u进入单源点最小生成树的顶点集mark[u]=1