Question

数字三角形 用C++编程

问题描述：
给定一个有n行数字组成的数字三角形，如图所示，试设计一个算法，计算出三角形顶至底的一条路径，使该路径经过的数字总和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

编程任务：
对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和最大值。

Answer 1

#include<iostream.h>
#define n 5 //设定三角形为5层,可修改
void main()
{
int sum=0,a[n][n],i,j,max;
cout<<"请按行输入三角形值：\n";
for(i=0;i<n;i++)//将三角形数值存入一个二维数组
{
cout<<"第"<<i+1<<"行：";
for(j=0;j<=i;j++)
cin>>a[i][j];
}
cout<<"输入三角形为：\n";
for(i=0;i<n;i++)//显示输入的三角形数值
{
for(j=0;j<=i;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
cout<<"最佳路径为:\n";
for(i=0;i<n;i++)//要从三角形的顶至底的路径经过的数字和最大,则每行都取最大值
{
max=a[i][0];//以下求每行的最大值
for(j=1;j<=i;j++)
if(max<a[i][j])
max=a[i][j];
cout<<max<<" ";
sum+=max;//求最大值的和
}
cout<<"\n最长路径为："<<sum<<endl;
}