2015年计算机等级考试二级C语言辅导实例编程（10）-计算机等级考试-计算机-珠峰网 www.my8848.com

2015年计算机等级考试二级C语言辅导实例编程（10）

发布时间：2011/1/16 18:10:52 来源：城市学习网编辑：ziteng

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

　　实践题目：

　　给定一个顺序表，编写一个求出其最大值和最小值的分治算法。

　　分析：

　　由于顺序表的结构没有给出，作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义，数据随机生成。我们知道如果数组大小为 1 则可以直接给出结果，如果大小为 2则一次比较即可得出结果，于是我们找到求解该问题的子问题即: 数组大小 <= 2。到此我们就可以进行分治运算了，只要求解的问题数组长度比 2 大就继续分治，否则求解子问题的解并更新全局解以下是代码。

　　/*** 编译环境TC ***/

　　#include

　　#define M 40

　　/* 分治法获取最优解 */

　　void PartionGet(int s,int e,int *meter,int *max,int *min){

　　/* 参数:

　　* s 当前分治段的开始下标

　　* e 当前分治段的结束下标

　　* meter 表的地址

　　* max 存储当前搜索到的最大值

　　* min 存储当前搜索到的最小值

　　int i;

　　if(e-s <= 1){ /* 获取局部解，并更新全局解 */

　　if(meter[s] > meter[e]){

　　if(meter[s] > *max)

　　*max = meter[s];

　　if(meter[e] < *min)

　　*min = meter[e];

　　} [NextPage] 　else{

　　if(meter[e] > *max)

　　*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);

　　}

　　int main(){

　　int i,meter[M];

　　int max = INT_MIN; /* 用最小值初始化 */

　　int min = INT_MAX; /* 用最大值初始化 */

　　printf("The array's element as followed:\n\n");

　　randomize(); /* 初始化随机数发生器 */

　　for(i = 0; i < M; i ++){ /* 随机数据填充数组 */

　　meter[i] = rand()%10000;

　　if(!((i+1)%10)) /* 输出表的随机数据 */

　　printf("%-6d\n",meter[i]);

　　else

　　printf("%-6d",meter[i]);

　　}

　　PartionGet(0,M - 1,meter,&max,&min); /* 分治法获取最值 */

　　printf("\nMax : %d\nMin : %d\n",max,min);

　　system("pause");

　　return 0;

　　}