[蓝桥杯] 递归与递推习题训练

拼搏现实的明天。 2023-09-26 18:07 221阅读 0赞

![d8651a493247401da154038100ee6a5e.gif][]

> **文章目录**
> 
> 一、递归实现指数型枚举
> 
> 1、1 题目描述
> 
> 1、2 题解关键思路与解答
> 
> 二、递归实现排列型枚举 
> 
> 2、1 题目描述
> 
> 2、2 题解关键思路与解答
> 
> 三、递归实现组合型枚举
> 
> 3、1 题目描述
> 
> 3、2 题解关键思路与解答
> 
> 四、带分数
> 
> 4、1 题目描述
> 
> 4、2 题解关键思路与解答
> 
> 五、费解的开关
> 
> 5、1 题目描述
> 
> 5、2 题解关键思路与解答
> 
>  六、总结
> 
> --------------------
> 
> ## 标题：蓝桥杯——递归与递推习题训练 ##
> 
> ## **作者：@Ggggggtm** ##
> 
> ## 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景 ##
> 
> ![b32c0fab104b42f98cf30eca296850dc.png][]

> 蓝桥杯比赛只有四十天左右啦，最近会按照模块更新一些有关蓝桥杯算法题。学习算法不仅仅是为了参见比赛，更是以后找工作的一个敲门砖。废话不多说，我们直接看题。

## 一、递归实现指数型枚举 ##

### 1、1 题目描述 ###

> **题目来源：**《算法竞赛进阶指南》
> 
> **题目难度：**简单
> 
> **题目描述：**
> 
> 从 1∼n这 n个整数中随机选取任意多个，输出所有可能的选择方案。
> 
> **输入格式：**
> 
> 输入一个整数 n。
> 
> **输出格式：**
> 
> 每行输出一种方案。
> 
> 同一行内的数必须升序排列，相邻两个数用恰好 1个空格隔开。
> 
> 对于没有选任何数的方案，输出空行。
> 
> 本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
> 
> **数据范围：**
> 
> 1≤ n≤ 15
> 
> **输入样例：**
> 
>     3
> 
> **输出样例：**
> 
>     3
>     2
>     2 3
>     1
>     1 3
>     1 2
>     1 2 3

### 1、2 题解关键思路与解答 ###

> 由于上述题目是要求递归，我们可以通过开一个数组**纪录是否选择该数组（**0表示还没对该数字进行操作，1表示选择该数字，2表示不选择该数字）。这样通过递归，我们就可以很好的枚举出每一种情况。我们结合代码一起理解一下。

#include<iostream>
    using namespace std;
    
    const int N=16;
    
    int n;
    int state[N];
    void dfs(int a)
    {
        if(a>n)
        {
             for(int i=1;i<=n;i++)
             {
                 if(state[i]==1)
                    printf("%d ",i);
             }
             puts("");
             return;
        }
        
        state[a]=2;
        dfs(a+1);
        //恢复现场
        state[a]=0;
        
        state[a]=1;
        dfs(a+1);
        //恢复现场
        state[a]=0;
    }
    int main()
    {
        cin>>n;
        
        dfs(1);
        return 0;
    }

## 二、递归实现排列型枚举 ##

### 2、1 题目描述 ###

> **题目来源：**《算法竞赛进阶指南》
> 
> **题目难度：**简单
> 
> **题目描述：**
> 
> 把 1∼n这 n个整数排成一行后随机打乱顺序，输出所有可能的次序。
> 
> **输入格式：**
> 
> 一个整数 n。
> 
> **输出格式：**
> 
> 按照从小到大的顺序输出所有方案，每行 1 个。
> 
> 首先，同一行相邻两个数用一个空格隔开。
> 
> 其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
> 
> **数据范围：**
> 
> 1≤n≤9
> 
> **输入样例：**
> 
>     3
> 
> **输出样例：**
> 
>     1 2 3
>     1 3 2
>     2 1 3
>     2 3 1
>     3 1 2
>     3 2 1

### 2、2 题解关键思路与解答 ###

> 这个题的关键就在于是排列。通过递归枚举的方法实现排列，我们需要开两个数组：**一个数组是记录还数字是否被使用过**（0是未被使用，1是已经使用），**另一个数组记录所排序的数字**。题目中还要求了字典序，正常从小到大递归就已经是字典序较小的排在前面。我们直接看代码。

#include<iostream>
    using namespace std;
    
    const int N=10;
    
    int n;
    int state[N];
    int used[N];
    void dfs(int a)
    {
        if(a>n)
        {
            for(int i=1;i<=n;i++)
                printf("%d ",state[i]);
            puts("");
            return;
        }
        for(int i=1;i<=n;i++)
        {
            if(used[i]==0)
            {
                state[a]=i;
                used[i]=1;
                dfs(a+1);
                
                used[i]=0;
            }
        }
    }
    int main()
    {
        cin>>n;
        
        dfs(1);
        return 0;
    }

## 三、递归实现组合型枚举 ##

### 3、1 题目描述 ###

> **题目来源：**《算法竞赛进阶指南》
> 
> **题目难度：**简单
> 
> **题目描述：**
> 
> 从 1∼n 这 n个整数中随机选出 m个，输出所有可能的选择方案。
> 
> **输入格式：**
> 
> 两个整数 n,m,在同一行用空格隔开。
> 
> **输出格式：**
> 
> 按照从小到大的顺序输出所有方案，每行 1 个。
> 
> 首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
> 
> 其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 `1 3 5 7` 排在 `1 3 6 8` 前面）。
> 
> **数据范围:**
> 
> n>0,  
> 0≤m≤n,  
> n+(n−m)≤25
> 
> **输入样例：**
> 
>     5 3
> 
> **输出样例：**
> 
>     1 2 3 
>     1 2 4 
>     1 2 5 
>     1 3 4 
>     1 3 5 
>     1 4 5 
>     2 3 4 
>     2 3 5 
>     2 4 5 
>     3 4 5

### 3、2 题解关键思路与解答 ###

> 组合与排列十分相似，但又有些不同。组合特殊的是 1，2，3 与 2，1，3 与 3，2，1相同的，算是一种组合类型。题目中要求的同一行内的数升序排列。怎么定义升序呢？我们可以人为的选数字为升序。我们**可以把整体的升序看成局部的升序**，只要是满足后一个数比前一个数大即可。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    
    using namespace std;
    
    int n,m;
    
    const int N=26;
    
    int way[N];
    void def(int a,int start)
    {
        if(a-1+n-start+1<m)  //剪枝
            return;
        if(a==m+1)
        {
            for(int i=1;i<=m;i++)
            {
                printf("%d ",way[i]);
            }
            printf("\n");
            return;
        }
        for(int i=start;i<=n;i++)
        {
            way[a]=i;
            def(a+1,i+1);
        }
    }
    int main()
    {
        cin>>n>>m;
        
        def(1,1);
        return 0;
    }

## 四、带分数 ##

### 4、1 题目描述 ###

> **题目来源：**第四届蓝桥杯省赛C++B/C组
> 
> **题目难度：**中等
> 
> **题目描述：**
> 
> 100可以表示为带分数的形式：100=3+69258 / 714
> 
> 还可以表示为：100=82+3546 / 197
> 
> 注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。
> 
> 类似这样的带分数，100 有 11 种表示法。
> 
> **输入格式:**
> 
> 一个正整数。
> 
> **输出格式:**
> 
> 输出输入数字用数码 1∼9不重复不遗漏地组成带分数表示的全部种数。
> 
> **数据范围:**
> 
> 1≤N<106
> 
> **输入样例1：**
> 
>     100
> 
> **输出样例1：**
> 
>     11
> 
> **输入样例2：**
> 
>     105
> 
> **输出样例2：**
> 
>     6

### 4、2 题解关键思路与解答 ###

> 我们可以把带分数的形式看成一个公式：n = a + b / c 。也就是a、b和c 的数字 中1∼9 分别出现且只出现一次。那我们就可以想枚举a和c的情况，然后通过公式 b = c\*n-c\*a 计算出b的值。再把b的每一位拿出来看看时候符合题目所要求的情况。我们直接结合代码一起理解一下。

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    
    const int N=12;
    
    int n,ans;
    bool st[N],backup[N];
    
    bool check(int a,int c)
    {
        long long b=n*(long long)c-a*c;
        
        memcpy(backup,st,sizeof(st));
        while(b)
        {
            int x=b%10;
            b/=10;
            if(!x || backup[x])
                return false;
            backup[x]=true;
        }
        for(int i=1;i<=9;i++)
        {
            if(!backup[i])
                return false;
        }
        return true;
    }
    void dfs_c(int u,int a,int c)
    {
        if(u>9)
            return;
        if(check(a,c))
            ans++;
        for(int i=1;i<=9;i++)
        {
            if(!st[i])
            {
                st[i]=true;
                dfs_c(u+1,a,c*10+i);
                
                st[i]=false;
            }
        }
    }
    void dfs_a(int u,int a)
    {
        if(a>=n)
            return;
        if(a)
            dfs_c(u,a,0);
        for(int i=1;i<=9;i++)
        {
            if(!st[i])
            {
                st[i]=true;
                dfs_a(u+1,a*10+i);
                
                st[i]=false;
            }
        }
    }
    int main()
    {
        cin>>n;
        
        dfs_a(0,0);
        
        cout<<ans<<endl;
        return 0;
    }

## 五、费解的开关 ##

### 5、1 题目描述 ###

> **题目来源：**《算法竞赛进阶指南》
> 
> **题目难度：**中等
> 
> **题目描述：**
> 
> 你玩过“拉灯”游戏吗？
> 
> 25 盏灯排成一个 5×5 的方形。
> 
> 每一个灯都有一个开关，游戏者可以改变它的状态。
> 
> 每一步，游戏者可以改变某一个灯的状态。
> 
> 游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
> 
> 我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。
> 
> **下面这种状态：**
> 
>     10111
>     01101
>     10111
>     10000
>     11011
> 
> **在改变了最左上角的灯的状态后将变成：**
> 
>     01111
>     11101
>     10111
>     10000
>     11011
> 
> **再改变它正中间的灯后状态将变成：**
> 
>     01111
>     11001
>     11001
>     10100
>     11011
> 
> 给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。
> 
> **输入格式：**
> 
> 第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。
> 
> 以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。
> 
> 每组数据描述了一个游戏的初始状态。
> 
> 各组数据间用一个空行分隔。
> 
> **输出格式：**
> 
> 一共输出 n 行数据，每行有一个小于等于 66 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
> 
> 对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出 −1。
> 
> **数据范围：**
> 
> 0<n≤500
> 
> **输入样例：**
> 
>     3
>     00111
>     01011
>     10001
>     11010
>     11100
>     
>     11101
>     11101
>     11110
>     11111
>     11111
>     
>     01111
>     11111
>     11111
>     11111
>     11111
> 
> **输出样例：**
> 
>     3
>     2
>     -1

### 5、2 题解关键思路与解答 ###

> 由于每个灯是数字 1 表示一盏开着的灯，用数字 0 表示关着的灯，我们就一行一行就行看。一行有五个灯，我们把代表灯的状态的数字看作一个数的二进制位。也就是一行有32种情况。**整体的思路就是下一行影响上一行，我们需要做的是首先枚举第一行的32种情况，接着调整完前四行，最后看第五行是否为全亮即可**。我们直接看代码：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    
    using namespace std;
    
    const int N=6;
    char g[N][N],backup[N][N];
    int dx[5]={-1,0,1,0,0},dy[5]={0,0,0,-1,1};
    
    void turn(int x,int y)
    {
        for(int i=0;i<5;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a<0 || a>4 || b<0 || b>4)
                continue;
            g[a][b]^=1;
        }
    }
    int main()
    {
        int n;
        cin>>n;
        while(n--)
        {
            int res=10;
            for(int i=0;i<5;i++)
                cin>>g[i];
            for(int op=0;op<32;op++)
            {
                int step=0;
                memcpy(backup,g,sizeof(g));
                for(int i=0;i<5;i++)
                {
                    if(op>>i&1)
                    {
                        step++;
                        turn(0,i);
                    }
                }
                for(int i=0;i<4;i++)
                {
                    for(int j=0;j<5;j++)
                    {
                        if(g[i][j]=='0')
                        {
                            step++;
                            turn(i+1,j);
                        }
                    }
                }
                
                bool back=false;
                for(int i=0;i<5;i++)
                {
                    if(g[4][i]=='0')
                    {
                        back=true;
                        break;
                    }
                }
                if(!back)
                    res=min(res,step);
                memcpy(g,backup,sizeof(g));
            }
            if(res>6)
                res=-1;
            cout<<res<<endl;
        }
        return 0;
    }

## 六、总结 ##

> 通过上面的习题练习，我们发现用递归去枚举也很简单。同时，我们也要掌握上面的递归枚举的思路和方法。在很多情况下，我们可以多开数组来进行记录或者操作，会给我们带来很大的便利。
> 
> 递归与递推的练习就到这里，希望以上内容对你有所帮助。

[d8651a493247401da154038100ee6a5e.gif]: https://img-blog.csdnimg.cn/d8651a493247401da154038100ee6a5e.gif
[b32c0fab104b42f98cf30eca296850dc.png]: https://img-blog.csdnimg.cn/b32c0fab104b42f98cf30eca296850dc.png