太原理工大学算法设计与分析实验报告资料.doc

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

1、本科实验报告课程名称：分算法设计与分析实验项目：分治法合并排序贪心法作业调度动态规划法求多段图问题回溯法求n皇后问题实验地点：行勉楼B209专业班级：软件14**班学号：****学生姓名：******指导教师：******2016年4月10日11实验1分治法合并排序一、实验目的1.掌握合并排序的基本思想2.掌握合并排序的实现方法3.学会分析算法的时间复杂度4.学会用分治法解决实际问题二、实验内容随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。三、实验环境Window7;惠普笔记

2、本；VC++6.0.四、算法描述和程序代码#include#include#includeusingnamespacestd;#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++];els

3、et[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(left

4、ight);//调用合并函数。}}voidmain(){inti;cout<<"排序前的数组为：";for(i=0;i<10;i++){a[i]=random(100);//调用random函数，产生10个0-100的随机数。cout<

5、排序是一个典型的分治算法，其基本运算为元素比较，最坏情况下的时间为W(n)=O(nlogn)，在排序过程中需要使用与原序列相同长度的辅助数组temp，因此它所需的额外空间为O(n)。通过编写代码，我很好的掌握了分治法的步骤：划分；求解子问题；合并。对“分治策略”有了更深的体会，它将原问题划分为彼此独立的、规模较小而结构相同的子问题。11实验2贪心法作业调度一、实验目的1.掌握贪心算法的基本思想2.掌握贪心算法的典型问题求解3.进一步多级调度的基本思想和算法设计方法4.学会用贪心法分析和解决实际问题二、实验内容设计贪

6、心算法实现作业调度，要求按作业调度顺序输出作业序列。如已知n=8，效益p=(35, 30, 25, 20, 15, 10, 5, 1)，时间期限 d=(4, 2, 4, 5, 6, 4, 5, 7)，求该条件下的最大效益。三、实验环境Window7;惠普笔记本；VC++6.0.四、算法描述和程序代码#includeusingnamespacestd;constintWork[8]={35,30,25,20,15,10,5,1};//所有作业按收益从大到小排序constintmaxTime[8]=

7、{4,2,4,5,6,4,5,7};classHomeWork{private:intres[8];boolflag[8];intmaxReap;public:voiddealWith(){//遍历所有作业:inti;for(i=0;i<8;i++){intTime=maxTime[i]-1;if(!flag[Time]){//如果最大期限那一天还未安排作业,则将当前作业安排在所允许的最大期限那天res[Time]=Work[i];flag[Time]=true;}else{//如果当前作业所允许的最大期限那一天已

8、经安排的其他作业,就向前搜索空位,将该作业安排进去for(intj=Time-1;j>=0;j--)11if(!flag[j]){res[j]=Work[i];flag[j]=true;break;}}}cout<<"作业完成顺序为:";for(i=0;i<7;i++){cout<