Question

分治法c语言求最大最小值

#include <stdio.h>
int min,max,min1,max1,min2,max2;
int a[10]={1,345,231,23,12,22,45,24,12,2};

int minmax( int *i,int *j,int max,int min)
{

if(i==j)
{
min=max=*i;
}
else if(i+1==j)
{

if(*i>*j)
{
min=*j;
max=*i;
}
else
{
min=*i;
max=*j;
}
}
else if((i+1!=j)&&(i!=j))
{
minmax(i,i+(j-i)/2,max1,min1);
printf("%d,%d\n",max2,min2);

minmax(i+(j-i)/2,j,max2,min2);
if(max1>max2)max=max1;
else max=max2;
if(min1>min2)min=min2;
else min=min1;

}

}
int main()
{

int minmax(int *i,int *j, int max,int min);
printf("%d,%d\n",a[0],a[9]);
minmax(a,a+9,max,min);
printf("%d,%d\n",max,min);
}
这个程序问题出在哪儿？谢谢！

Answer 1

1、分治法不是用来求最大值最小值的。在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)。

分治法的精髓：

分--将问题分解为规模更小的子问题；

治--将这些规模更小的子问题逐个击破；

合--将已解决的子问题合并，最终得出“母”问题的解。

2、求数组中的最大值和最小值，一般使用假设法，即假设数组的第1个元素为最大值，同时也是最小值，然后遍历数组，找到最大值和最小值。示例如下:

#include<stdio.h>
int main() 
{ 
int a[] = {1,2,3,4,5,6,7,8,9,10};
int max, min;
max = min = a[0]; //假设第1个元素即是最大值也是最小值。
int max_pos = 0, min_pos = 0;
//遍历数组，找出数组a中的最大数和最小数
for (int inx=0; inx!=sizeof(a) / sizeof(int); ++inx) {
if (a[inx]> max) max = a[inx], max_pos=inx;
else if (a[inx] < min) min = a[inx], min_pos=inx;
}
printf("最大数:%d\t最小数:%d\n", max ,min );
return 0;
}

Answer 2

1）问题出在minmax函数，这个函数找到的最大值和最小值没有返回。
2）虽然你定义了最大值和最小值为全局变量，但是在minmax函数的调用参数中你又定义了同名变量，这样在minmax函数内部实际使用的是局部变量。
3）最简单的方法，直接把minmax函数的后两个输入参数去掉。