分治法查找最大最小数的C代码

### 分治法查找最大最小数的C代码解析 #### 分治法简介 分治法（Divide and Conquer）是一种非常强大的算法设计策略，在解决复杂问题时常常被采用。其核心思想是将一个复杂的问题分解成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 #### 代码分析 ##### 定义宏与函数原型声明 ```c #ifndef MAXMIN_2010_03_11 #define MAXMIN_2010_03_11 #include "stdio.h" #define MAXSIZE 15 #define MAX(a, b) ((a) > (b) ? (a) : (b)) #define MIN(a, b) ((a) < (b) ? (a) : (b)) void Max_Min(int L[], int start, int end, int *max, int *min); #endif ``` 这里定义了几个宏，`MAXMIN_2010_03_11`用于防止头文件被重复包含；`MAXSIZE`定义了数组的最大长度为15；`MAX`和`MIN`是计算两个整数中的最大值和最小值的宏。 ##### 主程序 ```c int *p; #include "MaxMin.h" #define inFileName "input.txt" #define outFileName "output.txt" void main() { // declare variable FILE *fp; int length = 0; // the length of array int L[MAXSIZE]; // save the elements of array int max = 0, min = 0; // save the result // open input file if ((fp = fopen(inFileName, "r")) == NULL) { printf("cannot open input file: %s\n", inFileName); return; } // read data and judge validness if (fscanf(fp, "%d\n", &length) == EOF) { printf("read data Error!\n"); fclose(fp); return; } if ((length <= 0) || (length > MAXSIZE)) { printf("input data is invalid!\n"); fclose(fp); return; } for (int i = 0; i < length; i++) { if (fscanf(fp, "%d", &L[i]) == EOF) { printf("read data Error!\n"); fclose(fp); return; } } // close file fclose(fp); // call function Max_Min(L, 0, length - 1, &max, &min); // open the output file if ((fp = fopen(outFileName, "w")) == NULL) { printf("cannot open output file: %s\n", outFileName); return; } // write result to output file fprintf(fp, "%d %d", max, min); // close file fclose(fp); } ``` 主程序首先打开输入文件并读取数组长度及元素，然后调用`Max_Min`函数来查找最大值和最小值，并将结果写入输出文件。 ##### 查找最大最小数的核心函数 ```c #include "MaxMin.h" void Max_Min(int L[], int start, int end, int *max, int *min) { int left_max = 0, left_min = 0, right_max = 0, right_min = 0; // only one element if (start == end) { *max = L[start]; *min = L[start]; return; } int mid = (start + end) / 2; Max_Min(L, start, mid, &left_max, &left_min); Max_Min(L, mid + 1, end, &right_max, &right_min); *max = MAX(left_max, right_max); *min = MIN(left_min, right_min); } ``` 这是整个程序的核心部分，采用了递归的方式实现分治法。当子数组只有一个元素时，该元素即是最大值和最小值；否则，继续将数组分为左右两部分，并分别求出左右子数组的最大值和最小值，最终通过宏`MAX`和`MIN`计算出整个数组的最大值和最小值。 ##### 其他代码片段 代码中还包含了另一个不完整的`main`函数和其他未使用的代码片段，这些在实际运行过程中并不发挥作用，可能是因为程序员为了方便调试或其他目的而保留的。 ### 总结 该C代码实现了一个通过分治法查找最大最小数的功能，其中的关键在于递归地将问题规模缩小，并逐步求解。这种算法具有较高的效率，尤其是在处理大规模数据时更为明显。通过对上述代码的学习和理解，我们可以更好地掌握分治法的基本思想及其在实际编程中的应用技巧。