分治法的基本思想：是將一個(gè)規(guī)模為n的原問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題相同。遞歸地解這些子問(wèn)題，然后將子問(wèn)題的解合并為原問(wèn)題的解。

1 #include<stdio.h> 2 /* 分治法計(jì)算最大值和最小值的算法程序，遞歸實(shí)現(xiàn) */ 3 void maxmin2(int d[], int left, int right, int *max, int *min) //數(shù)組，頭，尾，最大值，最小值 4 { 5 int max1, min1; 6 //遞歸最小時(shí)處理 7 if(left==right) { //如果只有一個(gè)數(shù) 即使最大也是最小 8 *max = d[left]; 9 *min = d[left]; 10 } else if(left == right-1) { //兩個(gè)數(shù)，判斷大小 11 if(d[left] > d[right]){ 12 *max = d[left]; 13 *min = d[right]; 14 } else { 15 *max = d[right]; 16 *min = d[left]; 17 } 18 } else { 19 int mid = (left + right) / 2; //二分 20 maxmin2(d, left, mid, &max1, &min1); //處理左端 21 maxmin2(d, mid+1, right, &max1, &min1); //處理右端 22 if(*max < max1) // 先分后治 23 *max = max1; 24 if(*min > min1) 25 *min = min1; 26 } 27 } 28 29 int main() 30 { 31 int d[10] = {0,1,2,3,4,5,6,7,8,9}; 32 int max,min; 33 maxmin2(d,0,9,&max,&min); 34 printf("%d %d",max,min); 35 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Dicer/p/8533086.html

總結(jié)

以上是生活随笔為你收集整理的分治法求最大最小的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。