【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(1)

  • Post author:
  • Post category:其他



目录


写在前面:


题目:P1036 [NOIP2002 普及组] 选数 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)


题目描述:


输入格式:


输出格式:


输入样例:


输出样例:


解题思路:


代码:


AC !!!!!!!!!!


写在最后:


写在前面:

怎么样才能学好一个算法?

我个人认为,系统性的刷题尤为重要,

所以,为了学好深度优先搜索,为了用好暴搜应对蓝桥杯,

事不宜迟,我们即刻开始刷题!

题目:

P1036 [NOIP2002 普及组] 选数 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述:

输入格式:

第一行两个空格隔开的整数 n , k(1 ≤ n ≤ 20,k < n)。

第二行 n 个整数,分别为 x1​, x2​, ⋯, xn​(1 ≤ 5 × 1061 ≤ xi ​≤ 5 × 106)。

输出格式:

输出一个整数,表示种类数。

输入样例:

4 3
3 7 12 19

输出样例:

1

解题思路:

我们使用深度优先搜索的时候,

第一个要注意的点是搜索的顺序,

因为我们要保证,

我们写出的递归结构能够遍历

所有情况

在我们初学搜索的时候,我们一定要画一个

递归搜索树

观察,

递归非常抽象,画图能很好的帮助我们解题。(以上递归搜索的基本思路,多熟悉总是好的)

接下来是

具体思路

题目叫我们从n个数里面选k个相加,判断是否能成素数,

然后要我们输入那n个数,

那我们先画一下递归搜索树:

根节点:(以输入n=4, k=3, 输入数据:3,7,12,19)

我们根据每个位置能放什么数据的思路

往下递归搜索:


然后我们根据题目要求,

继续递归搜索,我们发现有些组合非法,需要剪枝:

我们继续递归搜索:

最后只剩四种组合合法,

我们再判断这四种组合是否相加为素数,

接下来,我们说一下剪枝,

如果该位置

已经存放的数+剩余可选的数<需要的数量

就剪枝


下面是代码实现:

代码:

//养成好习惯,包上常用头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

//根据题目要求开数组
const int N = 30;

//arr数组用来读入数据
int arr[N];

//st数组用来存放数据
int st[N];

int n, k;

//记录素数个数并返回
int res = 0;

//判断是否是素数
bool is_prime(int sum)
{
    if(sum < 2)
    {
        return false;
    }
    for(int i = 2; i <= sum / i; i++)
    {
        if(sum % i == 0)
        {
            return false;
        }
    }
    return true;
}

void dfs(int u, int start)
{
    //如果:(已经存放的数 + 剩余可选的数 < 需要的数量)就剪枝
    if((u - 1) + (n - start + 1) < k)
    {
        return;
    }
    
    if(u > k)
    {
        //求和
        int sum = 0;
        for(int i = 1; i <= k; i++)
        {
            sum += st[i];
        }
        
        //判断
        if(is_prime(sum))
        {
            res++;
        }
        return;
    }
    
    for(int i = start; i <= n; i++)
    {
        st[u] = arr[i];
        dfs(u + 1, i + 1);
        st[i] = 0;
    }
}

int main()
{
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &arr[i]);
    }
    dfs(1, 1);
    printf("%d\n", res);
    return 0;
}

AC !!!!!!!!!!

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果喜欢本文的话,欢迎点赞和评论,写下你的见解。

如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。

之后我还会输出更多高质量内容,欢迎收看。



版权声明:本文为Locky136原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。