寒假刷题-递归与递推

寒假刷题

92. 递归实现指数型枚举

解法1递归

使用递归对每一个坑位进行选择，每个坑位有两种选择，填或者不填，使用st数组来记录每个坑位的状态，u来记录已经有多少坑位有了选择。

每个坑位有2钟选择，n个坑位的复杂度就是2的n次方。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 16;
int n;
int st[N];
void dfs(int u){
    if(u>n)
    {
        for(int i = 1;i<=n;i++)
        {
            if(st[i]==1)printf("%d ",i);
        }
        printf("\n");
        return;
    }
    st[u] = 1;
    dfs(u+1);
    st[u]=0;
    dfs(u+1);
}
int main(){
    scanf("%d",&n);
    dfs(1);
    return 0;
}

坑位的下标和这个坑位的数字是存在对应关系的，所以可以用一个u来控制递归的出口。我们只关心u位置是否有数字。
st[u] = 1;
dfs(u+1);
这两句相当于是将这个位置画对勾，然后跳到下一个位置进行选择
st[u]=0;
dfs(u+1);
这两句就是这个位置不填数进入下一轮，顺便回到dfs之前的状态。(这题无所谓)

解法2二进制压缩

1-n的所有整数排列的方案可以看作一个二进制序列，例如1-3的排列中，1 3就对应二进制101。有数字用1表示，没有数字用0表示。
1-n共有2的n次方钟方案。将所有方案数枚举，然后判断位数是否是1。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int main()
{
    scanf("%d",&n);
    for(int i = 0;i < 1<<n;i ++)
    {
        for(int j = 0;j < n;j ++)
        {
            if(i >> j & 1)printf("%d ",j + 1);
        }
        printf("\n");
    }
    return 0;
}

94. 递归实现排列型枚举

这题就是一个全排列问题，和上一题的区别是很明显的。上一个的每个坑位的数字是固定的，可能有或没有，这个题的每个坑位的数是不固定的，且必须有。这个题需要使用st记录是否使用过。这个st和上一个题的st代表的意义不一样。

使用循环来进行dfs。循环从1开始，到n结束。通过st[i]可以知道数字i是否被使用过。如果没被使用过就使用i，然后进入下一层搜索。使用后一定要恢复现场。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10;
int m,st[N],ans[N];
int n;
void dfs(int x)
{
    if(x > n) 
    {
       for(int i = 1;i <= n;i ++)
       {
           printf("%d ",ans[i]);
       }
       printf("\n");
    }
 
    for(int i = 1;i <=n;i ++)
    {
        if(!st[i])
        {
            st[i] = 1;
            ans[x] = i;
            dfs(x+1);
            st[i] = 0;
        }
    }
}
int main()
{
    scanf("%d",&n);
    dfs(1);
    return 0;
}

717. 简单斐波那契

使用递推来进行求解，通过观察可以发现这个数列的第n项只与n-1和n-2项有直接关系，所以使用三个变量a b fn，依次向后轮转。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
    int n,fn;
    scanf("%d",&n);
    int a = 0,b = 1;
    for(int i = 1;i <= n;i ++)
    {
        cout<<a<<" ";
        fn = a+b;
        a=b,b=fn;
    }
}

95. 费解的开关

样例

改变右上角的开关

两步即可让所有的灯变亮。

观察题意可以发现能影响灯本身的除了灯自己还有灯上下左右的灯，可以枚举第一行灯的32种按法，记得备份原数组，然后从第一行按到第四行，第i行可以通过第i+1行的灯来控制，遍历完第四行后，看看第五行还有没有灭的灯，如果有的话，那这个方案就是不可行的。因为没有第六行来控制第五行。如果第五行全亮，那这个就是可以调，判断一下和ans哪个更小。

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

93. 递归实现组合型枚举

这题与全排列的区别就是字典序，只需要在判断是否使用过的时候加上一个判断，条件是当前的i是否大于ans数组的的最后一个元素，大于往里面添加，小于直接就跳过即可。ans数组初始化时要将元素变为-1,否则开头将无法添加。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 26;
int n,m;
int ans[N] = {-1},st[N]={0};
void dfs(int c,int m){
    if(c > m)
    {
        for(int i = 1;i <= m; i ++)
        {
            cout << ans[i] << " ";
        }
        cout<<endl;
        return;
    }
    for(int i = c ;i <= n; i ++)
    {
        if(!st[i]&&i > ans[c-1])
        {
          
          ans[c] = i;
          st[i] = 1;
          dfs(c + 1,m);
          st[i] = 0;
        }
       
    }
}
int main(){
    scanf("%d%d",&n,&m);
    dfs(1,m);
    return 0;
}

1209. 带分数

题意是
$$n=a+b/c$$
等式两边同时×c
$$c?n=c?a+b$$
通过dfs枚举a和c，然后计算出b，然后遍历st数组看看是否b的每一位都没有被用到。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 30;
int st[N],backup[N];
int n,ans,test;
bool check(int a,int c)
{
    long long b = (long long) n * c -a * c;
    
    if(!a || !b || !c)return false;
   
    memcpy(backup,st,sizeof st);

    while(b)
    {
        int ge = b % 10;
        if(ge == 0 || backup[ge])return false;
        backup[ge] = 1;
        b /= 10;
    }
       
    for(int i = 1;i <= 9;i ++)
    {
        if(backup[i] == 0) return false;
    }
    return true;
}
void dfs_c(int a,int c)
{
    
    if(check(a,c))ans ++;
    for(int i = 1; i <= 9; i ++)
    {
        if(st[i] == 0)
        {
            st[i] = 1;
            dfs_c(a,c*10 + i);
            st[i] = 0;
        }
    }
}
void dfs_a(int a)
{
    
    if(a > n)return;
    if(a)dfs_c(a,0);
    for(int i = 1;i <= 9; i ++)
    {
        if(st[i] == 0)
        {
            st[i] = 1;
            dfs_a(a*10 + i);
            st[i] = 0;
        }
    }
}
int main()
{
    scanf("%d",&n);
    dfs_a(0);
    cout << ans << endl;
    return 0;
}

116. 飞行员兄弟

和费解的开关类似，只不过这个题的数量比较下，所以枚举所有行的全部可能，共65536种，对每一种方案进行操作，记录最少的方案数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define x first
#define y second
using namespace std;

typedef pair<int,int> PII;
const int N = 5;
char st[N][N],backup[N][N];
vector <PII> ans;
int get(int x,int y)
{
    return x*4 + y;
}
void turn(int x,int y)
{
    if(st[x][y]=='+')st[x][y]='-';
    else st[x][y]='+';
}
void turnall(int x,int y)
{
    for(int i = 0;i < 4;i ++)
    {
        turn(x,i);
        turn(i,y);
    }
    turn(x,y);
}
int main()
{
    for(int i = 0;i < 4;i ++)
    {
        scanf("%s",st[i]);
    }
    for(int i = 0;i < 1 << 16;i ++)
    {
        vector <PII> step;
        memcpy(backup,st,sizeof st);
        for(int x = 0;x < 4;x ++)
        {
            for(int y = 0;y < 4;y ++)
            {
                if(i >> get(x,y) & 1)
                {
                    turnall(x,y);
                    step.push_back({x,y});
                }
            }
        }
        int dark = 0;
        for(int x = 0;x < 4;x ++)
        {
            for(int y = 0;y < 4;y ++)
            {
                if(st[x][y]=='+')
                {
                   dark = 1;
                   break;
                }
            }
        }
        if(dark == 0)
        {
            if(ans.empty()||ans.size() > step.size()) ans = step;
        }
         memcpy(st,backup,sizeof st);
    }
    
    cout << ans.size() << endl;
    for(auto p:ans)
    {
        cout << p.x+1<<" "<<p.y+1<<endl;
    }
    return 0;
}

1208. 翻硬币

有个初始态有个结束态。将初始态与结束态一一对比，遇到不一样的就将移动次数加一并且变换硬币状态。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int ans;
string start,aim;
void turn(int i)
{
    if(start[i]=='*')start[i] = 'o';
    else start[i] = '*';
}
int main()
{
    cin>>start>>aim;
    for(int i = 0;i < start.size() - 1;i ++)
    {
        if(start[i]!=aim[i])turn(i+1),ans++;
        
    }
    cout << ans <<endl;
    return 0;
}