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

《太原理工大学算法与分析实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、r){inti=l,j=m+Uk=l;while((i<=m)&&(j<=r))if(a[i]<=a[j])b[k++]二a[i++];elseb[k++]=a[j++];讦(i>m)for(intq=j;q<=r;q++)b[k++]=a[q];elsefor(intq=i;qv=m;q++)b[k++]=a[q];}voidCopy(intaf],intb[],ints,intn){for(inti=s;i<=n;i++)a[i]=b[i];}voidMergeSort(inta[],intleft,intright){in

3、ti;if(left

4、t(a,0,n-1);for(i=0;i

5、)。通过编写代码，我很好的掌握了分治法的步骤：划分；求解子问题；合并。对“分治策略”有了更深的体会，它将原问题划分为彼此独立的.规模较小而结构相同的子问题。四.算法描述和程序代码#include#include"math.h"usingnamespacestd;intmain(){intwf100]={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(w[i]>w[j]){t=w[i];w[i]

6、=w[jj；w[j]=t;}}for(inti=0;wnwmax){wn■二w[num-l];num—;}cout«"bestanswer:"«endl;for(inti=0;i

7、问题的算法设计技术，其求解过程由一些列决策构成。贪心算法的关键在于贪心策略,两要素是：最优子结构和贪心策略，对带时限的作业进行排序是一个典型的贪心算法，在本次实验中我使用了改进后的可行解判定方法来解决这个问题，使算法的时间从0(112)减少到接近O(n)。实验3动态规划法求多段图问题一、实验目的1.掌握动态规划算法的基本思想2.掌握多段图的动态规划算法3.选择邻接表或邻接矩阵方式来存储图4.分析算法求解的复杂度二、实验内容设G二(V,E)是一个带权有向图，其顶点的集合V被划分成k>2个不相交的子集Vi,Ki<=k,其中VI和Vk

8、分别只有一个顶点s(源)和一个顶点t(汇)。图中所有边的始点和终点都在相邻的两个子集Vi和Vi+1中。求一条s到t的最短路线。参考课本P124图7・1屮的多段图，试选择使用向前递推算法或向后递推算法求解多段图问题。三、实验环境WindowlO华硕笔记本电脑；De