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

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

1、..本科实验报告课程名称：算法设计与分析实验项目：分治法合并排序贪心法作业调度动态规划法求多段图问题回溯法求n皇后问题实验地点：致远楼B503专业班级：学号：学生：指导教师：2017年3月18日word教育资料..实验1分治法合并排序一、实验目的1.掌握合并排序的基本思想2.掌握合并排序的实现方法3.学会分析算法的时间复杂度4.学会用分治法解决实际问题二、实验容随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。三、实验环境Window10;惠普笔记本；Devcpp四、算法描述和程序代码#include#include<

2、iostream>#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++];elset[k++]=a[j++];}while(i<=mid)t[k++]=a[i++];while(j<=right)t[

3、k++]=a[j++];for(i=0,k=left;k<=right;)a[k++]=t[i++];}//分划函数，并且调用合并函数。voidMergeSort(intleft,intright){if(left

4、);//调用random函数，产生10个0-100的随机数。cout<

5、计方法4.学会用贪心法分析和解决实际问题二、实验容设计贪心算法实现作业调度，要求按作业调度顺序输出作业序列。如已知n=8，效益p=(35, 30, 25, 20, 15, 10, 5, 1)，时间期限 d=(4, 2, 4, 5, 6, 4, 5, 7)，求该条件下的最大效益。三、实验环境Window10;惠普笔记本；Devcpp四、算法描述和程序代码#includeusingnamespacestd;constintWork[8]={45,30,28,25,23,15,10,1};//所有作业按收益从大到小排序constintmaxTime[8]={4

6、,7,3,2,4,6,7,5};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{//如果当前作业所允许的最大期限那一天已经安排的其他作业,就向前搜索空位,将该作业安排进去for(int

7、j=Time-1;j>=0;j--)if(!flag[j]){word教育资料..res[j]=Work[i];flag[j]=true;break;}}}cout<<"作业完成顺序为:";for(i=0;i<7;i++){cout<