搜索
1本科实验报告课程名称：分算法设计与分析实验项目：分治法合并排序贪心法作业调度动态规划法求多段图问题回溯法求n皇后问题实验地点：行勉楼B209专业班级：软件14**班学号：201400****学生姓名：******指导教师：******2016年4月10日2实验1分治法合并排序一、实验目的1.掌握合并排序的基本思想2.掌握合并排序的实现方法3.学会分析算法的时间复杂度4.学会用分治法解决实际问题二、实验内容随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。三、实验环境Window7;惠普笔记本；VC++6.0.四、算法描述和程序代码#includeiostream#includestdio.h#includetime.husingnamespacestd;#definerandom(x)(rand()%x);inta[10];//合并排序函数。voidMerge(intleft,intmid,intright){intt[11];inti=left,j=mid+1,k=0;while((i=mid)&&(j=right)){if(a[i]=a[j])t[k++]=a[i++];elset[k++]=a[j++];}while(i=mid)t[k++]=a[i++];while(j=right)t[k++]=a[j++];for(i=0,k=left;k=right;)a[k++]=t[i++];}//分划函数，并且调用合并函数。voidMergeSort(intleft,intright){if(leftright){intmid=((left+right)/2);MergeSort(left,mid);3MergeSort(mid+1,right);Merge(left,mid,right);//调用合并函数。}}voidmain(){inti;cout排序前的数组为：;for(i=0;i10;i++){a[i]=random(100);//调用random函数，产生10个0-100的随机数。couta[i];}coutendl;MergeSort(0,9);cout排序后的数组为：;for(i=0;i10;i++){couta[i];}getchar();}五、实验结果截图六、实验总结分治算法是很有用的算法，分治法的设计一般是递归的。两路合并排序是一个典型的分治算法，其基本运算为元素比较，最坏情况下的时间为W(n)=O(nlogn)，在排序过程中需要使用与原序列相同长度的辅助数组temp，因此它所需的额外空间为O(n)。通过编写代码，我很好的掌握了分治法的步骤：划分；求解子问题；合并。对“分治策略”有了更深的体会，它将原问题划分为彼此独立的、规模较小而结构相同的子问题。4实验2贪心法作业调度一、实验目的1.掌握贪心算法的基本思想2.掌握贪心算法的典型问题求解3.进一步多级调度的基本思想和算法设计方法4.学会用贪心法分析和解决实际问题二、实验内容设计贪心算法实现作业调度，要求按作业调度顺序输出作业序列。如已知n=8，效益p=(35,30,25,20,15,10,5,1)，时间期限d=(4,2,4,5,6,4,5,7)，求该条件下的最大效益。三、实验环境Window7;惠普笔记本；VC++6.0.四、算法描述和程序代码#includeiostreamusingnamespacestd;constintWork[8]={35,30,25,20,15,10,5,1};//所有作业按收益从大到小排序constintmaxTime[8]={4,2,4,5,6,4,5,7};classHomeWork{private:intres[8];boolflag[8];intmaxReap;public:voiddealWith(){//遍历所有作业:inti;for(i=0;i8;i++){intTime=maxTime[i]-1;if(!flag[Time]){//如果最大期限那一天还未安排作业,则将当前作业安排在所允许的最大期限那天res[Time]=Work[i];flag[Time]=true;}else{//如果当前作业所允许的最大期限那一天已经安排的其他作业,就向前搜索空位,将该作业安排进去for(intj=Time-1;j=0;j--)5if(!flag[j]){res[j]=Work[i];flag[j]=true;break;}}}cout作业完成顺序为:;for(i=0;i7;i++){coutres[i]\t;}coutendl;coutendl最佳效益为:;intj;for(j=0;j7;j++)maxReap+=res[j];coutmaxReapendl;}HomeWork(){inti;for(i=0;i8;i++)flag[i]=false;maxReap=0;}};voidmain(){HomeWorka=HomeWork();a.dealWith();getchar();}五、实验结果截图六、实验总结通过实验编写代码使得我对应用贪心法求解问题有了很大的提高。贪心法是一种求解组合优化问题的算法设计技术，其求解过程由一些列决策构成。贪心算法的关键在于贪心策略，两要素是：最优子结构和贪心策略，对带时限的作业进行排序是一个典型的贪心算法，在本次实验中我使用了改进后的可行解判定方法来解决这个问题，使算法的时间从Θ(n2)减少到接近O(n)。6实验3动态规划法求多段图问题一、实验目的1.掌握动态规划算法的基本思想2.掌握多段图的动态规划算法3.选择邻接表或邻接矩阵方式来存储图4.分析算法求解的复杂度二、实验内容设G=(V,E)是一个带权有向图，其顶点的集合V被划分成k2个不相交的子集Vi，1i=k，其中V1和Vk分别只有一个顶点s（源）和一个顶点t（汇）。图中所有边的始点和终点都在相邻的两个子集Vi和Vi+1中。求一条s到t的最短路线。参考课本P124图7-1中的多段图，试选择使用向前递推算法或向后递推算法求解多段图问题。三、实验环境Window7;惠普笔记本；VC++6.0.四、算法描述和程序代码#includeiostreamusingnamespacestd;struct{intr[50];intlength;}SqList,L;voidMSort(intSR[],intTR1[],ints,intt);7voidMerge(intsR[],intTR[],inti,intmid,intn);voidmain(){cout请输入待排序的数目:;cinL.length;cout请输入待排序的数:;for(intc=0;cL.length;c++)cinL.r[c];cout合并排序前的数组为:;for(intd=0;dL.length;d++)coutL.r[d];coutendl;MSort(L.r,L.r,0,L.length-1);cout合并排序后的数组为:;for(inti3=0;i3L.length;i3++)coutL.r[i3];coutendl;}voidMSort(intSR[],intTR1[],ints,intt)//两路合并排序{intmid;intTR2[100];if(s==t)TR1[s]=SR[s];else//若序列的长度超过1，则划分为两个子序列{mid=(s+t)/2;//将待排序的序列一分为二MSort(SR,TR2,s,mid);//对左子序列排序MSort(SR,TR2,mid+1,t);//对右子序列排序Merge(TR2,TR1,s,mid,t);//将两个有序子序列合并成一个有序序列}}voidMerge(intSR[],intTR[],inti,intmid,intn)//将两个有序序列合并成一个有序序列{intj,k;for(j=mid+1,k=i;i=mid&&j=n;++k){if(SR[i]=SR[j])TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i=mid)//如果左子序列还有元素未输出，则将左子序列剩余元素依次输出{8intk1=k;for(inti1=i;i1=mid;i1++){TR[k1]=SR[i1];k1++;}}if(j=n)//如果右子序列还有元素未输出，则将右子序列剩余元素依次输出{intk2=k;for(intj2=j;j2=n;j2++){TR[k2]=SR[j2];k2++;}}}五、实验结果截图六、实验总结通过这次实验使得我对应用动态规划法求解问题有了很大的提高。动态规划算法将原问题归约为规模较小、结构相同的子问题，建立原问题与子问题优化函数间的依赖关系，从规模较小的子问题开始，利用上述依赖关系求解规模更大的子问题，直到得到原始问题的解为止。采用逐步向前递推的方式，由子问题的最优解来计算原问题的最优解。算法所用空间除邻接矩阵和最优解path以外，还需要长度为n的cost和d两个局部以为数组。这一算法的时间分析与DFS和BFS相似，总的执行时间为Θ(n)9实验4回溯法求n皇后问题一、实验目的1.掌握回溯算法的基本思想2.通过n皇后问题求解熟悉回溯法3.使用蒙特卡洛方法分析算法的复杂度二、实验内容要求在一个8*8的棋盘上放置8个皇后，使得它们彼此不受“攻击”。两个皇后位于棋盘上的同一行、同一列或同一对角线上，则称它们在互相攻击。现在要找出使得棋盘上8个皇后互不攻击的布局。三、实验环境Window7;惠普笔记本；VC++6.0.四、算法描述和程序代码#includeiostreamusingnamespacestd;#defineN8intres[100][8];intcountRes=0;boolPlace(intk,inti,int*x){for(intj=0;jk;j++)if(x[j]==i||abs(x[j]-i)==abs(j-k))returnfalse;returntrue;}voidNQueen(intk,intn,int*x){for(inti=0;in;i++)if(Place(k,i,x)){x[k]=i;if(k==n-1){for(i=0;in;i++){res[countRes][i]=x[i];coutx[i]\t;}countRes++;coutendl;}else{NQueen(k+1,n,x);}}}10voidNQueen(intn,int*x){NQueen(0,n,x);}intmain(){intx[N];for(inti=0;iN;i++)*(x+i)=-10;NQueen(N,x);coutendl共countRes种解endl;charshow;cout是否显示图示?(Y/N)endl;cinshow;if(show=='Y'||show=='y'){for(intn=0;ncountRes;n++){cout第n+1个解:endl;for(inti=0;iN;i++){for(intj=0;jN;j++){if(res[n][i]==j)coutQ\t;elsecout*\t;}coutendl;}}}return0;}五、实验结果截图11六、实验总结通过这次试验我对皇后问题的知识点有了很大的了解，编写代码和调试代码的能力有所提高。在算法设计策略中，回溯法是比贪心法和动态规划法更一般的方法。n皇后问题以检查两皇后是否冲突作为基本运算，该算法的最坏情形复杂性为O(3n×2nn)=O(nn+1)。n皇后问题有n!个叶子节点，遍历时间为Ω（n！）。