C++/C程序题

来源：百度知道 编辑：UC知道 时间：2024/05/15 10:42:38
The Triangle
Time Limit: 1000ms, Special Time Limit:2000ms, Memory Limit:32768KB
Total submit users: 191, Accepted users: 180
Problem 10014 : No special judgement
Problem description
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

(Figure 1)

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

Input
Your program is to read from standard input. The first line contains one integer T, the number of test cases, for each test case: the first line contain a integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.

Output <

这个问题很好玩，其实就是找到三角形从顶层到底层经过的数字之和为最大的路径，输出这个和值。
这个问题解决途径就是依次计算三角形上每个节点从顶层开始到本节点经过的数字之和的最大值（简称为该节点的权重值），最后从最底层的节点中返回权重值最大的节点的权重即可。应当注意到，考虑到算法的时间复杂性，每个节点的权重值可以分别通过其父节点（0个到2个，从三角形结构上看上一层节点为下一层节点的父节点）的权重值加上本节点数字来计算，并获得其中的最大值。其时间复杂性为O(n^2)。
设计程序时可以构造一个表结构，链表或者数组都可以，只要能从每个节点访问到其父节点就可以了。下面的C程序是以数组表结构的方式来实现，已经过调试，仅做参考。

#include <stdio.h>

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 (nro