算法分析设计题—数字三角形问题
5星 · 超过95%的资源 需积分: 20 5 浏览量
2011-01-04
16:29:09
上传
评论
收藏 28KB DOC 举报 
数字三角形问题
问题描述：
给定一个有 n 行数字组成的数字三角形，如图所示，试设计一个算法，计算出三角形
顶至底的一条路径，使该路径经过的数字总和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
编程任务：
对于给定的由 n 行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的
数字和最大值。
int N;
int fmax(int a,int b)
{
return a> b?a:b;
}
int f(int row,int col)//f(0,0)即为所要求的值,row 表示行数
{
//f(0,0)=max(f(1,0),f(1,1))+a[0][0]
if(row==N-2)//倒数第二层
return fmax(a[row+1][col],a[row+1][col+1])+a[row][col];
return fmax(f(row+1,col),f(row+1,col+1))+a[row][col];
}
int main()
{
/*输入三角形的行数*/
cin>> N;
/*输入每行的数*/
for(int i=0;i <N;i++)
for(int j=0;j <i+1;j++)
cin>> a[i][j];
cout <<f(4,0)<<endl;
cout <<f(3,0)<<endl;
cout <<f(2,0)<<endl;
cout <<f(1,0)<<endl;
cout <<f(0,0)<<endl;
return 0;
}
资源评论
qq_164969852015-01-12我下载错了，不过在这个程序上面得到了一些不错的启发
happylj04252012-10-13程序运行不出来呀
