太原理工大学算法与分析试验报告

1、本科实验报告课程名称：算法设计与分析实验项目：分治法，贪心法，动态规划法，回溯法2016年6月6日实验1分治法合并排序一、实验目的1 .掌握合并排序的基本思想2 .掌握合并排序的实现方法3 .学会分析算法的时间复杂度4 .学会用分治法解决实际问题二、实验内容随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。三、实验环境Visualc+四、算法描述和程序代码#include<iostream>usingnamespacestd;voidMerge(inta,intb,intl,intm,intr)inti=l,j=m+1,k=l;while(i&l

2、t;=m)&&(j<=r)if(ai<=aj)bk+=ai+;elsebk+=aj+;if(i>m)for(intq=j;q<=r;q+)bk+=aq;elsefor(intq=i;q<=m;q+)bk+=aq;voidCopy(inta,intb,ints,intn)for(inti=s;i<=n;i+)ai=bi;voidMergeSort(inta口,intleft,intright)inti;if(left<right)i=(left+right)/2;intb100;MergeSort(a,left,i);MergeSort(

3、a,i+1,right);Merge(a,b,left,i,right);Copy(a,b,left,right);)intmain()intt;cout<<"请输入分解的子问题的个数"<<endl;cin>>t;while(t-)inta100;intn,i;cout<<"子问题中白元素数"<<endl;cin>>n;for(i=0;i<n;i+)cin>>ai;MergeSort(a,0,n-1);for(i=0;i<n;i+)cout<<ai

4、<<''cout<<endl;)return0;)五、实验结果截图TK、实验总结分治算法是很有用的算法，分治法的设计一般是递归的。两路合并排序是一个典型的分治算法，其基本运算为元素比较，最坏情况下的时间为W(n)=O(nlogn),在排序过程中需要使用与原序列相同长度的辅助数组temp,因此它所需的额外空间为O(n)。通过编写代码，我很好的掌握了分治法的步骤：划分；求解子问题；合并。对“分治策略”有了更深的体会，它将原问题划分为彼此独立的、规模较小而结构相同的子问题。四、算法描述和程序代码#include<iostream>#include&

5、quot;math.h"usingnamespacestd;intmain()intw100=4,6,3,5,7,2,9,wn=0,wmax=26,num=0;for(inti=0;i<6;i+)for(intj=i+1;j<7;j+)intt;if(wi>wj)t=wi;wi=wj;wj=t;for(inti=0;wn<wmax;i+)wn+=wi;num+;if(wn>wmax)wn-=wnum-1;num-;cout<<"bestanswer:"<<endl;for(inti=0;i<num;i+)

6、cout<<wi<<""cout<<endl;cout<<"Thewnis"<<wn<<endl;cout<<"Themunis"<<num<<endl;return0;五、实验结果截图TK、实验总结通过实验编写代码使得我对应用贪心法求解问题有了很大的提高。贪心法是一种求解组合优化问题的算法设计技术，其求解过程由一些列决策构成。贪心算法的关键在于贪心策略，两要素是：最优子结构和贪心策略，对带时限的作业进行排序是一个典型的贪心算法

7、，在本次实验中我使用了改进后的可行解判定方法来解决这个问题，使算法的时间从©(n2)减少到接近O(n)。实验3动态规划法求多段图问题一、实验目的1 .掌握动态规划算法的基本思想2 .掌握多段图的动态规划算法3 .选择邻接表或邻接矩阵方式来存储图4 .分析算法求解的复杂度二、实验内容设G=(V,E)是一个带权有向图，其顶点的集合V被划分成k>2个不相交的子集Vi,1<i<=k,其中V1和Vk分别只有一个顶点s(源)和一个顶点t(汇)。图中所有边的始点和终点都在相邻的两个子集Vi和Vi+1中。求一条s到t的最短路线。参考课本P124图7-1中的多段图，试选择使用向前递推

8、算法或向后递推算法求解多段图问题。三、实验环境Window10华硕笔记本电脑；Dev-C+四、算法描述和程序代码#include<stdio.h>#include<stdlib.h>#include<conio.h>#include"iostream"# defineMAX100# definen12/*顶点数*/# definek5/*段数*/usingnamespacestd;intcnn;voidinit(intcost口)初始化图inti,j;for(i=0;i<13;i+)for(j=0;j<13;j+)cij=MA

9、X;)c12=9;c13=7;c14=3;c15=2;c26=4;c27=2;c28=1;c36=2;c37=7;c48=11;c57=11;c58=8;c69=6;c610=5;c79=4;c710=3;c810=5;c811=6;c912=4;c1012=2;c1112=5;)voidfgraph(intcost,intpath,intd)/使用向前递推算法求多段图的最短路径(intr,j,temp,min;for(j=0;j<=n;j+)costj=0;for(j=n-1;j>=1;j-)(temp=0;min=cjtemp+costtemp;初始化最小值for(r=0;r&

10、lt;=n;r+)(if(cjr!=MAX)(if(cjr+costr)<min)找到最小的r(min=cjr+costr;temp=r;)costj=cjtemp+costtemp;dj=temp;)path1=1;pathk=n;for(j=2;j<k;j+)pathj=dpathj-1;)intmain()(intcur=-1;intcost13,d12,bcost13;intpathk;intpath1k;cout<<"动态规划解多段图问题"<<endl;cout<<"nn"init(cost);f

11、graph(cost,path,d);cout<<"输出使用向前递推算法后的最短路径：nn"for(inti=1;i<=5;i+)(cout<<pathi<<""cout<<"n"cout<<endl<<"最短路径为长度："<<cost1<<endl;return0;五、实验结果截图匚+-s-wenjia门项目1,exe的态规划解多葭图问题输出使用向前递推算法后的影豉善径最L271012豆路径为长度二16Ppoch

12、gsexitedaFtei3-5431secondsultliretuvnualue&除按任意犍继续TK、实验总结通过这次实验使得我对应用动态规划法求解问题有了很大的提高。动态规划算法将原问题归约为规模较小、结构相同的子问题，建立原问题与子问题优化函数间的依赖关系，从规模较小的子问题开始，利用上述依赖关系求解规模更大的子问题，直到得到原始问题的解为止。采用逐步向前递推的方式，由子问题的最优解来计算原问题的最优解。算法所用空间除邻接矩阵和最优解path以外，还需要长度为n的cost和d两个局部以为数组。这一算法的时间分析与DFS和BFS相似，总的执行时间为(n)实验4回溯法求n皇后问题一

13、、实验目的1 .掌握回溯算法的基本思想2 .通过n皇后问题求解熟悉回溯法3 .使用蒙特卡洛方法分析算法的复杂度二、实验内容要求在一个8*8的棋盘上放置8个皇后，使得它们彼此不受“攻击”。两个皇后位于棋盘上的同一行、同一列或同一对角线上，则称它们在互相攻击。现在要找出使得棋盘上8个皇后互不攻击的布局。三、实验环境Window10华硕笔记本电脑；Dev-C+四、算法描述和程序代码#include<stdio.h>/*声明常量N存储行和列*/#defineN8#defineNUM8/*声明全局变量，hNN控制盘格，HNN控制输出，nN存储每一步的*纵坐标，count用于计数。*/inth

14、NN,nN,HNN;intcount=0;/*声明函数voidtryit(int,int)尝试符合条件的方法*/voidtryit(int,int);/*声明函数voidoutputArray(intN)输出数组*/voidoutputArray(intN);main()intx=0,y=0,i,j;/*初始化为零*/for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)h皿=0;tryit(x,y);printf("/其他的布局略n");printf("共有%d种布局.n",92);return(0);/*定义函数void

15、tryit(int,int)尝试符合条件的方法*/voidtryit(intx,inty)inti,j;if(count<=NUM)/*重复时跳出递归*/if(H00=1&&H14=1&&H27=1&&H35=1&&H42=1&&H56=1&&H61=1&&H73=1)&&count!=1)()else(if(x>=0&&x<=N-1&&y>=0&&y<=N-1&&hxy=0

16、)(/*对与皇后在同一行、歹u、余线上的点作出处理*/for(j=0;j<=7;j+)(if(hxj=0)hxj=x+1;if(hjy=0)hjy=x+1;if(x+j>=0&&x+j<=N-1&&y+j>=0&&y+j<=N-1&&hx+jy+j=0)hx+jy+j=x+1;if(x+j>=0&&x+j<=N-1&&y-j>=0&&y-j<=N-1&&hx+jy-j=0)hx+jy-j=x+1;if(x-j>

17、;=0&&x-j<=N-1&&y+j>=0&&y+j<=N-1&&hx-jy+j=0)hx-jy+j=x+1;if(x-j>=0&&x-j<=N-1&&y-j>=0&&y-j<=N-1&&hx-jy-j=0)hx-jy-j=x+1;)/*对皇后处的点作出标志*/hxy=-x-1;/*完成一种走法作出处理*/if(x=7)(/*转换成输出的格式*/for(i=0;i<=N-1;i+)(for(j=0;j<=N-1;j

18、+)(if(hij<0)H皿=1;elseHij=0;)count=count+1;/*输出前几种情况*/if(count<=NUM)(printf("布局%dn",count);outputArray(H);)/*对下一种走法，清楚前一次的影响*/for(i=0;i<=N-1;i+)(for(j=0;j<=N-1;j+)(if(hij=x|hij=-x|hij=-x-1)hij=0;)/*递归，尝试另一种方法*/tryit(x-1,nx-1+1);)/*未走完一次，继续下一行*/else(nx=y;tryit(x+1,0);)else(/*此路不通时，返回上一行，尝试下一种方法*/if(y>7)(/*清楚前一次影响*/for(i=0;i<=N-1;i+)(for(j=0;j<=N-1;j+)(if(hij=x|hij=-x)hij=0;)/*分情况递归*/if(x-1>=0)tryit(x-1,nx-1+1);elsetryit(0,0);)/*尝试下一格*/elsetryit(x,y+1);)/*定义函数voidoutputArray(intN)输出数组*/voidoutputArray(inthN)inti,j;for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)printf