递推概念和例题

一、什么是递推

递推算法以初始值为基础，用相同的运算规律，逐次重复运算，直至求出问题的解，它的本质是按照固定的规律逐步推出（计算出）下一步的结果

这种从“起点”重复相同的的方法直至到达问题的解，犹如单向运动，使用循环来实现 

递推算法的两个核心：

①如何通过已知项得到下一项，找出固定的规律，即：递推公式。

②从什么地方开始递推，确定第一项的值，即：初始状态(初始值)。

二、初试身手

 

这是一个典型递推问题，它的初始状态和递推公式分别是什么。

初始值为第1天的需要的草量f(1)=2。

递推公式为：f(n) = f(n-1)+1 

小编秘方：只要求出一道题的递推公式，题目就迎难而上解决啦

可是递推公式怎么求，让我用真题告诉你

三、小试牛刀

上台阶

题目描述

楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算走到第n阶台阶，共有多少种不同的走法。

输入格式

输入的每一行包括一组测试数据，即为台阶数n。最后一行为0，表示测试结束。

输出格式

每一行输出对应一行输入的结果，即为走法的数目。

输入输出样例

输入样例1：

1
2 
3 
4 
0

输出样例1：

1 
2 
4 
7

 

 

满分代码 

#include<bits/stdc++.h>
using namespace std;
long long a[75];
int main(){int n;a[1]=1;a[2]=2;a[3]=4;while(cin>>n&&n!=0){for(int i=4;i<=n;i++){a[i]=a[i-1]+a[i-2]+a[i-3];}cout<<a[n]<<endl;}return 0;
}

 

 骨牌铺法

题目描述

有2*n的一个长方形方格，用一个1*2的骨牌铺满方格，对于给出的任意一个n（1 <= n<= 46）,输出铺法的总数

输入格式

一行，一个整数n

输出格式

一行，一个整数表示铺法的总数

输入输出样例

输入样例1：

2

输出样例1：

2

#include<bits/stdc++.h>
using namespace std;
long long a[50];
int main(){int n;cin>>n;a[1]=1;a[2]=2;for(int i=3;i<=n;i++){a[i]=a[i-1]+a[i-2];}cout<<a[n];return 0;
}