アルゴリズムノート練習8.1深さ優先探索(DFS)問題C:【再帰入門】組合せ+判定素数

8529 ワード
アルゴリズムメモ
アルゴリズムノート練習問題解合集
本題リンク
タイトル
タイトルは、既知のn個の整数b 1,b 2,...,bnおよび1個の整数k(k1行目の2つの整数を入力:n,k(1<=n<=20,k整数(条件を満たすシナリオ数)を出力します.
サンプル入力
4 3
3 7 12 19

サンプル出力
1

構想void DFS(int sum, int numCnt, int nowIndex); DFSには、現在のステータスを記録するために3つのパラメータが必要です.
  • sum:現在の数値の和.
  • numCnt:現在いくつかの数字があります.
  • nowIndex:配列要素の下付きラベルを処理しています.

    • 再帰境界は2つあります.
  • numCnt == k:この時点でkの数字が加算され、sumが素数であるかどうかをチェックします.
  • nowIndex == n:下付き文字は0からカウントされるため、処理中の要素の下付き文字が配列境界を越えた場合、直接戻ります.(注意1をチェックしてから2をチェックし、順番を逆にしてはいけません).

    • 再帰コールには、次の2つのケースがあります.
  • DFS(sum + nums[nowIndex], numCnt + 1, nowIndex + 1);現在処理中の要素を加算する.
  • DFS(sum, numCnt, nowIndex + 1);現在の要素をスキップします.

    • 注意:
  • 素数判断は0と1を漏らさないでください.

    • コード#コード#
    #include 
#include 
using namespace std;
int n, k, ans = 0;
vector<int> nums(25);
bool isPrime(int n) {
	if (n < 2)
		return false;
	for (int i = 2; i * i <= n; ++i)
		if (n % i == 0)
			return false; 
	return true;
} 
void DFS(int sum, int numCnt, int nowIndex) {
	if (numCnt == k) {
		if (isPrime(sum))
			++ans;
		return;
	} 
	if (nowIndex == n)
		return; 
	DFS(sum + nums[nowIndex], numCnt + 1, nowIndex + 1);
	DFS(sum, numCnt, nowIndex + 1);
} 
int main() {
	while (scanf("%d %d", &n, &k) != EOF) {
		for (int i = 0; i < n; ++i)
			scanf("%d", &nums[i]);
		DFS(0, 0, 0);
		printf("%d
    "    , ans); 
	} 
	return 0;
}
    ツリー関連アルゴリズム
    テンセントの微信のお年玉のアルゴリズム