第三章递推算法递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法
这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推
无论顺推还是逆推，其关键是要找到递推式
这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点
递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）
递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算
一般说来，可以将递推算法看成是一种特殊的迭代算法
【例1】数字三角形
如下所示为一个数字三角形
请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大
只要求输出总和
1、一步可沿左斜线向下或右斜线向下走；2、三角形行数小于等于100；3、三角形中的数字为0，1，…，99；测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：5738810274445265【算法分析】此题解法有多种，从递推的思想出发，设想，当从顶层沿某条路径走到第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]即为所求的数字总和的最大值
【参考程序】#includeusingnamespacestd;intmain(){intn,i,j,a[101][101];cin>>n;for(i=1;ia[i][j];//输入数字三角形的值for(i=n-1;i>=1;i--)fo
