问题描述:从数塔的顶层出发,在每一个结点可以选择向左走或向右走,一直走到最底层,要求找出一条路径,使得路径上的数值和最大。
一个示例:
算法思想
输入:二维数组data[n][n]
8 | ||||
12 | 15 | |||
3 | 9 | 6 | ||
8 | 10 | 5 | 12 | |
16 | 4 | 18 | 10 | 9 |
输出:数塔的最大数值和及其路径
1.for循环初始化数组addmax的最后一行为数塔底层 数据;
2.从n-1层开始直到第1层对下三角元素addmax进行求和,并用path[i][j]记录路径;
第一层 |
8+max{49,52} =60 |
||||
第二层 |
12+max{31,37} =49 |
15+max{37,29} =52 |
|||
第三层 |
3+max{24,28} =31 |
9+max{28,23} =37 |
6+max{23,22} =29 |
||
第四层 |
8+max{16,14} =24 |
10+max{4,18} =28 |
5+max{18,10} =23 |
12+max{10,9} =22 |
|
初始化 | 16 | 4 | 18 | 10 | 9 |
3.输出最大值和最佳路径。
注:path
是一个二维数组,i
和j
是下标,表示访问path
数组中的某个元素。将j
赋值给path[i][j]
,即将j
存储到path
数组的(i, j)
位置。
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<math.h>
int main() {
int i, j;
int n;
printf("请输入数塔层数:");
scanf("%d", &n);
int data[10][10];
int addmax[10][10];
int path[10][10];
printf("请输入数塔:\n");
for (i = 0; i < n; i++) {
for (j = 0; j <= i; j++) {
scanf("%d", &data[i][j]);
}
} //以数组形式将数塔输入
for (j = 0; j < n; j++) {
addmax[n - 1][j] = data[n - 1][j];
} //将数塔最底层数据传给addmax数组
for (i = n - 2; i >= 0; i--) {
for (j = 0; j <= i; j++) {
if (addmax[i + 1][j] > addmax[i + 1][j + 1]) {
addmax[i][j] = data[i][j]+addmax[i + 1][j];//求最大和
path[i][j] = j;//标记路径
}
else {
addmax[i][j] = data[i][j]+addmax[i + 1][j + 1];
path[i][j] = j + 1;
}
}
}
printf("%d", addmax[0][0]);
printf("[%d", data[0][0]);
j = path[0][0];
for (i = 1; i < n; i++) {
printf("-->%d", data[i][j]);
j = path[i][j];
}
printf("]");
return 0;
}
版权声明:本文为博主作者:≈浅念°638原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/qq_64228554/article/details/134652782