本文共 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/