算法设计与分析实验.doc

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

1、本科实验报告课程名称：算法设计与分析实验项目：分治法合并排序、贪心法作业调度、动态规划法求多段图问题、回溯法求n皇后问题实验地点：行知楼c122专业班级：软件1310学号：学生姓名：葛文卿指导教师：王幸民2015年03月28日实验项目分治法合并排序一、实验目的掌握合并排序的基本思想掌握合并排序的实现方法学会分析算法的时间复杂度学会用分治法解决实际问题二、实验内容随机产生一个整型数组，然后用合并排序将该数组做升序排列，要求输出排序前和排序后的数组。三、实验环境程序设计语言：c++编程工具：microsoftvisualstudio2010四、算法描述和程序代码

2、#includeusingnamespacestd;voidmerge(int*data,intp,intq,intr){intn1,n2,i,j,k;int*left=NULL,*right=NULL;n1=q-p+1;n2=r-q;left=(int*)malloc(sizeof(int)*(n1));right=(int*)malloc(sizeof(int)*(n2));for(i=0;i

3、[q+1+j];i=j=0;k=p;while(i>input[i];}//处理数据mergeSort(input,0,n-1);//输出结果for(i=0;i

4、ata[k++]=left[i];for(;j

5、a,intp,intr){intq;if(p>n;input=(int*)malloc(sizeof(int)*(n));intq;if(p

6、序{q=(int)((p+r)/2);//将data数组分成两半mergeSort(data,p,q);//递归拆分左数组mergeSort(data,q+1,r);//递归拆分右数组merge(data,p,q,r);//合并数组}}intmain(){intn,i;int*input=NULL;//输入数据cout<<"请输入数组的长度:";cin>>n;input=(int*)malloc(sizeof(int)*(n));cout<<"请对数组赋值:";for(i=0;i>input[i];}//处理数据mergeSort(i

7、nput,0,n-1);//输出结果for(i=0;i

8、, 4, 5, 7)，求该条件下的最大效益。三、实验