【搜索】【入门】洛谷P1036 选数

题目描述

已知 n个整数x1​,x2​,…,xn​,以及1个整数k(k<n)。从nn个整数中任选kk个整数相加,可分别得到一系列的和。

例如当n=4,k=3,4个整数分别为3,7,12,19时,可得全部的组合与它们的和为:

3+7+12=22

3+7+19=29

7+12+19=3

3+12+19=34

现在,要求你计算出和为素数共有多少种。

例如上例,只有一种的和为素数:3+7+19=29

输入输出格式

输入格式:

键盘输入,格式为:

n,k(1≤n≤20,k<n)

x1​,x2​,…,xn​(1≤xi​≤5000000)

输出格式:

屏幕输出,格式为:1个整数(满足条件的种数)。

输入输出样例

输入样例: 
4 3
3 7 12 19
输出样例: 
1

1.首先要说说如何判断质数,判断质数最通俗易懂的办法就是:

  对于一个小于num的正整数x,如果num不能整除x,则num必然不能整除num/x (num = num/x * x)。反之相同。我们又知num =√num*√num。 如果n除以大于√num的数,必得到小于√num的商,而小于√num的整数已经在2到√num的整数试过了,因为就没有必要再试(√num, num)范围内的数了。代码如下:

  注:经常会看到别人说“一个数 n 如果是合数,那么它的所有的因子不超过sqrt(n)”。这句话是错误的。举一个例子,16的因子包括了1、2、4、8,但很明显8>√16。另外,因子跟因数是不一样的,因数还会包括数本身,如16的因数为1、2、4、8、16。

  所以我们可以这样实现:

#include<cstdio>
#include<cmath>
bool ask(int x)
{
        for (int i = 1 ; i <= sqrt(x) ;i ++){
               if(x % i == 0){
                    return 0;
               }     
        }
        return 1;
}

2。由于这个题的n非常小只有20,我们考虑搜索直接暴力。

分析题意可知本题适合用深搜。

深搜代码如下:

void dfs(int step ,int sum,int cnt)
{//step为总次数,sum为当前所选数的总和 cnt为当前选的数 
    if(step == n+1 || cnt == k){
        if(cnt == k && ask(sum)){
            ans ++;
        }
        return;
    }
    dfs(step + 1,sum +a[i],cnt+1);  //选择下一个数 
    dfs(step +1 ,sum ,cnt)          //不选择下一个数
    return; 
}

总代码:

#include <cstdio>
#include <cmath>
int n,k;
int ans;
const int N = 30;
int K[N];
bool ask(int x)
{
    for (int i = 2 ;i <= sqrt(x);i ++){
        if(x % i == 0){
            return 0;
        }
    }
    return 1;
}
void dfs(int step,int sum,int cnt)
{
    
    if((step == (n + 1) )|| (cnt == k)){
        if (ask(sum) && cnt == k){
            ans ++;
        }
        return;
    }
    dfs(step+1,sum + K[step],cnt +1);//选择下个数的情况 
    dfs(step+1,sum,cnt);      //不选择下个数的情况 
    return;
}
int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    scanf("%d%d",&n,&k);
    for (int i =  1 ;i <= n; i ++){
        scanf("%d",&K[i]);
    }
    dfs(1,0,0);
    printf("%d",ans);
//    fclose(stdin);
//    fclose(stdout);
    return 0;
}

ps:我永远喜欢石原里美!!

上一篇:洛谷P1036选数(素数+组合数)


下一篇:【云简评】之七《SAP应用在华登陆Windows Azure公有云》