面试算法题（对于笔试或机试很有用）

### 知识点总结 #### 1. 整数逆序存储至数组（递归实现） **题目描述：** 此题考察的是递归的基本运用，要求将一个整数逆序后存储到数组中。 **代码解析：** ```cpp void convert(int* result, int n) { if (n >= 10) // 当数字大于等于10时，递归调用，处理更高位的数字 convert(result + 1, n / 10); *result = n % 10; // 取最低位数字，并存储到数组中 } int main(int argc, char* argv[]) { int n = 123456789, result[20] = {}; convert(result, n); // 调用函数 printf("%d:", n); // 打印原始数字 for (int i = 0; i < 9; i++) // 循环打印逆序后的数字 printf("%d", result[i]); } ``` **解析：** - `convert` 函数使用递归方式，首先检查数字是否大于等于10。 - 如果大于等于10，则先递归调用自身处理更高位的数字，再处理当前位。 - 最后将结果存储在数组中。 #### 2. 求高于平均分的学生学号及成绩 **题目描述：** 本题要求输入学生学号和成绩，计算平均分，并输出所有高于平均分的学生学号及成绩。 **代码解析：** ```cpp double find(int total, int n) { int number, score, average; scanf("%d", &number); // 输入学号 if (number != 0) { // 如果学号不为0 scanf("%d", &score); // 输入成绩 average = find(total + score, n + 1); // 递归累加总分和人数 if (score >= average) // 成绩高于平均分则输出 printf("%d:%d\n", number, score); return average; // 返回平均分 } else { printf("Average=%d\n", total / n); // 输出平均分 return total / n; // 返回平均分 } } int main(int argc, char* argv[]) { find(0, 0); // 调用函数 } ``` **解析：** - `find` 函数通过递归计算平均分，并判断成绩是否高于平均分。 - 使用条件判断来控制递归的终止条件。 - 使用全局变量的方式简化了递归的参数传递。 #### 3. 递归实现回文判断 **题目描述：** 本题要求判断一个字符串是否为回文。 **代码解析：** ```cpp int find(char* str, int n) { if (n <= 1) // 字符串长度小于等于1时，返回1 return 1; else if (str[0] == str[n - 1]) // 如果首尾字符相等 return find(str + 1, n - 2); // 递归检查剩余子串 else return 0; // 不是回文 } int main(int argc, char* argv[]) { char* str = "abcdedcba"; printf("%s:%s\n", str, find(str, strlen(str)) ? "Yes" : "No"); // 输出结果 } ``` **解析：** - `find` 函数通过递归比较字符串首尾字符是否相同来判断是否为回文。 - 使用递归方式减少代码复杂度。 #### 4. 组合问题 **题目描述：** 从M个不同字符中任取N个字符的所有组合。 **代码解析：** ```cpp void find(char* source, char* result, int n) { if (n == 1) { // 当N=1时，输出所有单个字符 while (*source) printf("%s%c\n", result, *source++); } else { // 否则继续递归 int i, j; for (i = 0; source[i] != 0; i++); for (j = 0; result[j] != 0; j++); for (; i >= n; i--) { result[j] = *source++; // 将字符复制到结果数组 result[j + 1] = '\0'; // 结束标志 find(source, result, n - 1); // 递归 } } } int main(int argc, char* argv[]) { int const n = 3; char* source = "ABCDE", result[n + 1] = {0}; if (n > 0 && strlen(source) > 0 && n <= strlen(source)) find(source, result, 3); // 调用函数 } ``` **解析：** - `find` 函数采用递归方式实现，当N=1时直接输出所有单个字符。 - 否则递归地选取字符并输出组合。 - 使用递归简化了逻辑处理。 #### 5. 分解成质因数 **题目描述：** 将一个数分解为其质因数的形式。 **代码解析：** ```cpp void prim(int m, int n) { if (m > n) { // 当m>n时，继续分解 while (m % n != 0) n++; // 寻找能整除的质数 m /= n; // 更新m prim(m, n); // 递归调用 printf("%d*", n); // 打印质因数 } } int main(int argc, char* argv[]) { int n = 435234; printf("%d=", n); // 输出原数 prim(n, 2); // 调用函数 } ``` **解析：** - `prim` 函数使用递归方式找到能整除的质数。 - 通过递归不断地分解直到不能再分解为止。 - 该方法适用于较小的数字。 #### 6. 寻找迷宫的一条出路 **题目描述：** 寻找从起点到终点的路径，起点和终点已知。 **代码解析：** ```cpp #define MAX_SIZE 8 int H[4] = {0, 1, 0, -1}; int V[4] = {-1, 0, 1, 0}; char Maze[MAX_SIZE][MAX_SIZE] = { {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'}, {'o', 'o', 'o', 'o', 'o', 'X', 'X', 'X'}, {'X', 'o', 'X', 'X', 'o', 'o', 'o', 'X'}, {'X', 'o', 'X', 'X', 'o', 'X', 'X', 'o'}, {'X', 'o', 'X', 'X', 'X', 'X', 'X', 'X'}, {'X', 'o', 'X', 'X', 'o', 'o', 'o', 'X'}, {'X', 'o', 'o', 'o', 'o', 'X', 'o', 'o'}, {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'} }; void FindPath(int X, int Y) { if (X == MAX_SIZE || Y == MAX_SIZE) { // 达到边界 for (int i = 0; i < MAX_SIZE; i++) // 打印路径 for (int j = 0; j < MAX_SIZE; j++) printf("%c", Maze[i][j]); } else { // 未达到边界 // ...（此处省略具体实现细节） } } int main(int argc, char* argv[]) { FindPath(1, 1); // 假设起点为(1,1) } ``` **解析：** - 通过定义迷宫地图以及方向数组来实现路径查找。 - 使用递归方式尝试不同的路径，直到找到一条有效的出路。 - 实现中还需要考虑具体的边界条件和路径更新逻辑。 以上算法题目涵盖了递归、字符串处理、数据结构等多个方面，适合面试前进行练习。