递归

正如郭伟老师讲的，递归怎么讲都不为过。自以为基本功扎实的我认为自己对递归已经足够了解，上了郭伟老师的课发现自己还只是一知半解啊啊啊。所以还是要谦虚，要及时认真的做笔记。

递归有一下几个重要的作用：

替代多重循环（特别是在重数不确定的时候）
解决本来就是用递归形式定义的问题
将问题分解为规模更小的子问题进行求解

1替代多重循环（特别是在重数不确定的时候）

典型问题：求阶乘，N皇后

2解决本来就是用递归形式定义的问题

典型问题：表达式求值，汉诺塔

2.1表达式求值

递归定义的形式：

表达式：项，项和项的加减运算

项：因子，因子和因子的乘除运算

因子：'(’ 表达式 ')'，整数

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#define DEBUG(x) cout << #x << " = " << x << endl
using namespace std;
int exp_value();
int term_value();
int fact_value();
int exp_value()
{
    int result=term_value();
    bool more=true;
    while(more){
        char c=cin.peek();
        if(c=='+'||c=='-'){
            cin.get();
            int t=term_value();
            if(c=='+')result+=t;
            else result-=t;
        }
        else more=false;
    }
    return result;
}
int term_value()
{
    int result=fact_value();
    bool more=true;
    while(more){
        char c=cin.peek();
        if(c=='/'||c=='*'){
            cin.get();
            int t=fact_value();
            if(c=='/')result/=t;
            else result*=t;
        }
        else more=false;
    }
    return result;
}
int fact_value()
{
    int result=0;
    char c=cin.peek();
    if(c=='('){//c='c'
        cin.get();
        result=exp_value();
        cin.get();
    }
    else {
        while(isdigit(c)){
            result=result*10+c-'0';
            cin.get();
            c=cin.peek();
        }
    }
    return result;
}
int main()
{
    freopen("in.txt","r",stdin);
    printf("%d
",exp_value());
    return 0;
}

View Code

2.2汉诺塔

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#define DEBUG(x) cout << #x << " = " << x << endl
using namespace std;
///汉诺塔问题
///解决本来就是用递归形式定义的问题
void hanoi(int n,char src,char mid,char dst)
{
    if(n==1){
         cout<<src<<"->"<<dst<<endl;
        return;
    }
    hanoi(n-1,src,dst,mid);
    cout<<src<<"->"<<dst<<endl;
    hanoi(n-1,mid,src,dst);

}
int main()
{
//    freopen("in.txt","r",stdin);
    hanoi(8,'A','B','C');
    return 0;
}

View Code

3将问题分解为规模更小的子问题进行求

典型问题：上台阶，放苹果，算24

3.1上台阶

还是有点不太明白，为什么f（n）=f（n-1）+f（n-2）？

#include<iostream>
#include<cstdio>
using namespace std;
int N;
int stairs(int n)
{
    if(n<0)return 0;
    if(n==0)return 1;
    return stairs(n-1)+stairs(n-2);
}
int main()
{
    freopen("in.txt","r",stdin);
    while(cin>>N){
        cout<<stairs(N)<<endl;
    }
}

View Code

3.2放苹果

实话说，我根本想不出来。。。

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#define DEBUG(x) cout << #x << " = " << x << endl
using namespace std;
int apple(int m,int n)
{
    if(n>m)return apple(m,m);
    if(m==0)return 1;
    if(n==0)return 0;
    return apple(m,n-1)+apple(m-n,n);
}
int main()
{
    int t,m,n;
    freopen("in.txt","r",stdin);
    cin>>t;
    while(t--){
        cin>>m>>n;
        cout<<apple(m,n);
    }
    return 0;
}

View Code

3.3算24

比较经典，4个数算二十四，可以先算两个数，之后就是三个数算24，将问题分解为规模更小的子问题进行求解，大概就是这个意思吧。

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#define DEBUG(x) cout << #x << " = " << x << endl
#define EPS 1e-6
using namespace std;
double a[5];
bool isEqual(double a,double b) {
    return abs(a-b)<=EPS;
}
bool count24(double a[],int n) {
    int m=0;
    double b[5];
    if(n==1) {
//            DEBUG(a[0]);
        if(isEqual(a[0],24.0))
            return true;
        else
            return false;
    }
    for(int i=0; i<n-1; i++) {
        for(int j=i+1; j<n; j++) {
            for(int k=0; k<n; k++) {
                if(k!=i&&k!=j) {
                    b[m++]=a[k];
                }
            }
            double r;
            r=a[i]+a[j];
            b[m]=r;
            if(count24(b,m+1))
                return true;

            r=a[i]-a[j];
            b[m]=r;
            if(count24(b,m+1))
                return true;

            r=a[j]-a[i];
            b[m]=r;
            if(count24(b,m+1))
                return true;
            if(!isEqual(a[i],0)) {
                r=a[j]/a[i];
                b[m]=r;
                if(count24(b,m+1))
                    return true;
            }
            if(!isEqual(a[j],0)) {
                r=a[i]/a[j];
                b[m]=r;
                if(count24(b,m+1))
                    return true;
            }
        }
    }
    return false;
}
int main() {
    freopen("in.txt","r",stdin);
    for(int i=0;i<4;i++){
        cin>>a[i];
    }
    printf("%d
",count24(a,4));
    printf("%d
",true);
    return 0;
}

View Code