2011年计算机等级考试二级C辅导实例编程(10)

会计考友

　求最大值和最小值的分治算法　　实践题目：
　　给定一个顺序表，编写一个求出其最大值和最小值的分治算法。
2 q$ G5 z! M3 I; ]7 V0 a　　分析：
　　由于顺序表的结构没有给出，作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义，数据随机生成。我们知道如果数组大小为 1 则可以直接给出结果，如果大小为 2则一次比较即可得出结果，于是我们找到求解该问题的子问题即: 数组大小  *max)
: i$ h) H+ Y" T2 C2 Q/ ~2 f9 w, B  k　　*max = meter;
' q% h- L8 y: b　　if(meter[e] < *min)
. r' G8 c7 s. ^) I- d　　*min = meter[e];
　　}

会计考友

　else{　　if(meter[e] > *max)
　　*max = meter;
% t" C4 k5 i5 L, J2 o& `　　if(meter < *min)
$ Z. b) Z+ X& S' A　　*min = meter;
　　}
　　return ;
: V  n% ^. g; U! D  L; j, g　　}
　　i = s + (e-s)/2; /* 不是子问题继续分治,这里使用了二分，也可以是其它 */
　　PartionGet(s,i,meter,max,min);
　　PartionGet(i+1,e,meter,max,min);
9 n: N8 o# `0 [　　}
" f! [' Q6 R8 b4 F* o　　int main(){
　　int i,meter[M];
　　int max = INT_MIN; /* 用最小值初始化 */
" x& ?' s0 J" U: O8 Y7 T　　int min = INT_MAX; /* 用最大值初始化 */
" e+ g- i0 A$ h" Z' U　　printf("The array's element as followed:\n\n");
　　randomize(); /* 初始化随机数发生器 */
" |4 h) r, T  q4 j8 U0 E　　for(i = 0; i < M; i ++){ /* 随机数据填充数组 */
" z7 T1 p, Y5 V  X/ d　　meter = rand()%10000;
, e1 A+ Z' n$ G; t: d" z3 v; ~　　if(!((i+1)%10)) /* 输出表的随机数据 */
　　printf("%-6d\n",meter);
　　else
　　printf("%-6d",meter);
　　}
( ~4 S/ o# s3 {1 _3 U! @0 [. C' m　　PartionGet(0,M - 1,meter,&max,&min); /* 分治法获取最值 */
　　printf("\nMax : %d\nMin : %d\n",max,min);
　　system("pause");
　　return 0;
　　}