递推的计算方法

A. 递推法的一般步骤

所谓递推关系，通链绝培常是指一个数列》的第项a与前面k个项a,a…annn=n2nk
(k为正整数，kn)之间的关系：
an=f(an1,an_2;",an_k)(n>k)

递推法也常用以处理棚唯正整数为状宏雀态函数的数学问题，诸如递归数列的通项问题，与数列有关的计算问题，证明问题，等等，应用递推法解答数学问题，一般包括两个步骤：

第一步：建立递推关系，根据问题的特点，通过观察，试验，归纳，猜想等思维活动，寻求递推关系
第二步：求递推关系初始值和相应的递推关系，求得所需的结论
例1：计算两类带组合数C和Ck的器和Shd=ZCAkm，Un(n)=ZCnkm

B. 常见算法思想2：递推法

递推算法犹如稳重的有经验的老将，使用“稳扎稳打”的策略，不断利用已有的信息推导出新的东西。
在日常应用中有如下两种递推算法：
（1）顺推法：从已知条件出发，逐步推算出要解决问题的方法。
（2）逆推法：从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。

例如斐波那契数列就可以通过顺推法不断递推算出新的数据：

分析:我们要想办法找规律
兔子对数：
第一个月：1；第二个月:1；第三个月: 2；第四个月: 3；第五个月: 5；第六个月: 8；...
由此可见兔子的对象数据是:1,1,2,3,5,8...

规则:
A:从第三项开始,每一项是前两项之程
B:而且说明前两项是已知的

假如相邻的两个月的兔子对数是a,b
第一个相邻的数据:a=1,b=1
第二个相邻的数据:a=1,b=2
第三个相邻的数据:a=2,b=3
第四个相邻的数据:a=3,b=5
看到了:下一次的a是以前的b,下一次的b是以前的a+b;

可采用逆推法分析存钱和取钱的过程，因为按照月为周期取钱，所以4年可以分为48个月，并对每个月进行计算。
如果第48个月后sun大学毕业连本带息要取1000元，则要求第47个月银行的存钱金额为：
第47个月月末存款=1000/(1+0.0172/12);
第46个月月末存款=（第47存款+1000）/(1+0.0172/12);
第45月末存款=（第46存款+1000）/(1+0.0172/12);
…….
第2月月末存款=（第3月月末存款+1000）/(1+0.0172/12);
第1月月末存款=（第2月末存款+1000）/(1+0.0172/12);

打印结果：

C. 递推算法是怎么回事

递推定义
递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。

递推算法分为顺推和逆推两种。

顺推法
所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。

如斐波拉契数列，设它的函数为f(n),已知f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。则我们通过顺推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我们要求的解。

逆推判扰法
所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。

递推与递归的比较
相对于递归算法,递推算法免除了数据进出栈的过程，掘春旦也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值.

比如阶乘函数森禅：f(n)=n*f(n-1)

在f(3)的运算过程中,递归的数据流动过程如下:

f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}

而递推如下:

f(0)-->f(1)-->f(2)-->f(3)

由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推.但是递归作为比较基础的算法,它的作用不能忽视.所以,在把握这两种算法的时候应该特别注意.

D. 数列的递推公式

数列的递进公式，如下所示：

数列的递推公式=n/n+1。如果一个数列的第n项an与该数列的其他一项或多项之间存在对应关系的，这个关系就称为该数列的递推公式。例如斐波纳契数列的递推公式为 an=an-1+an-2。

等差数列递推公式：an=d(n-1)+a（d为公差，a为首项）。

等比数列递推公式：bn=q(n-1)*b （q为公比 b为首项）。

由递推公式写出数列的扰世方法：

1. 根据递推公式写出数列的前几项，依次代入计算即可。

2.若知道的是末项，通常将所给公式整理成用后面的项表示前面的项的形式。

数列的含义：

数列是以正整数集或它的有限子集为定义域的函数，是一列有序的数。数列中的每一个数都叫做这个数列的项。排在第一位的数称为这个数列的第1项，通常也叫喊罩做首项，排在第二位的数称为这个数列的第2项，以此类推，排在第n位的数称为郑李闹这个数列的第n项，通常用an表示。

E. 数列递推算法的原理

什么是递推
所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。
从已知条件出发逐步推到问题结果，此种方法叫顺推。
从问题出发逐步推到已知条件，此种方法叫逆推。
无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。
递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。
递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。

递推的特点
可用递推算法求解的题目一般有以下两个特点：
1、问题可以划分成多个状态；
2、除初始状态外，其它各个状态都可以用固定的递推关系式来表示。
在我们实际解题中，题目不会直接给出递推关系式，而是需要通过分析各种状态，找出递推关系式。

【例1】数字三角形。
如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。

1、 一步可沿左斜线向下或右斜线向下走；
2、 三角形行数小于等于100；
3、 三角形中的数字为0，1，…，99；
测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
【算法分析】
此题解法有多种，从递推的思想出发，设想，当从顶层沿某条路径走到第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] 即为所求的数字总和的最大值。

//【参考程序】
#include<iostream>
using namespace std;
int main(){
int n,i,j,a[101][101];
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
思考
如果要输出最大和的路径该怎么处理呢？

【例2】 骨牌问题
有2 × n的一个长方形方格，用一个1 × 2的骨牌铺满方格。
编写一个程序，试对给出的任意一个n(n>0), 输出铺法总数。
【算法分析】
（1）面对上述问题，如果思考方法不恰当，要想获得问题的解答是相当困难的。可以用递推方法归纳出问题解的一般规律。
（2）当n=1时，只能是一种铺法，铺法总数有示为x1=1。
（3）当n=2时：骨牌可以两个并列竖排，也可以并列横排，再无其他方法，如下左图所示，因此，铺法总数表示为x2=2；

（4）当n=3时：骨牌可以全部竖排，也可以认为在方格中已经有一个竖排骨牌，则需要在方格中排列两个横排骨牌（无重复方法），若已经在方格中排列两个横排骨牌，则必须在方格中排列一个竖排骨牌。如上右图，再无其他排列方法，因此铺法总数表示为x3=3。
由此可以看出，当n=3时的排列骨牌的方法数是n=1和n=2排列方法数的和

F. 什么是递推公式

如果数列{an}的第n项与它前一项或几项的关系可以用一个式子来表示，那么这个公式叫做这个数列仿笑的递推公式。

例如斐波纳契数列的递推公式为an=an-1+an-2

由递推公高宴式写出数列的方法：

1、根据递推公式写出数列的前几项，依次代入计算即可；

2、若知道的是末项，通常将所给公式整理成用后面的项表示前面的项的形式。

(6)递推的计算方法扩展阅读

常见的递推公式，如等差数列。

等差数列从第二项开始每一项是前项和后项的算术平均数。

如果等差数列的公差是正数，则该等戚大银差数列是递增数列；如果等差数列的公差是负数，则该数列是递减数列；如果等差数列的公差等于零，则该数列是常数列。

对于一个数列al，a2，…，an，…，如果它的相邻两项之差a2-a1，a3-a2，…，an+1-an，…构成公差不为零的等差数列，则称数列{an}为二阶等差数列。

运用递归的方法可以依次定义各阶等差数列：对于数列{an}，如果{an+1-an}是r阶等差数列，则称数列{an}是r+1阶等差数列.二阶或二阶以上的等差数列称为高阶等差数列。

G. 怎样用递推法计算行列式

递推法,主要针对带形行列式，例如上面这个行列式的通用解法：

H. 递推的递推算法

【例1】
植树节那天，有五位同学参加了植树活动，他们完成植树的棵树都不相同。问第一位同学植了多少棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；... 如此，都说比另一位同学多植两棵。最后问到第五位同学时，他说自己植了10棵。到底第一位同学植了多少棵树？
分析：设第一位同学植树的棵树为a1,欲求a1，需从第五位同学植树的棵数a5入手，根据“多两棵”这个规律，按照一定顺序逐步进行推算：
(1) a5=10;
(2) a4=a5+2=12;
(3) a3=a4+2=14;
(4) a2=a3+2=16;
(5) a1=a2+2=18;
Pascal程序：
Program Examl;
Var i,a:byte;
begin
a:=10;
for i:= 1 to 4 do
a:=a+2;
writeln('The Num is' ,a);
readln;
end.
本程序的递推运算可用下图示表示：
初始值a:=10 ----- i=1,a=a+2(12) ----- i=2,a=a+2(14) ------ i=3,a=a+2(16) ----- i=4,a=a+2(18) ---- 输出a值
例2：
十本不同的书放在书架上。现重新摆拍渣唯放，使每本书都不在原来放的梁辩位置。有几种摆法？
当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数袭培用M(n)表示,那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.
第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;
第二步,放编号为k的元素,这时有两种情况.1,把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;2,不把它放到位置n,这时,对于这n-1个元素,有M(n-1)种方法;
综上得到
M(n)=(n-1)[M(n-2)+M(n-1)]
递推算法以初始（起点）值为基础，用相同的运算规律，逐次重复运算，直至运算结束。这种从“起点”重复相同的方法直至到达一定“边界”，犹如单向运动，用循环可以实现。递推的本质是按规律逐次推出（计算）先一步的结果。