递归习题题解

C++奥赛一本通刷题记录(递归)

2017.11.9 By gwj1139177410

  1. 逆波兰表达式 openjudge1696

    //栈比较坑。。。
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>
    char a[3010];
    double trans(){ //float is bugs
       scanf("%s",a);
       if(strlen(a)==1){
           if(a[0]=='+')return trans()+trans();
           if(a[0]=='-')return trans()-trans();
           if(a[0]=='*')return trans()*trans();
           if(a[0]=='/')return trans()/trans();
       }else{
           return atof(a);
       }
    }
    int main(){
       printf("%f\n", trans());
       return 0;
    }
    
  2. 全排列 openjudge1750

    //直接套模板,据说STL也能水
    #include<cstdio>
    #include<cstring>
    const int maxn = 110;
    char a[maxn], b[maxn];
    int n, vis[maxn];
    void dfs(int cur){
       if(cur == n){
           for(int i = 0; i < n; i++)putchar(b[i]);
           printf("\n");
       }else for(int i = 0; i < n; i++){
           if(!vis[i]){
               vis[i] = 1;
               b[cur] = a[i];
               dfs(cur+1);
               vis[i] = 0;
           }
       }
    }
    int main(){
       scanf("%s", a); n = strlen(a);
       dfs(0);
       return 0;
    }
    
  3. 分解因数 openjudge1751

    //这题我第一个想法是排列组合,数论,然后。。。。
    #include<iostream>
    using namespace std;
    int f(int n, int m){ //找n的分解方案数
       if(n == 1)return 0;
       int ans = 1; //加上题目自己算一个值
       for(int i = m; i*i <= n; i++)//枚举n的每个约数,每次除掉(从小到大去重)
           if(n%i==0)ans += f(n/i,i);
       return ans;
    }
    int main(){
       int T;  cin>>T;
       while(T--){
           int n;  cin>>n;
           cout<<f(n,2)<<"\n";//找约数从2开始
       }
       return 0;
    }
    
  4. 斐波那契数列 openjudge1755

    //╮( ̄▽ ̄)╭数据太水我也没办法
    #include<iostream>
    using namespace std;
    int f(int n){
       return n==1||n==2?1:f(n-1)+f(n-2);
    }
    int main(){
       int T;  cin>>T;
       while(T--){
           int n;  cin>>n;
           cout<<f(n)<<"\n";
       }
       return 0;
    }
    
  5. pell数列 openjudge1788

    //(⁄ ⁄•⁄ω⁄•⁄ ⁄)这个没有记忆化药丸了
    #include<iostream>
    using namespace std;
    int f[1000010];
    int fn(int n){
       return f[n]?f[n]:f[n]=(2*fn(n-1)+fn(n-2))%32767;
    }
    int main(){
       f[1]=1; f[2]=2;
       int T;  cin>>T;
       while(T--){
           int n;  cin>>n;
           cout<<fn(n)<<"\n";
       }
       return 0;
    }
    
  6. 括号匹配问题 openjudge2705

    //模拟题一番水
    #include<iostream>
    #include<string>
    #include<stack>
    using namespace std;
    int main(){
       string s, t;
       stack<int>sk, tk;
       while(getline(cin,s)){
           t.resize(s.size());
           for(int i = 0; i < s.size(); i++){
               t[i] = ' ';
               if(s[i]=='(')sk.push(i);
               if(s[i]==')'){
                   if(sk.size())sk.pop();
                   else tk.push(i);
               }
           }
           while(sk.size()){
               t[sk.top()] = '$';
               sk.pop();
           }
           while(tk.size()){
               t[tk.top()] = '?';
               tk.pop();
           }
           cout<<s<<"\n"<<t<<"\n";
       }
       return 0;
    }
    
  7. 爬楼梯 openjudge3089

    #include<iostream>
    using namespace std;
    int a[50];
    int f(int n){
       return a[n]?a[n]:a[n]=f(n-1)+f(n-2);
    }
    int main(){
       a[1]=1; a[2]=2; //稍微注意一下边界就好啦
       int n;
       while(cin>>n){
           cout<<f(n)<<"\n";
       }
       return 0;
    }
    
  8. 汉诺塔问题 openjudge6261

    //这种就是经常出现在初赛看程序写结果里面的
    //ha2():将n个盘子从a经过c移动到b
    #include<iostream>
    using namespace std;
    void ha2(int n, char a, char b, char c){
       if(!n)return ;
       ha2(n-1,a,c,b); //把前n-1个盘子移动到辅助的杆c
       cout<<a<<"->"<<n<<"->"<<b<<"\n";//然后把自己移动到目标杆b
       ha2(n-1,c,b,a);//最后再把前n-1个盘子通过辅助的杆a辅助移动到目标杆b
    }
    int main(){
       int n; char a, b, c;
       cin>>n>>a>>b>>c;
       ha2(n,a,b,c);
       return 0;
    }
    
  9. 放苹果 openjudge666

    //已经很水啦,貌似递推做过呢
    #include<iostream>
    using namespace std;
    int f(int m, int n){
       if(m==0 || n==1)return 1;
       return n>m?f(m,m):f(m,n-1)+f(m-n,n);
    }
    int main(){
       int T;  cin>>T;
       while(T--){
           int m, n;  cin>>m>>n;
           cout<<f(m,n)<<"\n";
       }
       return 0;
    }
    
  10. 求最大公约数问题 openjudge7592

    #include<iostream>
    using namespace std;
    typedef long long LL;
    LL gcd(LL a, LL b){
      return !b?a:gcd(b,a%b);
    }
    int main(){
      LL a, b;  cin>>a>>b;
      cout<<gcd(a,b)<<"\n";
      return 0;
    }
    
  11. 2的幂次方表示 openjudge8758

    //直接模拟就好啦
    #include<iostream>
    using namespace std;
    void dfs(int dep, int n){
        //if(n<=2){ cout<<n; return; }
        int flag = 0;
        for(int i = dep; i >= 0; i--){
            if(n&(1<<i)){
                if(flag)cout<<"+";
                if(i == 1)cout<<2;
                else if(i==0||i==2)cout<<"2("<<i<<")";//等价于边界条件
                else{
                    cout<<"2(";
                    dfs(dep,i);
                    cout<<")";
                }
                flag = 1;
            }
        }
    }
    int main(){
        int n;  cin>>n;  dfs(30,n);
        return 0;
    }
    
  12. 分数求和 openjudge12

    //gcd&lcm
    #include<iostream>
    using namespace std;
    int gcd(int a, int b){
        return !b?a:gcd(b,a%b);
    }
    int lcm(int a, int b){
        return a/gcd(a,b)*b;
    }
    int main(){
        int a=0, b=1;
        int T;  cin>>T;
        while(T--){
            int c, d; cin>>c; cin.get(); cin>>d;
            int t = lcm(b,d);
            a = a*(t/b)+c*(t/d);  b = t;
            while((t=gcd(a,b))!=1){
                a/=t; b/=t;
            }
        }
        if(b==1||a==0)cout<<a<<"\n";
        else cout<<a<<"/"<<b<<"\n";
        return 0;
    }
    
  13. 因子分解 openjudge22

    #include<iostream>
    using namespace std;
    int main(){
        int n, flag=0;  cin>>n;
        for(int i = 2; i <= n; i++){
            int cnt = 0;
            while(n%i==0){
                n /= i;  cnt++;
            }
            if(cnt){
                if(flag)cout<<"*";
                if(cnt==1)cout<<i;
                else cout<<i<<"^"<<cnt;
                flag = 1;
            }
        }
        return 0;
    }
    
  14. 判断元素是否存在 openjudge41

    //感觉有点绕,拿set水了
    #include<iostream>
    #include<set>
    using namespace std;
    set<int>s;
    int main(){
        int k, x, t;  cin>>k; cin.get(); cin>>x;
        s.insert(k); t = k; int cnt = 0;
        for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
            s.insert(2*(*it)+1); s.insert(3*(*it)+1);
            if(*(--s.end())>x)cnt++;
            if(cnt>1000)break;//强行搞事情
        }
        if(s.count(x))cout<<"YES\n";else cout<<"NO\n";
        return 0;
    }
    
    //开个玩笑的,不过这也算递归?
    #include<iostream>
    using namespace std;
    const int maxn = 300010;
    int a[maxn];
    void enlarge(int x){
        if(x<maxn){
            a[x] = 1;
            enlarge(2*x+1);
            enlarge(3*x+1);
        }else return ;
    }
    int main(){
        int k, x;  cin>>k; cin.get(); cin>>x;
        enlarge(k);
        if(a[x])cout<<"YES\n";else cout<<"NO\n";
        return 0;
    }
    

0 条评论

目前还没有评论...