递推算法

算法

###1递推的步骤

确定递推变量
建立递推关系
确定变量的初值
确定边界条件
对递推过程进行控制 )1当所需递推次数是固定的,可以构造一个固定次数的循环 )2当所需递推次数是不固定的,可以根据具体情况归纳出递推结束的条件 ###2递推算法的框架

简单的顺推算法

for(1~i-1)=初值;               //确定初值
for(k=i;k<=n;k++)
f(k)=<递推关系>`            //根据递推关系顺推

简单的逆推算法

    for(n~i+1)=初值                     //确定初值
    for(k=i;k>=1;k--)
    f(k)=递推关系;              //根据递推关系逆推

二维数组顺推算法设递推二维数组为f(k,j),1<=k&&k<=n,1<=j&&j<=m,由初次条件求的f(1,1),f(1,2),....f(1,m),需求f(n,m) ,则根据所给定的递推关系由初次条件顺推得f(2,1),f(2,2).....f(2,m);以此类推直到求出f(n,m) for(1,1~m)=初值; //确定初值 for(k=2;k<=n;k++) for(j=1;j<=m;j++) f(k,j)=递推关系 //根据递推关系求值
多关系的递推关系
```
   f(1~i-1)=初值;
   for(k=i;k<=n;k++)
   {if(条件1)
       f(k)=递推关系1;
   if(条件2)
       f(k)=递推关系2;
       .
       .
       .
   if(条件N)
       f(k)=递推关系N;
```
} ###3 例子假设你现在正在爬楼梯，楼梯有 nn 级。每次你只能爬 11 级或者 22 级，那么你有多少种方法爬到楼梯的顶部？ #include<stdio.h> int a[100]; int main(){ int n,i; scanf("%d",&n); a[1]=1;a[2]=2; //确定初值 for(i=3;i<=n;i++) a[i]=a[i-1]+a[i-2]; //递推关系 printf("%d",a[n]);
}

Provide feedback