算法第三章上机实践报告

1.实践题目

数字三角形

给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。

2.问题描述

从顶部开始往下走并且加上每一层上的数字，不断累加结果，使到底底部的时候和最大。

3.算法描述

用二维数组来存放数字三角形：a[i][j]表示第i行第j个数字（i,j从1开始算）
maxsum(i,j)：从a[i][j]到底边的各条路径中，最佳路径的数字之和。
所以问题等于求maxsum（1,1）

4.算法时间及空间复杂度分析（要有分析过程）

（1）直接递归

从a[i][j]开始走，下一步只能往a[r+1][j] 或者a[r+1][j+1]走，想知道从第一行到到底底部的最大数字和，那就得知道从第二行到底部的最大数字和，以此类推。

得到递归方程如下：

if(r == N)
maxsum(i,j) = a[i][j]; //到底底部了，程序结束
else
a(i,j) = Max{maxsum(i+1,j),maxsum(i+1,j+1)} + a[i][j]; //选择较大的

部分代码:

int sum1=maxsum(i+1,j);                                                                                                          
int sum2=maxsum(i+1,j+1);
if(sum1>sum2){
　　return sum1+a[i][j];
}
else{
　　return sum2+a[i][j];
}

程序的缺点是进行了大量的重复运算，导致时间复杂度增加，中间的数字计算次数是上面左右两个数字计算次数之和。一直累加，可得时间复杂度为O（n^2）。

(2)备忘录算法

初始化Maxsum[i][j]的值为0，每算出来一个maxsum(i,j)之后就让Maxsum[i][j]的值为1，即把它的值保存起来。当下次要用到该值的时候直接取用，就可以避免重复计算了，由于三角形的数字总数为n(n+1)/2。所以完成计算的时间复杂度为O(n^2)

部分代码：

if(MaxSum[i][j] != 0){

        return MaxSum[i][j];

}

(3)填表法

从底部开始选择相邻两个数字，与上面的数字进行相加，比如最底部开始是4，5，4上面的数字是7，则选择让5和7相加并将得到的和12填入表中。一直进行这样的操作，从下往上把表填满即可得到a[1][1]是我们想要得到的最大值。可得方程:max{MaxSum[i+1][j],MaxSum[i+1][j+1]} （既选择下一行较大的数字）+a[i][j]

部分代码：

for(int i=n-1;i>=1;--i){//从最底层开始
　　for(int j = 1;j<=n;++j){
　　　　b[i][j] = max(b[i+1][j],b[i+1][j+1]) + a[i][j];//max会选择两个数较大一个数的函数
　　}
}

5.心得体会（对本次实践收获及疑惑进行总结）

刚开始编程的时候直接使用了递归的方法，后来提交的时候发现运行超时，意识到大量的重复计算导致程序的时间复杂度变高，改进后使用了填表法，程序顺利通过。

算法第三章上机实践报告

原文：https://www.cnblogs.com/tinyea/p/11693808.html