问题:求一列数中的最大最小值,设一共有N个数字.
1. max_min1()
最简单的想法是平凡算法,只要挨个比较就可以了.求最大值需要N-1次比较,最小值需要N-2次比较.
则T(N) = W(N) = A(N) = 2N -3
显然 S(N) = O(1)
2. max_min2()
分别去比较得出结果即可,求得最大最小值各需要N-1次比较.
T(N) = W(N) = A(N) = 2N -2
3. max_min3()
方法2中的判断有多多余的部分,MAX > list[i]的话就不用判断MIN是否> list[i]了.
因此有递增序列的情况下,B(N) = N -1,递减序列的情况下: W(N) = 2N -1
4. max_min4()
分治的算法,处理了n为奇数和偶数的情况.
(1)当N == 1时, 显然正确
(2)当N == 2时,显然正确
(3)设当N <= M的时候算法正确,即M被划分为M/2长的两个序列或者M/2与M/2 +1的时候的两个序列的情况下是正确的,设两序列分别为L1与L2
那么对于N = M + 1的情况,序列可被分为M/2与M/2+1的两个序列或者是M/2+1的两个序列,以L1与L2表示,
2/M + 1 <= M 成立, 则m11,m21为L1的最大值和最小值,m12,m21为L2的最大值和最小值,max取m11与m12中的最大值,min取m21与m22中的最小值,因为L1和L2是L的一个划分,所以max和min为list的最大值和最小值.
//不知道这样说明这个算法的正确性是否有问题.感觉是有问题的...
#include
#include
#include
#define MAX_LENGTH 100
/*Show usage*/
void usage(char * prog)
{
printf("%s Usage:\n", prog);
printf("%s \n", prog);
}
/*Generate and initialize the list*/
int * generate_list(int count)
{
int i;
int * list;
list = (int *)malloc(count*sizeof(int));
if(list == NULL)
{
perror("malloc");
return NULL;
}
/*Initialize the list with integers less than 100*/
srandom((unsigned int)time(NULL));
for (i = 0; i < count ; i ++)
list[i] = random()%100;
return list;
}
/*To find Max, Min, 2n - 3*/
void max_min1(int * list, int length)
{
int i, j = 0, temp;
int max = list[0], min = list[0];
for(i = 1; i < length; i ++)
{
if(max < list[i])
{
max = list[i];
j = i;
}
}
/*Swap*/
temp = list[j];
list[j] = list[length -1];
list[length -1] = temp;
for(i = 1; i < length -1; i ++)
if(min > list[i])
min = list[i];
printf("MAX = %d, MIN = %d\n", max, min);
}
/*To find Max, Min, 2n - 2*/
void max_min2(int * list, int length)
{
int i;
int max = list[0], min = list[0];
for(i = 1; i < length; i ++)
{
if(max < list[i])
max = list[i];
if(min > list[i])
min = list[i];
}
printf("MAX = %d, MIN = %d\n", max, min);
}
/*To find Max, Min, W(N) = 2n-2, B(N) = n - 1*/
void max_min3(int * list, int length)
{
int i;
int max = list[0], min = list[0];
for(i = 1; i < length; i ++)
{
if(max < list[i])
max = list[i];
else
if(min > list[i])
min = list[i];
}
printf("MAX = %d, MIN = %d\n", max, min);
}
/*To find Max, Min, */
void max_min4(int * list, int length, int * max, int * min, int pos)
{
if(length == 1)
{
*max = list[pos];
*min = list[pos];
}
else if(length == 2)
{
if(list[pos] > list[pos + 1])
{
*max = list[pos];
*min = list[pos + 1];
}
else
{
*max = list[pos + 1];
*min = list[pos];
}
}
else /*divide the list into 2 parts and call the max_min4() */
{
int * m11, * m21, * m12, * m22;
m11 = (int *)malloc(sizeof(int));
m12 = (int *)malloc(sizeof(int));
m21 = (int *)malloc(sizeof(int));
m22 = (int *)malloc(sizeof(int));
if(length % 2 == 0)
{
max_min4(list, length/2, m11, m21, pos);
max_min4(list, length/2, m12, m22, pos + length/2);
}
else
{
max_min4(list, length/2, m11, m21, pos);
max_min4(list, length/2 + 1, m12, m22, pos + length/2);
}
if(*m11 < *m12) *max = *m12;
else *max = *m11;
if(*m21 < *m22) *min = *m21;
else *min = *m22;
free(m11);
free(m12);
free(m21);
free(m22);
}
return;
}
int main(int argc, char * argv[])
{
int length, i;
int * list = NULL;
int *max, *min;
/*Deal with the arguments*/
if(argc != 2)
{
usage(argv[0]);
exit(127);
}
length = atoi(argv[1]);
if(!length || length > MAX_LENGTH)
{
usage(argv[0]);
exit(129);
}
list = generate_list(length);
if(list == NULL)
exit(128);
else
{
for(i = 0; i < length; i ++)
printf("%d ", list[i]);
printf("\n");
max_min1(list, length);
max_min2(list, length);
max_min3(list, length);
max = (int *)malloc(sizeof(int));
min = (int *)malloc(sizeof(int));
max_min4(list, length, max, min, 0);
printf("MAX = %d, MIN = %d\n", *max, *min);
}
free(list);
free(max);
free(min);
return 1;
}
