c语言：采用分治法递归求含n个数的某个序列的最大元素和次大元素。

Question

当序列a[low..high]中元素的个数等于2时，通过直接比较即可找出序列的最大元素和次大元素；当元素的个数大于2时，求出中间位置mid，将序列分为a[low..mid]和a[mid+1..high]如题，问题代码如下，输出结果不正确，找不到原因，望大佬指点.

Answer 1

high -low 为奇数，这个mid是小数。

（1）数组个数为n，还用a[n]

（2）还不如直接用个for循环，将max=0

#include <stdio.h>

#define N 21

int max(int a,int b){

if(a>b)

return a;

return b;

}

int getM(int * a,int l,int u){

if(u==l)

return a[u];

else{

return max(getM(a,l,(u+l)/2),getM(a,(u+l)/2+1,u) );

}

}

int main()

{

int a[N]={1,2,3,4,5,6,7,8,9,21,11,12,13,14,15,16,17,18,19,20,17};

printf("max=%d",getM(a,0,N-1));

return 0;

}

扩展资料：

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。

n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可。

而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

参考资料来源：百度百科-分治法

Answer 2

high -low 为奇数，你这个mid是小数了，你是不是要取整？本回答被网友采纳