《分治算法求最大值与最小值.doc》由会员分享，可在线阅读，更多相关《分治算法求最大值与最小值.doc（3页珍藏版）》请在金锄头文库上搜索。
1、实践题目： 给定一个顺序表，编写一个求出其最大值和最小值的分治算法。 分析： 由于顺序表的结构没有给出，作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义，数据随机生成。我们知道如果数组大小为 1 则可以直接给出结果，如果大小为 2则一次比较即可得出结果，于是我们找到求解该问题的子问题即: 数组大小 = 2。到此我们就可以进行分治运算了，只要求解的问题数组长度比 2 大就继续分治，否则求解子问题的解并更新全局解以下是代码。 */ /* 编译环境TC */ #include #include #include #define M 40 /* 分治法获取最优解 */ void Partio
2、nGet(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 + (e-s)/2; /* 不是子问题继续分治,这里使用了二分，也可
3、以是其它 */ 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;
