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

会计考友

　求最大值和最小值的分治算法　　实践题目：
　　给定一个顺序表，编写一个求出其最大值和最小值的分治算法。
$ y4 B( \' M  X　　分析：
　　由于顺序表的结构没有给出，作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义，数据随机生成。我们知道如果数组大小为 1 则可以直接给出结果，如果大小为 2则一次比较即可得出结果，于是我们找到求解该问题的子问题即: 数组大小  *max)
1 H2 e+ I/ `/ [* @4 Q: [3 C0 E6 U　　*max = meter;
( t% h2 W! Q- E" @- f3 l! w- i　　if(meter[e] < *min)
　　*min = meter[e];
# t( d! @& g* q1 _8 P　　}

会计考友

　else{　　if(meter[e] > *max)
' j/ r; k% b9 C7 f- q　　*max = meter;
　　if(meter < *min)
　　*min = meter;
　　}
7 f& F5 i6 w7 ?% ~& y* D; ]　　return ;
　　}
　　i = s + (e-s)/2; /* 不是子问题继续分治,这里使用了二分，也可以是其它 */
/ |& K6 _- g, w3 J2 n3 j7 ?　　PartionGet(s,i,meter,max,min);
# W& Q7 q8 w0 B' @8 z( o　　PartionGet(i+1,e,meter,max,min);
5 n$ w7 `) k' C: G　　}
7 e" A3 _3 h0 x7 ]( ^( l0 }　　int main(){
　　int i,meter[M];
$ C8 N% d. \- \　　int max = INT_MIN; /* 用最小值初始化 */
　　int min = INT_MAX; /* 用最大值初始化 */
) q( |$ O1 ?5 X) {2 H) Y　　printf("The array's element as followed:\n\n");
" |* s" o, s0 p0 @: t9 I# B　　randomize(); /* 初始化随机数发生器 */
　　for(i = 0; i < M; i ++){ /* 随机数据填充数组 */
+ ^' Z4 |5 u* X0 b　　meter = rand()%10000;
　　if(!((i+1)%10)) /* 输出表的随机数据 */
　　printf("%-6d\n",meter);
: `* f; Z' \8 C1 x# X: R　　else
　　printf("%-6d",meter);
　　}
　　PartionGet(0,M - 1,meter,&max,&min); /* 分治法获取最值 */
　　printf("\nMax : %d\nMin : %d\n",max,min);
　　system("pause");
# G6 C+ ~2 Z' p  h7 w! K　　return 0;
　　}