蓝桥杯—递归

我不是女神ヾ 2022-06-18 05:44 278阅读 0赞

2013第四届第3题

题目标题: 第39级台阶  
  
小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!  
  
站在台阶前，他突然又想着一个问题：  
  
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？

#include<iostream>
    using namespace std;
    int count=0;
    void fun(int stair,int step)
    {
        //stair用于表示剩余的楼梯的层数，当等于0时停止递归
        //step是走过的步数，用来判断是否是偶数，是否符合要求
        if(stair<0)return;
        if(stair==0)      //39节楼梯全部走完
        {
            if(step%2 == 0)
                count++;
            return;
        }
        fun(stair-1,step+1);   //这一步走了一个台阶
        fun(stair-2,step+1);   //这一步走了两个台阶
    }
    int main()
    {
        fun(39,0);
        cout<<count<<endl;
        return 0;
    }

运行解果：  
![Center][]

分析：  
![Center 1][]

2014第5届第3题

标题：李白打酒  
  
话说大诗人李白，一生好饮。幸好他从不开车。  
  
一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：  
  
无事街上走，提壶去打酒。  
逢店加一倍，遇花喝一斗。  
  
这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。  
  
请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。

#include<iostream>
    using namespace std;
    int count=0;
    void dfs(int x,int y,int z) //x:店  y:花  z:酒
    {
        if(x>5||y>9)     //y限制为9，是因为要判断，最后是否遇到花
            return;
        if(x==5&&y==9)  
        {
            if(z==1) //判断最后遇到花
            {
                count++;
                return;
            }
            else
                return;
        }
        dfs(x+1,y,z*2);   //遇到店
        dfs(x,y+1,z-1);   //遇到花
    }
    int main()
    {
        dfs(0,0,2);
        cout<<count<<endl;
        return 0;
    }

运行结果：

![Center 2][]

2014年第5届第2题

标题：切面条  
  
一根高筋拉面，中间切一刀，可以得到2根面条。  
  
如果先对折1次，中间切一刀，可以得到3根面条。  
  
如果连续对折2次，中间切一刀，可以得到5根面条。  
  
那么，连续对折10次，中间切一刀，会得到多少面条呢？  
  
答案是个整数，请通过浏览器提交答案。不要填写任何多余的内容。

思路：  
由于对折次数仅为10，数据规模并不大，可以通过手算简单的完成。  
对折0次，得到2根；  
对折1次，得到2 \* 2 - 1 = 3  
对折2次，得到3 \* 2 - 1 = 5  
对折3次，得到5 \* 2 - 1 = 9  
对折4次，得到9 \* 2 - 1 = 17  
对折5次，得到17 \* 2 - 1 = 33  
对折6次，得到33 \* 2 - 1 = 65  
对折7次，得到65 \* 2 - 1 = 129  
对折8次，得到129 \* 2 - 1 = 257  
对折9次，得到257 \* 2 - 1 = 513  
对折10次，得到513 \* 2 - 1 = 1025

#include <iostream>
    using namespace std;
    int f(int nn)
    {
        if(nn==0)
            return 2;
        return f(nn-1)*2-1;
    }
    int main()
    {
        int n,b;
        cin>>n;
        b=f(n);
        cout<<b<<endl;
        return 0;
    }

运行结果：

![Center 3][]

## 球赛    ##

一场球赛开始前，售票工作在紧张进行中。  
每张球票为50元，有m+n个人在排队等待买票，其中有m个人手持50元的钞票，另外n个人手持100元的钞票。  
求出这m+n个人排队购票，使售票处不至于找不开钱的局面的不同排队种数。  
（约定：开始售票处没有零钱，拿同样面值钞票的人对换位置为同一种排队。）

思路：

![Center 4][]

实现：

#include <iostream>
    #include <stdio.h>
    using namespace std;
    
    int f(int m,int n)
    {
        if(n==0)
            return 1;
        else if(m<n)
            return 0;
        return f(m,n-1)+f(m-1,n);
    }
    int main()
    {
        int m,n;
        printf(" input m,n: ");
        scanf("%d,%d",&m,&n);
        printf("  f(%d,%d)=%ld.\n",m,n,f(m,n));
        return 0;
    }

运行结果：  
![Center 5][]

// 购票排队,递推实现
    #include<stdio.h>
    int main()
    {
        int m,n,i,j;
        long f[100][100];
        printf(" input m,n: ");
        scanf("%d,%d",&m,&n);
        // 确定初始条件
        for(j=1; j<=m; j++)
            f[j][0]=1;
        for(j=0; j<=m; j++)
            for(i=j+1; i<=n; i++)
                f[j][i]=0;
    
        for(i=1; i<=n; i++)
            for(j=i; j<=m; j++)
                f[j][i]=f[j-1][i]+f[j][i-1];   //  实施递推
        printf("  f(%d,%d)=%ld.\n",m,n,f[m][n]);
        return 0;
    }

运行结果：  
![Center 6][]

[Center]: /images/20220618/e68b606dcbc64305b44fd918b2f2f199.png
[Center 1]: /images/20220618/354551a5046d4025b386effb0bf1942c.png
[Center 2]: /images/20220618/4a055a03fa85432781e6a4dab315be3b.png
[Center 3]: /images/20220618/52a9cf5752bb4aaa9629447415cc0c37.png
[Center 4]: /images/20220618/849311e360a74f2d8a992383f7acc439.png
[Center 5]: /images/20220618/7adffb3f07d14eb788edf991b63e7669.png
[Center 6]: /images/20220618/e4961be8ec53483d91995922f2f2b2be.png