递推概念和例题

递推概念和例题

引用

CSDN

1.

https://m.blog.csdn.net/wangzihao0910/article/details/144037431

一、什么是递推

递推算法以初始值为基础，用相同的运算规律，逐次重复运算，直至求出问题的解，它的本质是按照固定的规律逐步推出（计算出）下一步的结果
这种从“起点”重复相同的方法直至到达问题的解，犹如单向运动，使用循环来实现
递推算法的两个核心：

1. 如何通过已知项得到下一项，找出固定的规律，即：递推公式。
2. 从什么地方开始递推，确定第一项的值，即：初始状态(初始值)。

二、初试身手

这是一个典型递推问题，它的初始状态和递推公式分别是什么。
初始值为第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;
}  

骨牌铺法

题目描述
有2n的一个长方形方格，用一个12的骨牌铺满方格，对于给出的任意一个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;
}