C语言 数据结构 经典算法大全

### C语言 数据结构 经典算法大全 #### 河内之塔 **知识点：** - **背景介绍：** 河内之塔是一个著名的递归问题，最初由法国数学家Édouard Lucas在1883年提出。根据传说，越南的一座寺庙中有64个金盘，僧侣们需要将这些盘子从一根柱子移动到另一根柱子上，但只能按照大小顺序移动，即大盘不能放在小盘之上。根据传说，当所有盘子都完成移动时，世界就会终结。 - **问题定义：** 河内之塔问题可以定义为：给定三个柱子（通常标记为A、B、C），在第一个柱子上有n个不同大小的盘子，按照从大到小的顺序堆叠在一起。目标是将所有盘子从第一个柱子移动到第三个柱子上，但在任何时候，大盘都不能放在小盘之上。 - **递归算法实现：** - 基本思想：将问题分解为规模较小的相同问题。对于n个盘子，可以先将n-1个盘子从A柱子移动到B柱子上，然后将最大的一个盘子从A柱子移动到C柱子上，最后再将n-1个盘子从B柱子移动到C柱子上。 - 代码实现： ```c void hanoi(int n, char from, char to, char aux) { if (n == 1) { printf("Move disk 1 from %c to %c\n", from, to); } else { hanoi(n - 1, from, aux, to); printf("Move disk %d from %c to %c\n", n, from, to); hanoi(n - 1, aux, to, from); } } ``` - 时间复杂度：每个盘子都要移动两次，因此总的操作次数为2^n-1次，时间复杂度为O(2^n)。 #### 费式数列 **知识点：** - **定义：** 费式数列(Fibonacci sequence)是一个数列，其中每个数字是前两个数字的和。数列通常从0和1开始。 - **递归实现：** - 基本思路：F(n) = F(n-1) + F(n-2)，其中F(0) = 0, F(1) = 1。 - 代码实现： ```c int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); } ``` - 缺点：重复计算问题严重，时间复杂度为指数级O(2^n)。 - **动态规划实现：** - 解决方法：使用数组存储已计算过的值，避免重复计算。 - 代码实现： ```c int fibonacciDP(int n) { if (n <= 1) return n; int f[n+1]; f[0] = 0; f[1] = 1; for (int i = 2; i <= n; i++) f[i] = f[i-1] + f[i-2]; return f[n]; } ``` - 时间复杂度：O(n)。 #### 巴斯卡三角形 **知识点：** - **定义：** 巴斯卡三角形(Pascal's Triangle)是一种三角形排列的数字，每一行的数字都是上一行相邻两数之和。 - **生成方式：** - 第0行只有一个数字1。 - 对于第n行（n>0），第k个数字等于上一行的第k-1个数字加上第k个数字。 - **代码实现：** - 使用二维数组来存储巴斯卡三角形的每一行。 - 代码示例： ```c void pascalTriangle(int n) { int triangle[n][n]; memset(triangle, 0, sizeof(triangle)); for (int line = 0; line < n; line++) { triangle[line][0] = triangle[line][line] = 1; for (int j = 1; j < line; j++) triangle[line][j] = triangle[line-1][j-1] + triangle[line-1][j]; } // 输出巴斯卡三角形 for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) printf("%d ", triangle[i][j]); printf("\n"); } } ``` - 时间复杂度：O(n^2)。 以上内容介绍了河内之塔、费式数列以及巴斯卡三角形这三个经典的算法问题。通过这些例子，我们可以看到递归与动态规划在解决这类问题中的应用。这些算法不仅有助于提高编程能力，还能加深对数据结构和算法原理的理解。