liukairui @ 2019-07-17 23:23:11
问一下这个DFS为什么在找到解以后无法正常记录每一层的数字,会数多
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <stack>
using namespace std;
bool is_z[20050],flag=false;
int zsb[2500],n,cur=0,cnt=0,ans[2500];
void dfs(int now,int rest,int summary){
if(summary>n)return;
if(now==cur-1&&(rest!=1||is_z[n-summary]==false)){return;}
if(rest==1&&is_z[n-summary]==true){ans[cnt++]=n-summary;flag=true;return;}
if(rest==1&&is_z[n-summary]==false)return;
//边界
dfs(now,rest-1,summary+zsb[now]);
if(flag==true){ans[cnt++]=zsb[now];return;}
dfs(now+1,rest-1,summary+zsb[now]);
if(flag==true){ans[cnt++]=zsb[now];return;}
dfs(now+1,rest,summary);
if(flag==true){ans[cnt++]=zsb[now];return;}
return;
}
int main(){
cin>>n;
//构造素数表
memset(is_z,true,sizeof(is_z));
for(int i=2;i<=sqrt(n*3);i++){
if(is_z[i]==false)continue;
for(int j=2;j*i<=n*3;j++)is_z[i*j]=false;
}
for(int i=2;i<=n;i++)if(is_z[i]==true)zsb[cur++]=i;
//dfs
dfs(0,3,0); //dfs(now,已经选了几个数,summary)
for(int i=2;i>=0;i--)cout<<ans[i]<<" ";
return 0;
}
例如 输入2009 记录应该是 3 3 2003 但是我的记录是2 3 3 2003
by Lupus @ 2019-07-18 07:39:32
tql%%%%% orz