递归---选数

本文主要是介绍递归---选数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

选数

选数

题意

给定n,k,从 n 个整数中任选 k 个整数相加,如果相加的和为素数就记一次，输出有几个和为素数

思路

本题使用递归，先算出K个数的和，再判断是否为素数，如果是素数就记一，最后输出

算法一：递归

时间复杂度

普及

实现步骤

定义一个递归函数dfs，如果K个数的和为素数记一，并继续递归，防止算重。定义bool值判断是否为素数

代码

#include <iostream>
#include <cstdio>
using namespace std;
bool isprime(int a){//判断素数for(int i = 2;i * i <= a; i++)if(a % i == 0)return false;//扔回falsereturn true;//扔回true
}int n,k;
int a[25];
long long ans;void dfs(int m, int sum, int startx){//递归
//m代表现在选择了多少个数
//sum表示当前的和
//startx表示升序排列，以免算重if(m == k){//如果全部选完 if(isprime(sum))//如果和为素数ans++;return ;}for(int i = startx; i < n; i++)dfs(m + 1, sum + a[i], i + 1);//递归//步数要加一，和也要加//升序起始值要变成i+1,以免算重return ;
}int main(){scanf("%d%d",&n,&k);for(int i = 0; i < n; i++)scanf("%d",&a[i]);dfs(0,0,0);//调用函数，定义最初值为0 printf("%d\n",ans); return 0;
}

这篇关于递归---选数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---