问题描述

给字一个由n行数字组成的数字三角形（等腰三角形）。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

输入

数字三角形的行数和数字三角形

输出

最大的路径和以及路径

输入样例

5 7 8 3 9 8 7 1 2 3 4 4 5 6 7 8

输出样例

33 7 8 8 3 7

提示

输入：请输入数字三角形的行数： 请输入数字三角形：

输出：路径总和最大为： 自顶向下的路径为:

完整代码：

#include "stdafx.h" int main(int argc, char* argv[]) { int i,j,n; int a[100][100];//用于存放三角形 int b[100][100];//用于复制a数组 printf("请输入数字三角形的行数：\n"); scanf("%d",&n);//获取输入的行数 printf("请输入数字三角形：\n"); for(i=1;i<=n;i++){ for(j=1;j<=i;j++){ scanf("%d",&a[i-1][j-1]);//输入三角形 b[i-1][j-1]=a[i-1][j-1];//复制 } } for(int row=n-2;row>=0;row--){//从倒数第二行开始往上递推 for(int col=0;col<=row;col++){ if(a[row+1][col]>a[row+1][col+1]){//将每个数下面的两个数进行比较 a[row][col]+=a[row+1][col]; //取较大的数加 } else{ a[row][col]+=a[row+1][col+1]; } } } printf("路径总和最大为：\n"); printf("%d\n",a[0][0]); printf("自顶向下的路径为:\n"); printf("%d ",b[0][0]);//先输出第一行的数字 int l=0;//定义列 for(int m=1;m<n;m++){//从第二行开始往下递推 if(a[m][l]>a[m][l+1]){ printf("%d ",b[m][l]);//根据数值较大的数的位置输出b数组中指定位置的值 }else{ printf("%d ",b[m][l+1]); l=l+1;//如果较大的数为右边的数则下次开比较的列加1 } } printf("\n"); return 0; }

测试

测试用例1：根据提示输入数字三角形的行数为5，输入数字三角形为 7 8 3 9 8 7 1 2 3 4 4 5 6 7 8 回车后系统显示路径总和最大的值为33，以及自顶向下的路径为7 8 8 3 7

测试用例2：根据提示输入数字三角形的行数为6，输入数字三角形为 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 7 8 9 10 11 12 回车后系统显示路径总和最大的值为39，以及自顶向下的路径为7 3 8 7 5 9