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

《求最大值和最小值的分治算法.doc》由会员分享，可在线阅读，更多相关《求最大值和最小值的分治算法.doc（3页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、如有侵权，请联系网站删除，仅供学习与交流求最大值和最小值的分治算法【精品文档】第 3 页给定一个顺序表，编写一个求出其最大值和最小值的分治算法。 分析： 由于顺序表的结构没有给出，作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义，数据随机生成。我们知道如果数组大小为 1 则可以直接给出结果，如果大小为 2则一次比较即可得出结果，于是我们找到求解该问题的子问题即: 数组大小 = 2。到此我们就可以进行分治运算了，只要求解的问题数组长度比 2 大就继续分治，否则求解子问题的解并更新全局解以下是代码。 /* 编译环境TC */ #include #include #include #def

2、ine M 40 /* 分治法获取最优解 */ void PartionGet(int s,int e,int *meter,int *max,int *min) /* 参数: * s 当前分治段的开始下标 * e 当前分治段的结束下标 * meter 表的地址 * max 存储当前搜索到的最大值 * min 存储当前搜索到的最小值 int i; if(e-s metere) if(meters *max) *max = meters; if(metere *max) *max = meters; if(meters *min) *min = meters; return ; i = s +

3、(e-s)/2; /* 不是子问题继续分治,这里使用了二分，也可以是其它 */ PartionGet(s,i,meter,max,min); PartionGet(i+1,e,meter,max,min); int main() int i,meterM; int max = INT_MIN; /* 用最小值初始化 */ int min = INT_MAX; /* 用最大值初始化 */ printf(The arrays element as followed:nn); randomize(); /* 初始化随机数发生器 */ for(i = 0; i M; i +) /* 随机数据填充数组 */ meteri = rand()%10000; if(!(i+1)%10) /* 输出表的随机数据 */ printf(%-6dn,meteri); else printf(%-6d,meteri); PartionGet(0,M - 1,meter,&max,&min); /* 分治法获取最值 */ printf(nMax : %dnMin : %dn,max,min); system(pause); return 0;