C++検索と遡及アルゴリズムの選択数
2237 ワード
せんすう
タイトルの説明
n個の整数x 1,x 2,...,xn,および1個の整数k(k入力
n,k (1≤n≤20,k＜n) x1,x2,...,xn(1≤<=xi≤<=5000000)
しゅつりょく
1つの整数(条件を満たす種数).
サンプル入力
サンプル出力
問題を解く
この問題は,n集合におけるk個数の全配列に判定素数を加えたものに相当するが,同じ配列を順序変更することはできず,すべての配列スキームを出力する必要はない.この考えによれば、コードをすぐに書くことができます.
しかしnum配列を省いてグローバル変数sumを直接定義し、dfsの文にsumでx[i]を直接加えることで、総量を計算する時間を節約し、配列の空間を節約することができ、一挙両得で、コードは以下の通りである.
どうですか.簡単になりましたか.(～￣▽￣)～
タイトルの説明
n個の整数x 1,x 2,...,xn,および1個の整数k(k
n,k (1≤n≤20,k＜n) x1,x2,...,xn(1≤<=xi≤<=5000000)
しゅつりょく
1つの整数(条件を満たす種数).
サンプル入力
4 3
3 7 12 19サンプル出力
1問題を解く
この問題は,n集合におけるk個数の全配列に判定素数を加えたものに相当するが,同じ配列を順序変更することはできず,すべての配列スキームを出力する必要はない.この考えによれば、コードをすぐに書くことができます.
#include
#include
using namespace std;
int n,k,x[21],num[21],cnt;
bool check()
{
int sum=0;
for(int i=1;i<=k;i++)
sum+=num[i];
for(int i=2;i<=sqrt(sum);i++)
if(sum%i==0)
return 0;
return 1;
}
void dfs(int a,int last)
{
for(int i=last;i<=n;i++)
{
num[a]=x[i];
if(a==k&&check()) cnt++;
else dfs(a+1,i+1);
}
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>x[i];
dfs(1,1);
cout< しかしnum配列を省いてグローバル変数sumを直接定義し、dfsの文にsumでx[i]を直接加えることで、総量を計算する時間を節約し、配列の空間を節約することができ、一挙両得で、コードは以下の通りである.
#include
#include
using namespace std;
int n,k,x[21],sum,cnt;
bool check()
{
for(int i=2;i<=sqrt(sum);i++)
if(sum%i==0)
return 0;
return 1;
}
void dfs(int a,int last)
{
for(int i=last;i<=n;i++)
{
sum+=x[i];
if(a==k&&check()) cnt++;
dfs(a+1,i+1);
sum-=x[i];
}
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>x[i];
dfs(1,1);
cout< どうですか.簡単になりましたか.(～￣▽￣)～