分治与递归上机.doc_第1页
分治与递归上机.doc_第2页
分治与递归上机.doc_第3页
分治与递归上机.doc_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法设计与分析实验报告实验1分治与递归上机实验目的1掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法；2熟练掌握利用递归设计分治算法的基本步骤；3学会利用分治算法解决实际问题。实验要求按以下实验内容完成题目，并把编译、运行过程中出现的问题以及解决方法填入实验报告中，按时上交。实验学时 2学时。实验内容一、实验内容金块问题。老板有一袋金块（共n块，n是2的幂（n2），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。请对自己实现的程序进行复杂性分析。二、算法描述（1）划分：将数组分割成两半（2）治理：在每一半中找到最大值和最小值。（3）合并：返回两个最大值中的最大值和两个最小值中的最小值。Minmax(int low,int high) if low=high return(Alow,Ahigh) /只有一个元素 else if high-low=1 then /如果只有两个元素直接解决 if AlowAhigh then return(Alow,Ahigh) else return(Ahigh,Alow) end if else /否则递归解决 mid=(low+high)/2 ; /将区间一分为二 (x1,y1)=minmax(low,mid); /求左半区间的最大最小值 (x2,y2)=minmax(mid+1,high); /右半区间的最大最小值 x=minx1,x2; y=max(y1,y2); /求整体最大最小值 return(x,y); endif三、源程序#include#define Maxsize 1000void Minmax(int A,int low,int high,int *min,int *max);void main()int n;int min,max;int GoldMaxsize;printf(please input n: );scanf(%d,&n);printf(please input weight of gold: );for(int i=1;i=n;i+)scanf(%d,&Goldi);Minmax(Gold,1,n,&min,&max);printf(nMin: %d,min);printf(nMax: %dn,max);void Minmax(int A,int low,int high,int *min,int *max)int mid,x1,x2,y1,y2;if (low=high)*min=*max=Alow;if (high-low=1)if (Alowx2) *min=x2;else *min=x1;if (y1y2) *max=y1;else *max=y2;
人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论