已知n个整数x1,x2,…,xn ，以及1 个整数k (k<n)。从n 个整数中任选k 个整数相加，可分别得到一系列的和。例如当n=4,k=3,4 个整数分别为3,7,12,19 时，可得全部的组合与它们的和为：
3+7+12=22
3+7+19=29
7+12+19=38
3+12+19=34现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3+7+19=29
输入格式为：
n,k(1≤n≤20,k<n)
x1,x2,…,xn(1≤xi≤5000000)
输出格式
屏幕输出，格式为：1 个整数（满足条件的种数）。
做这道鬼题目把这不降原则玩意想出来了，但是没想到居然有名字，还挺高级
不降原则是个神马意思呢
举个例子：比如说在6里面随便选5个数，那么选法都是什么呢？瞎枚举？
12345
12346
前两个还不会弄混
然后很可能就乱了
少点数可能不会乱
但是多了就不好整了
比如说在100里随便选50个数。
123456789101112......Die.
所以我们可以运用不降原则：保证枚举的这些数是升序排列
其实真正的不降原则还可以平
比如122334......
但是请注意这道题也不能平
否则就有重复数字了
拿6个里面选3个举例子
123
124
125
126
第一轮枚举完毕。
第二个数加一
13？
这个“？”应该是4，因为是升序排列
134
135
136
接着，就是这样
145
146
156
第一位是1枚举完毕
第一位是2呢?
234
235
236
245
246
256就是这样的，枚举还是蛮清晰的吧
以此类推.....
345
346
356
456然后就枚举不了了，结束。所以说，这样就可以避免判重了
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define false 0
#define true 1
int x[20],n,k;//依照题目所设
int isprime(int n){//判断是否质数
int s=sqrt((double) n);
for(int i=2;i<=s;i++){
if(n%i==0)return false;
}
return true;
}
int rule(int chose_num,int already_sum,int start,int end){//choose_left_num为剩余的k，already_sum为前面累加的和，start和end为全组合剩下数字的选取范围；调用递归生成全组合，在过程中逐渐把K个数相加，当选取的数个数为0时，直接返回前面的累加和是否为质数即可
if(chose_num==0)
return isprime(already_sum);
int sum=0;
for(int i=start;i<=end;i++){
sum+=rule(chose_num-1,already_sum+x[i],i+1,end);
}
return sum;
}
int main(){
scanf("%D%D", &n, &k);
for(int i =0;i<n;i++) scanf("%d", &x[i]);
printf("%d", rule(k,0,0,n-1));//调用递归解决问题
system("pause");
return 0;
}
