已知n個(gè)整數(shù)x1,x2,…,xn ，以及1 個(gè)整數(shù)k (k<n)。從n 個(gè)整數(shù)中任選k 個(gè)整數(shù)相加，可分別得到一系列的和。例如當(dāng)n=4,k=3,4 個(gè)整數(shù)分別為3,7,12,19 時(shí)，可得全部的組合與它們的和為：
3+7+12=22
3+7+19=29
7+12+19=38
3+12+19=34現(xiàn)在，要求你計(jì)算出和為素?cái)?shù)共有多少種。
例如上例，只有一種的和為素?cái)?shù)：3+7+19=29
輸入格式為：
n,k(1≤n≤20,k<n)
x1?,x2?,…,xn?(1≤xi?≤5000000)
輸出格式
屏幕輸出，格式為：1 個(gè)整數(shù)（滿足條件的種數(shù)）。
做這道鬼題目把這不降原則玩意想出來(lái)了，但是沒想到居然有名字，還挺高級(jí)
不降原則是個(gè)神馬意思呢
舉個(gè)例子：比如說(shuō)在6里面隨便選5個(gè)數(shù)，那么選法都是什么呢？瞎枚舉？
12345
12346
前兩個(gè)還不會(huì)弄混
然后很可能就亂了
少點(diǎn)數(shù)可能不會(huì)亂
但是多了就不好整了
比如說(shuō)在100里隨便選50個(gè)數(shù)。
123456789101112......Die.
所以我們可以運(yùn)用不降原則：保證枚舉的這些數(shù)是升序排列
其實(shí)真正的不降原則還可以平
比如122334......
但是請(qǐng)注意這道題也不能平
否則就有重復(fù)數(shù)字了
拿6個(gè)里面選3個(gè)舉例子
123
124
125
126
第一輪枚舉完畢。
第二個(gè)數(shù)加一
13？
這個(gè)“？”應(yīng)該是4，因?yàn)槭巧蚺帕?/p>
134
135
136
接著，就是這樣
145
146
156
第一位是1枚舉完畢
第一位是2呢?
234
235
236
245
246
256就是這樣的，枚舉還是蠻清晰的吧
以此類推.....
345
346
356
456然后就枚舉不了了，結(jié)束。所以說(shuō)，這樣就可以避免判重了
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define?false?0
#define?true?1
int?x[20],n,k;//依照題目所設(shè)
int?isprime(int?n){//判斷是否質(zhì)數(shù)
????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為全組合剩下數(shù)字的選取范圍；調(diào)用遞歸生成全組合，在過(guò)程中逐漸把K個(gè)數(shù)相加，當(dāng)選取的數(shù)個(gè)數(shù)為0時(shí)，直接返回前面的累加和是否為質(zhì)數(shù)即可
????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));//調(diào)用遞歸解決問(wèn)題
????system("pause");
????return?0;
}
