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

本科实验报告课程名称:算法设计与分析实验项目:分治法合并排序贪心法作业调度动态规划法求多段图问题回溯法求n皇后问题实验地点:致远楼B503专业班级:学号:学生:指导教师:2017年3月18日实验1分治法合并排序一、、实验容随机产生一个整型数组,然后用合并排序将该数组做升序排列,要求输出排序前和排序后的数组。三、实验环境Window10;惠普笔记本;Devcpp算法描述和程序代码#include<>#include<iostream>#include<>#include<>usingnamespacestd;#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++]; else t[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<right){ intmid=((left+right)/2); MergeSort(left,mid); MergeSort(mid+1,right); Merge(left,mid,right);//调用合并函数。 }}intmain(){ inti; cout<<"排序前的数组为:"; for(i=0;i<10;i++){ a[i]=random(100);//调用random函数,产生10个0-100的随机数。 cout<<a[i]<<""; } cout<<endl; MergeSort(0,9); cout<<"排序后的数组为:"; for(i=0;i<10;i++){ cout<<a[i]<<""; } getchar(); return0;}五、实验结果截图六、实验总结通过编写这个程序,我进一步了解了分株算法的思想,在实际运用过程当中,尤其是在算法编写方面相对来说比较简单,实现起来较为容易。实验2贪心法作业调度一、、实验容设计贪心算法实现作业调度,要求按作业调度顺序输出作业序列。如已知n=8,效益p=(35, 30, 25, 20, 15, 10, 5, 1),时间期限 d=(4, 2, 4, 5, 6, 4, 5, 7),求该条件下的最大效益。三、实验环境Window10;惠普笔记本;Devcpp四、算法描述和程序代码#include<iostream>usingnamespacestd;constintWork[8]={45,30,28,25,23,15,10,1};//所有作业按收益从大到小排序 constintmaxTime[8]={4,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(intj=Time-1;j>=0;j--) if(!flag[j]){ res[j]=Work[i]; flag[j]=true; break; } } } cout<<"作业完成顺序为:"; for(i=0;i<7;i++){ cout<<res[i]<<"\t"; } cout<<endl; cout<<endl<<"最佳效益为:"; intj; for(j=0;j<7;j++) maxReap+=res[j]; cout<<maxReap<<endl; } HomeWork(){ in