題目鏈接：https://www.luogu.com.cn/problem/P1036

考點：素數(shù)、dfs、組合

題意：給n個整數(shù)，從中選取k個求和，統(tǒng)計“和為素數(shù)”的次數(shù)。

做法一（直接dfs）：
dfs，3個參數(shù)分別記錄了數(shù)組下標(biāo)起點、當(dāng)前已選數(shù)的和、當(dāng)前已選數(shù)量。

#include <bits/stdc++.h> using namespace std;int A[25]; int cnt = 0; int n,k; bool isprime(int x) {if (x == 0 || x == 1) return true;for (int i = 2; i <= sqrt(x); i++) {if (x % i == 0) return false;}return true; }void dfs(int sta, int sum, int total) {if (total == k) {//cout << sum << endl; // debugif (isprime(sum)) cnt++;return;} for (int i = sta; i < n; i++) {dfs(i + 1, sum + A[i], total + 1); // 從起點的下一個數(shù)開始取數(shù)，已選數(shù)+1} }int main() {cin >> n >> k;for (int i = 0; i < n; i++) cin >> A[i];dfs(0, 0, 0);cout << cnt;return 0; }

一開始沒想到可以用dfs，只是想著能遍歷出所有組合情況就好了。

解法二（遍歷組合）：
不就是求每種組合的和嗎，遍歷就完事兒了。

遍歷組合的算法：https://blog.csdn.net/Kwansy/article/details/103538652

#include <bits/stdc++.h> using namespace std; const int Max = 20; int A[Max]; int cnt = 0;bool isprime(int x) {if (x == 0 || x == 1) return true;for (int i = 2; i <= sqrt(x); i++) {if (x % i == 0) return false;}return true; }void dfs(int sta, int n, int k, int cur) {static int R[Max];if (cur == k) {int sum = 0;for (int i = 0; i < k; i++) {//cout << R[i] << " ";sum += R[i];}if (isprime(sum)) cnt++;return;}for (int i = sta; i < n; i++) { // 遍歷起點R[cur] = A[i];dfs(i+1, n, k, cur+1);} }int main() {int n,k; cin >> n >> k;for (int i = 0; i < n; i++) cin >> A[i];dfs(0, n, k, 0); // 從第0個開始取，總長n，取k個，當(dāng)前已取0cout << cnt;return 0; }

總結(jié)

以上是生活随笔為你收集整理的【dfs】P1036 选数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。