欢迎来到天天文库
浏览记录
ID:58080944
大小:24.00 KB
页数:3页
时间:2020-04-10
《求最大值和最小值的分治算法.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、给定一个顺序表,编写一个求出其最大值和最小值的分治算法。分析:由于顺序表的结构没有给出,作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义,数据随机生成。我们知道如果数组大小为1则可以直接给出结果,如果大小为2则一次比较即可得出结果,于是我们找到求解该问题的子问题即:数组大小<=2。到此我们就可以进行分治运算了,只要求解的问题数组长度比2大就继续分治,否则求解子问题的解并更新全局解以下是代码。*//***编译环境TC***/#include#include#include#defi
2、neM40/*分治法获取最优解*/voidPartionGet(ints,inte,int*meter,int*max,int*min){/*参数:*s当前分治段的开始下标*e当前分治段的结束下标*meter表的地址*max存储当前搜索到的最大值*min存储当前搜索到的最小值*/inti;if(e-s<=1){/*获取局部解,并更新全局解*/if(meter[s]>meter[e]){if(meter[s]>*max)*max=meter[s];if(meter[e]<*min)*min=meter[e];}else{if(meter[e]>*m
3、ax)*max=meter[s];if(meter[s]<*min)*min=meter[s];}return;}i=s+(e-s)/2;/*不是子问题继续分治,这里使用了二分,也可以是其它*/PartionGet(s,i,meter,max,min);PartionGet(i+1,e,meter,max,min);}intmain(){inti,meter[M];intmax=INT_MIN;/*用最小值初始化*/intmin=INT_MAX;/*用最大值初始化*/printf("Thearray'selementasfollowed:
4、");randomize();/*初始化随机数发生器*/for(i=0;i
此文档下载收益归作者所有