编译实验报告书.docVIP

学生学号 0120810680334 实验课成绩 武汉理工大学 学 生 实 验 报 告 书 实验课程名称 《算法设计与分析》 开 课 学 院 计算机科学与技术学院 指导老师姓名 何九周 学 生 姓 名 鲁爱燕 学生专业班级 软件0803 2010 — 2011 学年 第 一 学期 实验课程名称：算法设计与分析 实验项目名称 分治法应用及设计 实验成绩 实验者 鲁爱燕 专业班级 软件0803 组别 同组者 实验日期 年 月 日 第一部分：实验分析与设计（可加页） 实验内容描述（问题域描述） 利用分治法，写一个二分检索的递归算法，并利用任何一种语言，在计算机上实现，同时进行时间复杂性分析。 用分治法，实现对n个元素进行排序的算法，并进行时间复杂性分析。 实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述） 程序一代码如下： #includeiostream using namespace std; int binsearch(int a[],int left,int right,int x); int main() { int a[8]={4,8,9,10,50,55,60,97},cont=1,x; while(cont==1) { cout请输入要查询的值x：endl; cinx; coutbinsearch(a,0,7,x)endl; cout继续查询 yes-1 or no-0 ? endl; cincont; if(cont1) {cout您输入的数字有问题！请重新输入endl; cincont;} } return 0; } int binsearch(int a[],int left,int right,int x) {if(left=right) {int middle=(left+right)/2; if(a[middle]==x)return middle; else if(a[middle]x)return binsearch(a,left,middle-1,x); else return binsearch(a,middle+1,right,x); } return -1; } 三、主要仪器设备及耗材 Visual C++ 6.0 程序二代码如下： #includestdio.h #includestdlib.h typedef int RecType;//要排序元素类型 void Merge(RecType *R,int low,int m,int high) {int i=low,j=m+1,p=0; //置初始值 RecType *R1; //R1是局部向量 R1=(RecType *)malloc((high-low+1)*sizeof(RecType)); if(!R1)return; //申请空间失败 while(i=mj=high) //两子文件非空时取其小者输出到R1[p]上 R1[p++]=(R[i]=R[j])?R[i++]:R[j++]; while(i=m) //若第1个子文件非空，则复制剩余记录到R1中 R1[p++]=R[i++]; while(j=high) //若第2个子文件非空，则复制剩余记录到R1中 R1[p++]=R[j++]; for(p=0,i=low;i=high;p++,i++) R[i]=R1[p];//归并完成后将结果复制回R[low..high] } void MergeSort(RecType R[],int low,int high) {//用分治法对R[low..high]进行二路归并排序 int mid; if(lowhigh)//区间长度大于1 { mid=(low+high)/2;//分解 MergeSort(R,low,mid);//递归地对R[low..mid]排序 MergeSort(R,mid+1,high); //递归地对R[mid+1..high]排序 Merge(R,low,mid,high);//组合，将两个有序区归并为一个有序区 } } void main