分治法求最大最小值分治法求最大最小值
一. 实验目的及实验环境
实验目的:加深对分治算法原理及实现过程的理解。
实验环境:VC++6.0
二. 实验内容
用分治法求数组中最大元素和最小元素。
三(方案设计
如果数组大小为 1 则可以直接给出结果,如果大小为 2则一次比较即可
结果,于是我们找到求解该问题的子问题即: 数组大小
using namespace std;
void min_max(int a[],int i,int j,int &min,int &max)
{
int mid,max1,max2,min1,m...
分治法求最大最小值
一. 实验目的及实验环境
实验目的:加深对分治算法原理及实现过程的理解。
实验环境:VC++6.0
二. 实验内容
用分治法求数组中最大元素和最小元素。
三(
如果数组大小为 1 则可以直接给出结果,如果大小为 2则一次比较即可
结果,于是我们找到求解该问
的子问题即: 数组大小 <= 2。到此我们就可
以进行分治运算了,只要求解的问题数组长度比 2 大就继续分治,否则求解
子问题的解并更新全局解。
四(测试数据及运行结果
五(总结
1( 实验过程中遇到的问题及解决办法
在刚开始的时候由于对分治法只是理论上的理解,并没有真的实际操作,
所以不是很会,在写代码的时候有点困难,在参考
上例子自己思考之后就
有思路了。
2( 对设计及调试过程的心得体会。
通过这次上机实验,自己从设计方案到代码的实现,虽然费了一些时间,
但是总归弄清了分治法的思想,将一个难以直接解决的大问题,分割成一些
规模较小的相同问题,以便各个击破,分而治之所以在以后的学习过程中自
己一定要学以致用,只有自己亲手实践了才会理解更深刻,知识才会掌握更
牢固。在考虑问题是一定要严谨,注意细节,设计好方案才是实现算法的关
键,同时以后要增加自己的知识面。
六(附录:源代码(电子版)
#include
using namespace std;
void min_max(int a[],int i,int j,int &min,int &max)
{
int mid,max1,max2,min1,min2;
if(i==j){
max=a[i];
min=a[i];
return ;
}
if(j==i+1)
{
if(a[i]>a[j]){min=a[j];max=a[i];}
else{min=a[i];max=a[j];}
}
else
{
mid=(i+j)/2;
min_max(a,i,mid,min1,max1);
min_max(a,mid+1,j,min2,max2);
if(min1>min2)min=min2;
else min=min1;
if(max1>max2)max=max1;
else max=max2;
}
}
int main()
{
int n,m,a[100],min,max;
cin>>n;
while(n!=0)
{
cin>>m;
for(int i=1;i<=m;i++)cin>>a[i];
min_max(a,1,m,min,max);
cout<
本文档为【分治法求最大最小值】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。