问一下这个DFS为什么在找到解以后无法正常记录数据

P1579 哥德巴赫猜想(升级版)

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


|