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

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

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

2、include#include#includeusingnamespacestd;#definerandom(x)(rand()%x);inta[10];//合并排序函数。voidMerge(intleft,intmid,intright){intt[ll];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

3、++]=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、for(i=0;i<10;i++){a[i]=random(100);//调用random函数，产生10个0H00的随机数。cout<

5、数组temp，因此它所需的额外空间为O(n)。通过编写代码，我很好的掌握了分治法的步骤：划分；求解子问题；合并。对“分治策略”有了更深的体会，它将原问题划分为彼此独立的、规模较小而结构相同的子问题。实验2贪心法作业调度一、实验目的1.掌握贪心算法的基本思想2.掌握贪心算法的典型问题求解3.进一步多级调度的基本思想和算法设计方法4.学会用贪心法分析和解决实际问题二、实验内容设计贪心算法实现作业调度，要求按作业调度顺序输出作业序列。如已知n=8,效益p=(35,30,25,20,15,10,5,1),时间期限d=(4,2,4,5,6,4,

6、5,7)，求该条件下的最大效益。三、实验环境Window7;惠普笔记本；VC++6.0.算法描述和程序代码^include〈iostream〉usingnamespacestd;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;publie:voiddealWithO{//遍历所有作业：inti

7、;for(i=0;i<8;i++){intTime=maxTime[i]-1;if(!flag[Time]){//如果最大期限那一天还未安排作业，则将当前作业安排在所允许的最大期限那天res[Time]=Work[i];flag[Time]=true;}else{//如果当前作业所允许的最大期限那一天已经安排的其他作业，就向前搜索空位,将该作业安排进去for(intj=Time-1;j>=0;j—)if(!flag[j]){res[j]=Work[i];flag[j]=true;break;}}}cout«"作业完成顺序为<;for(

8、i=0;i〈7;i++){cout<