这个问题很好玩，其实就是找到三角形从顶层到底层经过的数字之和为最大的路径，输出这个和值。这个问题解决途径就是依次计算三角形上每个节点从顶层开始到本节点经过的数字之和的最大值（简称为该节点的权重值），最后从最底层的节点中返回权重值最大的节点的权重即可。应当注意到，考虑到算法的时间复杂性，每个节点的权重值可以分别通过其父节点（0个到2个，从三角形结构上看上一层节点为下一层节点的父节点）的权重值加上本节点数字来计算，并获得其中的最大值。其时间复杂性为O(n^2)。设计程序时可以构造一个表结构，链表或者数组都可以，只要能从每个节点访问到其父节点就可以了。下面的C程序是以数组表结构的方式来实现，已经过调试，仅做参考。#include typedef struct { int val;
// 本节点数字 int sum;
// 本节点劝重值 int lparent; // 左父节点索引 int rparent; // 右父节点索引}NODE;// 输入三角形，并计算每个节点的父节点索引int input_triangle(NODE *p, int nrow);// 计算每个节点的父节点索引int pindex(int index, int min, int max);// 计算权重，并返回最大的权重值int calc_max(NODE *p, int nrow);void main(){ int ntriangle; // 多少个三角形 int nrow;
// 每个三角形多少行 NODE *tnode = NULL; // 数组头指针scanf("%d", &ntriangle);while(ntriangle > 0){
scanf("%d", &nrow);
if (nrow > 0)
{
if (tnode != NULL)
{
free((char *)tnode);
}
tnode = (NODE *)calloc((nrow + 1) * nrow / 2, sizeof(NODE));
if (input_triangle(tnode, nrow) == 1)
{
printf("%d\n", calc_max(tnode, nrow));
}
}
ntriangle--;}if (tnode != NULL){
free((char *)tnode);
tnode = NULL;}}int input_triangle(NODE *p, int nrow){ int i; int j; int k; int n; int val;k = 0; for(i = 0; i99))
{
fprintf(stderr, "Error: bad number '%d'(valid:0~99)\n", val);
return 0;
}
p->val = val;
p->sum = 0;
if (i > 0)
{
n = (i - 1) * i / 2;
p->lparent = pindex(k - i - 1, n, n + i - 1);
p->rparent = pindex(k - i,
n, n + i - 1);
}
else
{
p->lparent = -1;
p->rparent = -1;
}
} } return 1;}int pindex(int index, int min, int max){ return ((indexmax) ? (-1) : index);}int calc_max(NODE *p, int nrow){ int i; int j; int k; int n;p[0].sum = p[0].val;j = (nrow + 1) * nrow / 2; for(i = 1; i = 0)
{
k = p.lparent;
n = p.val + p[k].sum;
if (n > p.sum)
{
p.sum = n;
}
}
if (p.rparent >= 0)
{
k = p.rparent;
n = p.val + p[k].sum;
if (n > p.sum)
{
p.sum = n;
}
} }
n = p[j-NROW].sum; for(i = j - NROW + 1; i < j; i++) {
if (n < p.sum)
{
n = p.sum;
} } return n;} |
