入门算法 二 递归

递归

思路：

通过将问题分解为规模较小的同类问题，逐步求解并最终回归到最初问题的答案。
递归的主要思想就是从最后的转态向最初的状态转移，最初的状态的值已知，用最初已知的值来往最后的状态递归，已求解最后的状态的值。

例题1：

code：

#include<iostream>
using namespace std;
int n;
int f(int x){
    if(x==0)return 1;//到达终点算一种走法
    if(x<0)return 0;//超过不算
    return f(x-1)+f(x-2);//当前方法数=上一阶+上两阶的方法数
}
int main(){
    cin>>n;
    cout<<f(n);
    return 0;
}

例题2:

code:

#include<iostream>
#include<bitset>
using namespace std;
using ll=long long;
const int N=100;
bitset<N>vis[N];
int mx[]={2,1,-1,-2,2,1,-1,-2};
int my[]={1,2,-2,-1,-1,-2,2,1};
int n,m;//终点
int hx,hy;//马的位置
int s=0;//记录步数
int f(int a,int b){
    //马的位置的数量f(x,y)=f(x-1,y)+f(x,y-1);
    if(a<0||b<0)return 0;
    if(a==0&&b==0)return 1;
    if(vis[a][b])return 0;//马的位置
    return f(a-1,b)+f(a,b-1);
}
int main(){
    cin>>n>>m>>hx>>hy;
    vis[hx][hy]=true;
    for(int i=0;i<8;i++){
        int x=hx+mx[i];
        int y=hy+my[i];
        if(x>=0&&x<=n&&y>=0&&y<=m)vis[x][y]=true;
    }
    cout<<f(n,m);
    return 0;
}

例题3:

code:

#include<iostream>
using namespace std;
using ll=long long;
const int N=20;
int n;
ll a[N][N];
ll f(int i,int j){//i表示剩余需要入栈的元素数，j表示当前栈内的元素数
    //没有入栈的元素，且当前栈内的元素为空
    if(i==0&&j==0)return 1;
    ll res=0;
    //入栈
    if(i>0)res+=f(i-1,j+1);
    //出栈
    if(j>0)res+=f(i,j-1);
    return res;
}
int main(){
    cin>>n;
    cout<<f(n,0);
    return 0;
}

例题4:

code：

#include<iostream>
using namespace std;
int n;
int f(int x){//以x为开头的合法数列的数量
    //边界是当x<=0时，不能构造合法数列，返回0，由于递归调用都默认x>0，所以边界不会触发
    //初始化为1，因为只有它本身的话，答案是1
    int cnt=1;
    //遍历每一个可以添加到以x为开头的后面的元素值
    //枚举的元素继续递归就可以求出将每一个以枚举出来的数为开头符合条件的情况了，然后求和，则求出最后的答案
    //递归的终点是f(1)=1;
    for(int i=1;i<=x/2;i++)cnt+=f(i);
    return cnt;
}
int main(){
    cin>>n;
    cout<<f(n);
    return 0;
}

例题5:

code：

#include<iostream>
using namespace std;
using ll=long long;
const int N=25;
ll f[N][N][N];
ll w(ll a,ll b,ll c){
    //处理边界
    if(a<=0||b<=0||c<=0)return 1;
    if(a>20||b>20||c>20)return w(20,20,20);
    //记忆化
    if(f[a][b][c])return f[a][b][c];
    //题意
    if(a<b&&b<c)f[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    else f[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
    return f[a][b][c];
}
int main(){
    ll a,b,c;
    while(cin>>a>>b>>c){
        if(a==-1&&b==-1&&c==-1)break;
        cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<w(a,b,c)<<'\n';
    }
    return 0;
}