欢迎来到天天文库
浏览记录
ID:57842701
大小:30.69 KB
页数:4页
时间:2020-03-31
《分治算法实验报告.docx》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、算法分析与设计实验报告第1次实验姓名学号班级时间10.17上午地点四合院102实验名称分治算法实验(用分治法查找数组元素的最大值和最小值)。实验目的通过上机实验,要求掌握分治算法的问题描述、算法设计思想、程序设计。实验原理在满足分治法的条件下,根据不同的输入用例,能准确的输出用例中的最大值与最小值。并计算出程序运行所需要的时间。分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。递归地解这些子问题,然后将各子问题的解合并得到原问题的解。实验步骤①先解决小规模的问题,如数组中只有1个元素或者只有两个元素时候的情况。②将问题分
2、解,如果数组的元素大于等于3个,将数组分为两个小的数组。③递归的解各子问题,将(中分解的两个小的数组再进行以上两个步骤((最后都化为小规模问题。④将各子问题的解进行比较最终得到原问题的解。关键代码voidSelectMaxMin(int*a,inti,intj,int&max,int&min){if(i==j){max=a[i];min=a[i];return;}else{intmid=(i+j)/2;intmaxi,maxj,mini,minj;SelectMaxMin(a,i,(i+j)/2,maxi,mini);SelectMaxMin(a,((i+j)/2)+1
3、,j,maxj,minj);if(maxi>maxj)max=maxi;elsemax=maxj;if(mini4、及具体写算法思想以及步骤。要想更好的掌握还得要理论与实践结合!我懂得,程序、工程都是由一个个细节堆码起来的,不能忽视任何一个小问题,要想熟练地写代码,还是要扎扎实实的练习!实验得分助教签名附录:完整代码SelectMaxMin.cpp:#include#include#include#include#includeusingnamespacestd;voidSelectMaxMin(int*a,inti,intj,int&max,int&min){if(i==j){max=a[i];m5、in=a[i];return;}else{intmid=(i+j)/2;intmaxi,maxj,mini,minj;SelectMaxMin(a,i,(i+j)/2,maxi,mini);SelectMaxMin(a,((i+j)/2)+1,j,maxj,minj);if(maxi>maxj)max=maxi;elsemax=maxj;if(mini6、tart=clock();//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);intm;cout<<"Pleaseinputthenumber:";cin>>m;inta[m];srand((unsignedint)time(NULL));cout<<"随机产生的数据(0-100):";for(inti=0;i7、m-1,max,min);cout<<"max="<
4、及具体写算法思想以及步骤。要想更好的掌握还得要理论与实践结合!我懂得,程序、工程都是由一个个细节堆码起来的,不能忽视任何一个小问题,要想熟练地写代码,还是要扎扎实实的练习!实验得分助教签名附录:完整代码SelectMaxMin.cpp:#include#include#include#include#includeusingnamespacestd;voidSelectMaxMin(int*a,inti,intj,int&max,int&min){if(i==j){max=a[i];m
5、in=a[i];return;}else{intmid=(i+j)/2;intmaxi,maxj,mini,minj;SelectMaxMin(a,i,(i+j)/2,maxi,mini);SelectMaxMin(a,((i+j)/2)+1,j,maxj,minj);if(maxi>maxj)max=maxi;elsemax=maxj;if(mini6、tart=clock();//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);intm;cout<<"Pleaseinputthenumber:";cin>>m;inta[m];srand((unsignedint)time(NULL));cout<<"随机产生的数据(0-100):";for(inti=0;i7、m-1,max,min);cout<<"max="<
6、tart=clock();//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);intm;cout<<"Pleaseinputthenumber:";cin>>m;inta[m];srand((unsignedint)time(NULL));cout<<"随机产生的数据(0-100):";for(inti=0;i7、m-1,max,min);cout<<"max="<
7、m-1,max,min);cout<<"max="<
此文档下载收益归作者所有