数塔问题算法c语言,利用vc6.0实行,能运行有结果
时间: 2024-03-12 17:44:55 浏览: 15
数塔问题是一个经典的动态规划问题,其算法如下:
1. 先读入数塔的高度n和数塔本身tower;
2. 从下往上遍历数塔,对于每个数塔中的数字tower[i][j],计算出它的最大和maxSum[i][j],即从该数开始一直走到塔顶时的最大和。
3. 最后maxSum[1][1]中存储的就是整个数塔的最大和。
下面是C语言的实现代码:
```
#include <stdio.h>
#define MAX_N 100
int n;
int tower[MAX_N][MAX_N];
int maxSum[MAX_N][MAX_N];
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
// 读入数塔的高度和数塔本身
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
scanf("%d", &tower[i][j]);
}
}
// 从下往上遍历数塔,计算出每个数的maxSum
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
maxSum[i][j] = max(maxSum[i+1][j], maxSum[i+1][j+1]) + tower[i][j];
}
}
// 输出整个数塔的最大和
printf("%d\n", maxSum[1][1]);
return 0;
}
```
你可以在VC6.0中创建一个新的控制台应用程序,将上述代码复制到main函数中,编译并运行即可得到结果。