用c语言写出记忆递归算法实现数塔,从顶部出发在每一个节点可以选择向左或者向右走,一直走到底层,要求找出一条路径,使得路径上的数字之和最大。(分别使用动态规划算法和记忆递归算法实现,数塔的数据从下标为1的位置开始存放)
时间: 2024-03-16 15:46:10 浏览: 15
以下是使用记忆递归算法实现数塔的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100
int n;
int tower[MAX_N][MAX_N];
int memo[MAX_N][MAX_N];
int max(int a, int b) {
return a > b ? a : b;
}
int search(int i, int j) {
if (memo[i][j] != -1) {
return memo[i][j];
}
if (i == n) {
memo[i][j] = tower[i][j];
} else {
int left = search(i+1, j);
int right = search(i+1, j+1);
memo[i][j] = tower[i][j] + max(left, right);
}
return memo[i][j];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
scanf("%d", &tower[i][j]);
memo[i][j] = -1;
}
}
int result = search(1, 1);
printf("%d\n", result);
return 0;
}
```
解析:
1. 定义了全局变量 `n` 表示数塔的层数,`tower` 二维数组存储数塔,`memo` 二维数组存储记忆化搜索的结果。
2. `max` 函数用于比较两个数的大小。
3. `search` 函数是记忆递归算法的核心部分,用于搜索从第 $i$ 层第 $j$ 个节点出发可以得到的最大数字和。首先判断 `memo` 数组是否已经计算过该节点的结果,如果已经计算过,则直接返回结果。如果该节点在最后一层,则返回该节点的值,否则递归计算下一层的两个节点的最大值,并加上当前节点的值,将结果存入 `memo` 数组中。
4. `main` 函数用于读入数塔数据,在计算结束后输出结果。
注意:该代码中 `tower` 和 `memo` 数组从下标为1的位置开始存放。