[第一章]递归与递推-阿里云开发者社区

题目一描述

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 n

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 1个空格隔开。对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1≤n≤15

输入样例：

输出样例：

2 3

1 3

1 2

1 2 3

算法原理

将每一次的递归画出来：

代码实现

#include <iostream>
using namespace std;
const int N=20;
int n;
bool vis[N]; //判断选还是不选
void DFS(int u) //第几层就是筛选第几个数字
{
    if(u>n) //不可以有等号，如果有等号会少一层递归，即最后一层无法递归 
    {
        for(int i=1;i<=n;i++)//从1到n选择
        if(vis[i])  //把选择的数打印出来
            cout<<i<<" ";
        cout<<endl;
        return ;
    }
    else 
    {
        vis[u]=true;//选这个数字
        DFS(u+1);
        vis[u]=false;//不选这个数字
        DFS(u+1);
    }
}
int main() 
{
    cin>>n;
    DFS(1);  //从1开始选择，到n结束，所以不能从0开始；
    return 0;
}

还可以参考下面这个代码：

#include<bits/stdc++.h>
using namespace std;
int n;
//用二进制状态压缩,也就是用二进制上的位来记录数有没有被用过。
// u是当前枚举到的数，state是二进制数记录哪些数被选
void dfs(int u ,int state)
{
    if( u == n)
    {
        for(int i = 0; i< n; i++)
            //判断第i位是不是1，如果是1就代表被选，输出
            if(state >> i & 1) 
                //第几位就代表输出几，只不过不是从0开始，而是从1开始
                cout << i + 1 << " ";
        cout << endl;
        return;
    }
    // 不用这个数，第u位不动
    dfs(u + 1, state); 
    // 用这个数，把第u位变成1
    // 运算优先级： 左移高于位运算|
    dfs(u + 1, state | 1 << u);  
}
int main(){
    cin >> n;
    /*
    回顾一下dfs参数的含义：
        - u是当前枚举到的数，
        -state是二进制数记录哪些数被选
    则 dfs(0, 0)表示：当前枚举到0，没有数被选
    */ 
    dfs(0, 0);
}

题目二解析

从 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

算法原理

其实只需要把例1的代码稍加修改就可以了。再增加两个情况，一种是动态数组所选择的数已经超过了m个，或者剩余的数凑不够m个，排除这两种情况就是我们所要的答案了。

代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> num;
void dfs(int k)
{
    //如题解所述
    if(num.size() > m || num.size() + (n - k + 1) < m)
        return;
    //到达枚举边界，输出结果并结束
    if(k == n + 1)
    {
        for(int i = 0;i < num.size();++i)
            cout << num[i] << " ";
        cout << endl;
        return;
    }
    //选择这个数
    num.push_back(k);
    dfs(k+1);
    //回溯
    num.pop_back();
    //不选择这个数
    dfs(k+1);
}
int main(void)
{
    cin >> n >> m;
    dfs(1);
    return 0;
}

题目三解析

把 1∼n这 n个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式

一个整数 n

输出格式

按照从小到大的顺序输出所有方案，每行 1 个。

首先，同一行相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围

1≤n≤9

输入样例：

输出样例：

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

算法原理

其实就是求无重复元素的全排列，经典的dfs题。

dfs 最重要的是搜索顺序。用什么顺序遍历所有方案。

对于全排列问题，以 n = 3 为例，可以这样进行搜索：

假设有 3 个空位，从前往后填数字，每次填一个位置，填的数字不能和前面一样。

最开始的时候，三个空位都是空的： __

首先填写第一个空位，第一个空位可以填 1，填写后为：1

填好第一个空位，填第二个空位，第二个空位可以填 2，填写后为：1 2 __

填好第二个空位，填第三个空位，第三个空位可以填 3，填写后为： 1 2 3

这时候，空位填完，无法继续填数，所以这是一种方案，输出。

然后往后退一步，退到了状态：1 2 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 3 ，没有其他数字可以填。

因此再往后退一步，退到了状态：1 。第二个空位上除了填过的 2，还可以填 3。第二个空位上填写 3，填写后为：1 3 __

填好第二个空位，填第三个空位，第三个空位可以填 2，填写后为： 1 3 2

这时候，空位填完，无法继续填数，所以这是一种方案，输出。

然后往后退一步，退到了状态：1 3 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 2，没有其他数字可以填。

因此再往后退一步，退到了状态：1 。第二个空位上除了填过的 2，3，没有其他数字可以填。

因此再往后退一步，退到了状态：。第一个空位上除了填过的 1，还可以填 2。第一个空位上填写 2，填写后为：2 __

填好第一个空位，填第二个空位，第二个空位可以填 1，填写后为：2 1 __

填好第二个空位，填第三个空位，第三个空位可以填 3，填写后为：2 1 3

这时候，空位填完，无法继续填数，所以这是一种方案，输出。

然后往后退一步，退到了状态：2 1 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 3，没有其他数字可以填。

因此再往后退一步，退到了状态：2 。第二个空位上除了填过的 1，还可以填 3。第二个空位上填写 3，填写后为：2 3 __

填好第二个空位，填第三个空位，第三个空位可以填 1，填写后为：2 3 1

这时候，空位填完，无法继续填数，所以这是一种方案，输出。

然后往后退一步，退到了状态：2 3 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 1，没有其他数字可以填。

因此再往后退一步，退到了状态：2 。第二个空位上除了填过的 1，3，没有其他数字可以填。

因此再往后退一步，退到了状态：。第一个空位上除了填过的 1，2，还可以填 3。第一个空位上填写 3，填写后为：3 __

填好第一个空位，填第二个空位，第二个空位可以填 1，填写后为：3 1 __

填好第二个空位，填第三个空位，第三个空位可以填 2，填写后为：3 1 2

这时候，空位填完，无法继续填数，所以这是一种方案，输出。

然后往后退一步，退到了状态：3 1 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 2，没有其他数字可以填。

因此再往后退一步，退到了状态：3 。第二个空位上除了填过的 1，还可以填 2。第二个空位上填写 2，填写后为：3 2 __

填好第二个空位，填第三个空位，第三个空位可以填 1，填写后为：3 2 1

这时候，空位填完，无法继续填数，所以这是一种方案，输出。

然后往后退一步，退到了状态：3 2 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 1，2，没有其他数字可以填。

因此再往后退一步，退到了状态：3 。第二个空位上除了填过的 1，2，没有其他数字可以填。

因此再往后退一步，退到了状态： __。第一个空位上除了填过的 1，2，3，没有其他数字可以填。

此时深度优先搜索结束，输出了所有的方案。

算法：

用 path 数组保存排列，当排列的长度为 n 时，是一种方案，输出。
用 state 数组表示数字是否用过。当 state[i] 为 1 时：i 已经被用过，state[i] 为 0 时，i 没有被用过。
dfs(i) 表示的含义是：在 path[i] 处填写数字，然后递归的在下一个位置填写数字。
回溯：第 i 个位置填写某个数字的所有情况都遍历后，第 i 个位置填写下一个数字。

代码实现

#include<iostream>
using namespace std;
const int N = 10;
int path[N];//保存序列
int state[N];//数字是否被用过
int n;
void dfs(int u)
{
    if(u > n)//数字填完了，输出
    {
        for(int i = 1; i <= n; i++)//输出方案
            cout << path[i] << " ";
        cout << endl;
    }
    for(int i = 1; i <= n; i++)//空位上可以选择的数字为:1 ~ n
    {
        if(!state[i])//如果数字 i 没有被用过
        {
            path[u] = i;//放入空位
            state[i] = 1;//数字被用，修改状态
            dfs(u + 1);//填下一个位
            state[i] = 0;//回溯，取出 i
        }
    }
}
int main()
{
    cin >> n;
    dfs(1);
    return 0;
}

题目四解析

你玩过“拉灯”游戏吗？

25盏灯排成一个 5×5的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。

下面这种状态

10111

01101

10111

10000

11011

在改变了最左上角的灯的状态后将变成：

01111

11101

10111

10000

11011

再改变它正中间的灯后状态将变成：

01111

11001

10100

11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6步以内使所有的灯都变亮。

输入格式

第一行输入正整数 n，代表数据中共有 n个待解决的游戏初始状态。

以下若干行数据分为 n组，每组数据有 5行，每行 5个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式

一共输出 n行数据，每行有一个小于等于 6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 6步以内无法使所有灯变亮则输出 −1。

数据范围

0<n≤500

输入样例：

00111

01011

10001

11010

11100

11101

11110

11111

01111

11111

输出样例：

-1

算法原理：

大致解题思路：这道题目首先看一眼，我们就可以知道必然与位运算有着密切的关系，因为出现了0和1，这是一个重要的发现，接着我们在仔细分析题意，我们知道如果纯暴力枚举的话，必然是会超时的，那么如何优化呢？因此我们需要从题目中找出非常有用的性质来优化，这是一个大致的思路方向

每一个位置顶多只会操作一次。因为如果操作两次的话，相当于不操作，必然是不满足最优解。

在一套方案中，操作的顺序无关紧要，这一个略加思索便可得知最重要的性质，如果我们确定了第I行的操作方案的话，那么后面的行数都可以依此递推，下面给出一个详细的解答。

11011

10110

01111

11111

比如说这个例子，如果我们确定了第1行，那么第二行所有的0(坐标：a[i][j])都只能是第三行a[i+1][j]来修改了，因为如果你第二行修改的话，那么第一行将会打乱，下面每一行依此类推。

所以说，我们只需要得出第一行的顺序，后面的顺序都可以顺序推出

代码实现

解法一：

#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,k,a[7][7],ans1=1e6,b[7][7];//7,7是因为怕在最后一排溢出
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        getchar();
        for (i=1;i<=5;i++)
        {
            for (j=1;j<=5;j++)
            {
                char ch=getchar();
                b[i][j]=ch-'0';
            }
            getchar();
        }
        for (i=0;i<=(1<<5);i++)
        {
            for (j=1;j<=5;j++)
            {
                for (k=1;k<=5;k++)
                    a[j][k]=b[j][k];
            }
            int ans=0;
            for (j=1;j<=5;j++)
                if (i>>(j-1) & 1)
                {
                    ans++;
                    a[1][j-1]^=1;
                    a[1][j+1]^=1;
                    a[1][j]^=1;
                    a[2][j]^=1;
                }
            for (j=1;j<=4;j++)//切记是1~4，而不是2~5，因为我们是控制i+1行，而不是控制第i行
                for (k=5;k>=1;k--)
                    if (!a[j][k])
                    {
                        ans++;
                        a[j][k]^=1;//上面
                        a[j+2][k]^=1;//下面
                        a[j+1][k]^=1;//本身
                        a[j+1][k+1]^=1;//右面
                        a[j+1][k-1]^=1;//左面
                    }
            //cout<<ans<<endl;
            bool ok=true;
            for (j=1;j<=5;j++)
                for (k=1;k<=5;k++)
                    if (!a[j][k])
                        ok=false;
            if (ok)
                ans1=min(ans1,ans);//,cout<<ans<<endl;
        }
        if (ans1>6)
            cout<<-1;
        else
            cout<<ans1;
        ans1=1e7;
        puts("");
    }
    return 0;
}

解法二：

#include <bits/stdc++.h>
using namespace std;
int a[7][7],b[7][7],n,answer;
int init()
{
    getchar();
    for (int i=1;i<=5;i++)
    {
        for (int j=1;j<=5;j++)
        {
            char ch=getchar();
            a[i][j]=ch-'0';
        }
        getchar();
    }
}
int handle(int x,int y)
{
    b[x][y]^=1;
    b[x-1][y]^=1;
    b[x][y+1]^=1;
    b[x][y-1]^=1;
    b[x+1][y]^=1;
}
bool judge(void)
{
    for (int i=1;i<=5;i++)
        for (int j=1;j<=5;j++)
            if(!b[i][j])
                return false;
    return true;
}
int work(void)
{
    answer=1e7;
    for (int i=1;i<=(1<<5);i++)
    {
        int ans=0;
        memcpy(b,a,sizeof(a));
        for (int j=1;j<=5;j++) 
            if (i>>(j-1) & 1)
            {
                handle(1,j);
                ans++;
            }
        for (int j=1;j<=4;j++)
            for (int k=1;k<=5;k++)
                if (!b[j][k])
                {
                    ans++;
                    handle(j+1,k);
                }
        if (judge())
            answer=min(ans,answer);
    }
    return answer;
}
int main()
{
    cin>>n;
    while(n--)
    {
        init();
        if (work()<=6)
            cout<<answer;
        else
            cout<<"-1";
        puts("");    
    }
    return 0;
}

解法三：

// 思路：我们枚举第一行的点击方法，共32种，完成第一行的点击后，固定第一行，
// 从第一行开始递推，若达到第n行不全为0，说明这种点击方式不合法。
// 在所有合法的点击方式中取点击次数最少的就是答案。
// 对第一行的32次枚举涵盖了该问题的整个状态空间，因此该做法是正确的
// 
// 时间复杂度：32*20*5*500 = 一百六十万
// 对第一行操作有32种可能 * 对前四行有20种操作可能 * 每一次操作都要改变5个灯的状态 * 最多读入的时候可能有500次light矩阵
//
// 最关键的两个性质
// 每一个位置最多只会被点击一次
// 如果固定了第一行，那么满足题意的点击方案最多只有一种
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
char g[N][N];
void turn(int x,int y)
{
    int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};
    for(int i=0;i<5;i++)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>=0 && xx<5 && yy>=0 && yy<5)
        {
            g[xx][yy]^=1;
        }
    }
}
int work()
{
    int ans = 0x3f3f3f3f;
    for(int k=0;k< 1<<5;k++)
    {
        int res=0;
        char temp[N][N];
        memcpy(temp,g,sizeof g);
        //第一行按灯一共有32种可能，对于每一种可能，我们操作选择后，开始固定，
        //此时第一行不一定是全亮的状态，第一行只是32种操作可能的一种
        //然后遍历前四行，如果g[i][j] == '0', 那么turn(i+1, j)
        //这一步是枚举第一行的点击方法，只要第一行固定了，那么满足题意的点击方法就只有一种了。
        //假如第一行是00111, k从0到31进行枚举，如果k = 00001，
        //那么代表g矩阵中第一行的第一个灯要点击一下，
        //第一行变为11111。
        //k不断变大(0变到31)
        //假如第一行是00111, k从0到31进行枚举，如果k = 10001，
        //那么代表g矩阵中第一行的第一个灯和最后一个灯要点击一下，
        //第一行变为11100。
        //之后固定这一行，改变下面的灯看是否能全变亮。
        //这也就是为什么我们copy light, 每一次对k的枚举都会改变light。
        for(int j=0;j<5;j++)
        {
            if(k>>j & 1)
            {
                res++;
                turn(0,j);
            }
        }
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<5;j++)
            {
                if(g[i][j]=='0')
                {
                    res++;
                    turn(i+1,j);
                }
            }
        }
        bool flag=true;
        for(int i=0;i<5;i++)
        {
            if(g[4][i]!='1')
            {
                flag=false;
                break;
            }
        }
        if(flag) ans = min(ans,res);
        memcpy(g,temp,sizeof g);
    }
    if(ans>6) return -1;
    else return ans;
}
int main()
{
    int n; cin>>n;
    while(n--)
    {
        for(int i=0;i<5;i++) cin>>g[i];
        cout<< work() <<endl;   
    }   
    return 0;
}

题目五解析

以下数列 0 1 1 2 3 5 8 13 21 … 被称为斐波纳契数列。

这个数列从第 3项开始，每一项都等于前两项之和。

输入一个整数 N，请你输出这个序列的前 N项。

输入格式

一个整数 N。

输出格式

在一行中输出斐波那契数列的前 N 项，数字之间用空格隔开。

数据范围

0<N<46

输入样例：

输出样例：

0 1 1 2 3

算法原理：

简单的递归问题

代码实现

#include<bits/stdc++.h>//万能头文件
using namespace std;
int main()
{
    int a[10010],n;
    cin >> n;
    a[0]=0;//给第一个数字定值为零
    a[1]=1;//同上(因为第一和第二个数不能参与累加)
    if(n>=1)//简单判断
    cout << 0<<" ";
    if(n>=2)
    cout << 1<<" ";
    for (int i = 2; i <n; i ++ )//要从第三个数开始，所以i=2
    {
        a[i]=a[i-1]+a[i-2];//累加
        cout << a[i]<<" ";//空格很有必要
    }
    return 0;//可有可无
}

题目六解析

算法原理：

解题思路：

暴力枚举出9个数的全排列，然后用一个长度为9的数组保存全排列的结果
从全排列的结果中用两重循环暴力分解出三段，形如下图，通过 i,j将一个排列分割，每段代表一个数
验证枚举出来的三个数是否满足题干条件，若满足则计数

代码实现

#include <iostream>
using namespace std;
const int N = 10;
int target;  // 题目给出的目标数
int num[N];  // 保存全排列的结果
bool used[N];  // 生成全排列过程中标记是否使用过
int cnt;  // 计数，最后输出的结果
// 计算num数组中一段的数是多少
int calc(int l, int r) 
{
  int res = 0;
  for (int i = l; i <= r; i++) 
  {
    res = res * 10 + num[i];
  }
  return res;
}
// 生成全排列
// 当全排列生成后进行分段
void dfs(int u) 
{
  // 用两层循环分成三段
  if (u == 9) 
  {
    for (int i = 0; i < 7; i++) 
    {
      for (int j = i + 1; j < 8; j++) 
      {
        int a = calc(0, i);
        int b = calc(i + 1, j);
        int c = calc(j + 1, 8);
        // 注意判断条件，因为C++中除法是整除，所以要转化为加减乘来计算
        if (a * c + b == c * target) 
        {
          cnt++;
        }
      }
    }
    return;
  }
  // 搜索模板
  for (int i = 1; i <= 9; i++) 
  {
    if (!used[i]) 
    {
      used[i] = true; // 标记使用
      num[u] = i;
      dfs(u + 1);
      used[i] = false; // 还原现场
    }
  }
}
int main() {
  scanf("%d", &target);
  dfs(0);
  printf("%d\n", cnt);
  return 0;
}

下面再给出一个直接调用 next_permutation() 函数的做法，可以代替手写暴搜来枚举全排列，蓝桥杯是可以使用这个函数的。

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int target;
int num[N];
int calc(int l, int r) 
{
  int res = 0;
  for (int i = l; i <= r; i++) 
  {
    res = res * 10 + num[i];
  }
  return res;
}
int main() 
{
  cin >> target;
  for (int i = 0; i < 9; i++) 
  {
    num[i] = i + 1;
  }
  int res = 0;
  do 
  {
    for (int i = 0; i < 9; i++) 
    {
      for (int j = i + 1; j < 9; j++) 
      {
        int a = calc(0, i);
        int b = calc(i + 1, j);
        int c = calc(j + 1, 8);
        if (a == 0 || b == 0 || c == 0) 
        {
          continue;
        }
        if (a * c + b == c * target) 
        {
          ++res;
        }
      }
    }
    // 调用函数生成全排列
  } while (next_permutation(num, num + 9));
  cout << res << '\n';
  return 0;
}

题目七解析

算法原理：

如果通过每次翻转两枚相邻硬币，能从状态一变为状态二，则两个状态之间必定有偶数个不同状态的硬币。

模拟法：

从最左侧开始遍历，如果该位置硬币状态与目标不同，就翻动该位置和该位置后面的两枚硬币。

因为题目说了有解，所以遍历到倒数第二枚的时候，所有硬币状态就与目标相同了。

这个方法也有点贪心的思路，每次追求当前位置状态与目标状态一致。我还是喜欢称它为模拟法。

代码实现

//cpp
#include <iostream>
#include <string>
using namespace std;
const int N = 110;//用不到，看范围就直接写了
int main()
{
    string s1, s2;//s1:初始状态，s2:目标状态
    int cnt = 0;//记录翻转次数
    cin >> s1 >> s2;
    for (int i = 0; i < s1.size() - 1; i++)
    {
        if (s1[i] != s2[i])//第 i 个位置上状态不同，就翻转该位置和后一个位置硬币
        {
            cnt++;//翻转一次硬币
            if (s1[i] == '*') s1[i] = 'o';//翻转 i 位置上的硬币
            else s1[i] = '*';
            if (s1[i+1] == 'o') s1[i+1] = '*';//翻转 i + 1 位置上的硬币
            else s1[i+1] = 'o';
        }
    }
    cout << cnt;//输出翻转次数
}

[第一章]递归与递推

题目一描述

算法原理

代码实现

题目二解析

算法原理

代码实现：

题目三解析

算法原理

代码实现

题目四解析

算法原理：

代码实现

题目五解析

算法原理：

代码实现

题目六解析

算法原理：

代码实现

题目七解析

算法原理：

代码实现

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

[第一章]递归与递推

题目一描述

算法原理

代码实现

题目二解析

算法原理

代码实现：

题目三解析

算法原理

代码实现

题目四解析

算法原理：

代码实现

题目五解析

算法原理：

代码实现

题目六解析

算法原理：

代码实现

题目七解析

算法原理：

代码实现

热门文章

最新文章

相关电子书