本文共 2563 字，大约阅读时间需要 8 分钟。
湖南大学信息科学与工程学院第15届生涯规划节周末夜校之C++讲座
（Date：20201205，面向2020级大一新生）
已知n个整数 x1,x2,…,xn，以及一个整数 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）每组输入有两行，
输出格式：一个整数（满足条件的种数）。
4 3 3 7 12 19
1
1、找到递归开始状态，即递归入口；
2、调用递归函数；
3、判断递归参数合法性，制定“由错误导致的”递归终止条件；
4、为合法的参数执行运算操作；
5、找到递归边界并判断，制定“由递归边界导致的”递归终止条件；
6、确定下一步的递归方向，用更新的参数调用递归；
7、函数返回上一层递归前，还原在本层递归中改变的参数。
1、找到递归开始状态，即递归入口：ar作为待组合数字的存放位置，从ar的第一个数开始考虑组合，即ar[0]。因此main函数设置了标记为count，且循环次数为n-k（n为待组合数字的数量，因为至少要选k个数。考虑第n-k个数之后的数，作为首个组合数没有意义）
2、调用递归函数：search作为搜索的递归函数，第一个参数代表搜索深度，即已经有几个数被加入了组合。第二个参数代表开始搜索的位置，即每次从ar的第count-1位开始进行数字组合。
3、判断递归参数合法性，制定“由错误导致的”递归终止条件：如果当前开始的组合位置已经超过了ar数组的容量，那么直接返回，无任何操作。
4、为合法的参数执行运算操作：当前搜索位置的数加入数字组合，直接做加法。
5、找到递归边界并判断，制定“由递归边界导致的”递归终止条件：如果level==k-1，那么说明本次递归中的数字组合中数字的数量已经满足k个的要求，此时判断它们的和是不是素数，如果是，result（记录素数组合个数）加一，否则返回上一层递归，继续搜索。
6、确定下一步的递归方向，用更新的参数调用递归：下一层搜索时，搜索深度level+1，代表组合中的数字多了一个（因为是新一次的搜索）；搜索方向为当前position后面的所有数字（因此使用int count = position+1; count < n; count++这一循环）。
7、函数返回上一层递归前，还原在本层递归中改变的参数：本层中对于已选数字组合的和参数num，以及素数组合数量result进行了改变，在函数放回当前level中选择的数，返回上一层level之前，num减去本层中选取的数字，回到进入该层之前的情况。而result无需还原，因为result记录的是素数组合的种类，必须累加。
#include#include using namespace std;int ar[20] = {-1};int n = -1, k = -1, result = 0, num = 0;bool prime(int num) //判断素数 { int end = sqrt(num); for(int count = 2; count < end; count++) { if((num%count) == 0) return false; } return true;}void search(int level, int position){ if(position > n) //递归终止条件之一：当前位置超出数组范围 { return; //无任何操作，直接返回，无需复原 } num += ar[position]; //执行加法操作，选择当前位相加 if(level == k-1) //递归终止条件之二：选够了k个数，即递归的层数level=k-1 { if(prime(num)) { result++; //素数的数量加一 } return; //函数返回，由于result是一个累计素数统计，因此，无需还原result } for(int count = position+1; count < n; count++) //从当前位开始考虑后续的所有位，是否要选择加入 { search(level+1, count); //无论count循环位是多少，level，即递归深度加一 num -= ar[count]; //当递归从深一层返回的时候，需要减去在深一层中选择加上的数，即还原变量 }}int main(){ cin >> n >> k; for(int count = 0; count < n; count++) cin >> ar[count]; for(int count = 0; count < n-k; count++) //至少需要k个数相加，因此，循环位最高达到n-k即可 { search(0, count); //从第0号位作为递归起始条件（第一个数） num -= ar[count]; //当该函数返回时，从下一个数开始相加累计（for循环使count+1，因此需要将num复原为0） } cout << result << endl; return 0;}
转载地址：http://lqepz.baihongyu.com/