AcWing 题目题解 - 递归与递推

AcWing 题目题解 - 递归与递推 AcWing 92. 递归实现指数型枚举

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

输入格式
输入一个整数n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。对于没有选任何数的方案，输出空行。
本题有自定义校验器(SPJ)，各行（不同方案)之间的顺序任意。
数据范围
1≤n≤15

输入样例：

3

输出样例：

3
2
2 3
1
1 3
1 2
1 2 3

 方法一：暴力

对于每个数都有选or不选两种，所以有2^n种可能

#include 
using namespace std;
int n;
int main(){
    cin>>n;
    //1<>j&1) printf("%d ",j+1);
        }
        printf("n");
    }
}

方法二：递归

#include 
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<>n;
    DFS(1);  //从1开始选择，到n结束，所以不能从0开始；
    return 0;
}

 
AcWing 93. 递归实现组合型枚举

从1～n这n个整数中随机选出m个，输出所有可能的选择方案。
输入格式
两个整数n, m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 5 7排在1368前面)。
数据范围n > 0 ，0  

输入样例：

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 

#include
#include
#include
#include
using namespace std;
const int N=30;
int n,m;
int way[N];

void dfs(int u,int start)
{
    //if (u + n - start < m) return;  // 剪枝
    if(u==m+1)
    {
        for(int i=1;i<=m;i++) cout<>n>>m;
    dfs(1,1);
    return 0;
    
}

AcWing 94. 递归实现排列型枚举

把1 ～n这n个整数排成一行后随机打乱顺序，输出所有可能的次序。输入格式
一个整数n。
输出格式
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

输入样例：

3

输出样例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

递归

#include
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;
}

 非递归类型枚举：

C++STL中全排列函数next_permutation

全排列就是一次对对象序列或值序列的重新排列。例如，“ABC”中字符可能的排列是："ABC", "ACB", "BAC", "BCA", "CAB", "CBA"

next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列，同时并改变num数组的值。

另外，需要强调的是，next_permutation（）在使用前需要对欲排列数组按升序排序，否则只能找出该序列之后的全排列数。

#include 
using namespace std;
const int N=11;
int n,a[N];
int main() 
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        a[i]=i;
    do
    {
        for(int i=1;i<=n;i++)
            cout<

 AcWing 1209. 带分数

 

输入样例1：

100

输出样例1：

11

输入样例2：

105

输出样例2：

6

方法一： 

#include
#include
#include
#include

using namespace std;

const int N=520;

int had_use[N],ever[N];

int ans=0;

int n;

bool check(int a,int c)
{


    int b=n*c-a*c;//把公式整理一下，然后先把b计算出来

    if(!a||!b||!c)return false;

    memcpy(ever,had_use,sizeof had_use);//因为我们要对这个判断是否出现的数组进行修改，但是原数组又不能变化，所以我们
    //额外开一个数组进行使用，这样就可以达到判断且不会改变原数组的目的
    while(b)
    {
        int t=b%10;//取它的每一位，用来更新一下用过的数字
        b/=10;//删掉这个已经被选中的数
        if(!t||ever[t])return false;
        ever[t]=1;
    }
    for(int i=1;i<=9;i++)//遍历一下，判断每个数
      if(!ever[i])
      return false;

   return true;
}

void dfs_c(int x,int a,int c)//x表示我们已经用了多少个数字
{
    if(x>=10)return;//如果我们把10个数字都用了的话，那就直接return了

    if(check(a,c))ans++;//如果满足要求，那我们判断一下a,c是否符合题目要求，如果符合，那么答案++

    for(int i=1;i<=9;i++)//否则的话我们把c从1到9全部枚举一遍
      if(!had_use[i])
      {
          had_use[i]=1;
          dfs_c(x+1,a,c*10+i);//如果这个数没用过，那么我们就把它放在c的后面,继续dfs下一层
          had_use[i]=0;
      }
}
void dfs_a(int x,int a)
{
    if(a>=n)return;
    if(a)dfs_c(x,a,0);//如果说a是满足情况的，那么我们就枚举一下c,后面那个0表示c的大小

    for(int i=1;i<=9;i++)//枚举一下当前这个位置可以用哪些数字
      if(!had_use[i])
      {
          had_use[i]=1;
          dfs_a(x+1,a*10+i); //如果这个数没有被用过，那么我们就加上它，并且dfs下一层
          had_use[i]=0;//恢复现场，回溯一下
      }

}
int main()
{
    scanf("%d",&n);
    dfs_a(0,0);//第一个0表示我们已经用了多少个数字,后面那个0表示我们当前的a是多少
    printf("%d",ans);
    return 0;
}

方法二：

#include
using namespace std;

const int N = 20;
int shu[N];//存放全排列数字
bool st[N];//数字是否出现 
int n;//输入一个数字，验证符合的数字个数 
int cnt;//符合条件的数字个数 

//验证一个排列是否符合 
void yan()
{
    int a = 0,b = 0, c = 0;
    //分成三段
    for(int i = 2; i<9 ; i++)
    {
        for(int j = i+1 ; j<10 ; j++)
        {
            a = 0,b = 0,c = 0;//重新验证新数字 
            for(int x = 1 ; x < i ; x++) a = a * 10 + shu[x]  ; 
            for(int y = i ; y < j ; y++) b = b * 10 + shu[y]  ;
            for(int z = j ; z < 10; z++) c = c * 10 + shu[z]  ;

            //等式要符合，并且要是b和c能整除 
            if(n == a + (b / c)  && b % c == 0) cnt++; 
        }
    } 
}

void dfs(int u)
{
    //处理边界 
    if(u == 10)
    {
        //进行验证数字 
        yan();
        return ; 
    }

    //枚举1 - 9 不重复的数字 
    for(int i = 1 ; i<10 ; i++)
    {
        if(!st[i])
        {
            st[i] = true;
            shu[u] = i;
            dfs(u+1);//递归 
            st[i] = false;//恢复现场 
         } 
    }
}

int main()
{
    cin>>n;

    dfs(1);//从1开始 

    cout< 
 
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714574.html