求最大值和最小值的分治算法.doc

《求最大值和最小值的分治算法.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