主要内容 #

1. 递推算法概述
2. 数塔问题
3. 算法分析
4. 参考程序

1. 递推算法概述 #

一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。
递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。

2. 数塔问题 #

如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。
1、 一步可沿左斜线向下或右斜线向下走；
2、 三角形行数小于等于100；
3、 三角形中的数字为0，1，…，99；
测试数据通键盘逐行输入，如上例数据应以如下所示格式输入：

                      5
    7                 7
   3 8                3 8
  8 1 0               8 1 0
 2 7 4 4              2 7 4 4 
4 5 2 6 5             4 5 2 6 5
                      输入的数据

3. 算法分析 #

从递推的思想出发，设想，当从顶层沿某条路径走到第i层向第i+1层前进时，我们的选择一定是沿其下两条可行路径中最大数字的方向前进，为此，我们可以采用倒推的手法，设a[i][j]存放从i,j 出发到达n层的最大值，则a[i][j]=max{a[i][j]+a[i+1][j]，a[i][j]+a[i+1][j+1]}，a[1][1] 即为所求的数字总和的最大值。

4. 参考程序 #

#include < iostream >
using namespace std;
int main(){
    int n, i, j, a[101][101];
    //输入数塔的行数n
    cin >> n;
    //逐行输入数据
    for(i = 1; i <= n; ++i){
        for(j = 1; j <= i; ++j){
            cin >> a[i][j];
        }
    }
    //采用倒推的手法，从底层往上推
    for(i = n - 1; i >= 1; i--){
        for(j = 1; j <= i; j++){
            if(a[i + 1][j] >= a[i + 1][j + 1]){
                a[i][j] += a[i + 1][j];
            }else{
                a[i][j] += a[i + 1][j + 1];
            }
        }
    }
    //输出结果
    cout << a[1][1] << endl;
    return 0;
}