初学Dfs算法，送出水题2道 - 编程论坛

#2

叶纤2020-03-02 19:32

程序代码：

//我这人不会算法只能用最笨的方法第一题我把ij标出来方便我以后看

#include<iostream>

using std::cout;
using std::cin;
using std::endl;

int main()
{   int num[]= {6,8,4,2,3};
    int a{10};int count=0;
   // int c=0;
    //int j=0;
    for(int i=0; i<5&&num[i]; ++i)
    {   for( int j=1; j<5&&(j!=i); ++j)
        {  int c=num[i]+num[j];

            if(c==a)
            {

            ++count;cout<<i<<j<<endl;

            }

        }

    }
            if(count==0)
            cout << "meifax" ;

}

第二题一会儿写

#3

return_02020-03-02 19:38

他输出的是：
02
31

#4

return_02020-03-02 19:41

我张贴一部分第一题代码吧：

程序代码：

#include<bits/stdc++.h>
using namespace std;
int n,t,a[10010];
bool flg=false;
void dfs(int i,int sum){
    if(i==?????){
        if(?????==t)flg=?????;
        return;
    }
    dfs(i+1,?????);
    dfs(i+1,?????);
}
int main(){
    cin>>?????>>t;
    for(int i=?????;i<?????;i++){
        ?????
    }
    dfs(?????,?????);
    if(?????)cout<<"YES";
    else cout<<"NO";
    return 0;
}

#5

叶纤2020-03-02 19:42

对啊6+4=8+2=10第二题没看懂

[此贴子已经被作者于2020-3-2 21:26编辑过]

#6

return_02020-03-02 19:44

......

#7

return_02020-03-02 19:45

他貌似不让我输入耶

#8

叶纤2020-03-02 21:02

程序代码：

#include<iostream>

using std::cout;
using std::cin;
using std::endl;
bool arry(int num[],int dest,int a)
{    int count=0;

for(int i=0; i<dest&&num[i]; ++i)
    {   for( int j=1; j<dest&&(j!=i); ++j)
        {  int c=num[i]+num[j];

            if(c==a)
            {

            ++count;

            }

        }

    }
            return count!=0;
    }
int main()

{ int dest=0;
  int num[10010]= {};
    int a={};
    cout<<"输入目标t"<<endl;
    cin>>a;
    int count=0;
    cout<<"输入数组"<<endl;
    std::cin.ignore(32767,'\n');
    while((cin.peek()!=EOF)&&(cin.peek()!='\n'))
    {cin>>num[dest];
    ++dest;}
    cout<<std::boolalpha;

cout<< arry(num,dest,a);
}

#9

叶纤2020-03-02 22:31

第二题给个正确的例子啊，我想的答案不一定和你题目中的一致

#10

return_02020-03-03 08:24

第二个我贴代码，但不填主要部分

#11

return_02020-03-03 08:25

Input
4
2 3 4 9
Output
YES

#12

return_02020-03-03 08:26

程序代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[10010];
bool flg=false;
void dfs(int i,int t1,int t2){
    if(i==n){
        if(?????)flg=true;
        return;
    }
    dfs(?????);
    dfs(?????);
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[?????];
    }
    dfs(?????);
    if(?????)cout<<"YES";
    else cout<<"NO";
    return 0;
}

#13

小雪122020-03-03 11:00

[quote]以下是引用return_0在2020-3-2 19:17:53的发言：

1.子集的和
给定n个正整数，请从中找出一些子集组合，使得子集和恰好等于一个给定的目标t。
如果找到满足的条件了，输出“YES”,否则输出“NO”
如给出：3 5 4 7 6，目标t为10,
因为3+7、4+6满足条件，所以输出“YES”(提示请select后面一行字)
提示：这题没有提示！！！因为它简单到我给不出提示！！！
2.平分子集 1
给定n个正整数，请将它们分成两组，要求这两组数字的和完全相等，（不要求两组数字的数量相等），如果可行，则输出"YES"，否则输出"NO"。
如给出：3 5 4 7 6
因为没有满足条件的项，所以输出“NO”(提示请select后面一行字)
提示： dfs(i+1,sum1+a,sum);

[３７３６１７

#14

小雪122020-03-03 11:01

请问怎么操作我是小白‘

#15

叶纤2020-03-03 15:05

程序代码：

//我不会算法只能用最笨的方法
//第二题
#include<iostream>
using std::cout;
using std::cin;
using std::endl;
bool arry(int a[],short x,short y,short z)
{   short n1=y-x+1;
    short n2=z-y;
    int l[n1+1];int r[n2+1];
    int sum=0;int sum2=0;
    for(int i=0;i<n1;++i)
    { l[i]=a[i];
        sum+=l[i];}

// cout<<sum;
    for(int j=1;j<n2;++j)
    {r[j]=a[y+j];
        sum2+=r[j];}
  // cout<<sum2;
    return sum==sum2;}
int main()
{    int a[164356]={};int dexs=0
;     while((std::cin.peek()!=EOF)&&(std::cin.peek()!='\n'))
{     cin>>a[dexs];
      ++dexs;
    }
    cout<<std::boolalpha;
       cout<< arry(a,0,dexs/2,dexs);
}

3 5 1 9
true

程序代码：

第一题
#include<iostream>

using std::cout;
using std::cin;
using std::endl;
bool arry(int num[],int dest,int a)
{    int count=0;

for(int i=0; i<dest&&num[i]; ++i)
    {   for( int j=1; j<dest&&(j!=i); ++j)
        {  int c=num[i]+num[j];

            if(c==a)
            {

            ++count;

            }

        }

    }
            return count!=0;
    }
int main()

{ int dest=0;
  int num[10010]= {};
    int a={};
    cout<<"输入目标t"<<endl;
    cin>>a;
    int count=0;
    cout<<"输入数组"<<endl;
    std::cin.ignore(32767,'\n');
    while((cin.peek()!=EOF)&&(cin.peek()!='\n'))
    {cin>>num[dest];
    ++dest;}
    cout<<std::boolalpha;

cout<< arry(num,dest,a);
}

输入目标t
10 输入数组 1 5 8 9 2 true

[此贴子已经被作者于2020-3-3 15:08编辑过]

#16

return_02020-03-04 18:57

。。。

#17

叶纤2020-03-04 19:16

回复 16楼 return_0

咋滴啦，你看看我的代码对头不？给我品品呀，要不你把你的代码发出来，我品品你的代码也行呀

#18

return_02020-03-04 19:27

我贴完整代码：

#19

return_02020-03-04 19:27

程序代码：

#include<bits/stdc++.h>
using namespace std;
int n,t,a[10010];
bool flg=false;
void dfs(int i,int sum){
    if(i==n){
        if(sum==t)flg=true;
        return;
    }
    dfs(i+1,sum+a[i]);
    dfs(i+1,sum);
}
int main(){
    cin>>n>>t;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    dfs(0,0);
    if(flg)cout<<"YES";
    else cout<<"NO";
    return 0;
}

#20

return_02020-03-04 19:29

其实这种dfs（深度优先搜索）比跟枚举差不多快，但是写起来简单

#21

return_02020-03-04 19:29

现在全部分值移动到第二题。

#22

叶纤2020-03-04 19:54

好厉害啊递归用的这么熟练

#23

wmf20142020-03-04 20:23

void dfs(int i,int t1,int t2){
    if(i==n){
        if(t1==t2)flg=true;   '我填一个空，其他的同志们努力啊。我写的话，也会用递归，肯定不会使用全局变量。
        return;
    }
    dfs(?????);
    dfs(?????);
}

#24

return_02020-03-04 20:33

回复 23楼 wmf2014

填对了

#25

叶纤2020-03-04 20:41

还可以这么玩!我现在才知道这是一个填空题。。。。

#26

return_02020-03-05 08:44

呵呵

#27

return_02020-03-05 08:46

我提示一个吧
void dfs(int i,int t1,int t2){
    if(i==n){
        if(t1==t2)flg=true;
        return;
    }
    dfs(i+1,t1+a[i],t2);
    dfs(?????);
}

#28

wmf20142020-03-05 20:19

回复 27楼 return_0

都提示到这里了？怎么还没人填完空？

#29

叶纤2020-03-05 21:53

只会用非递归做这题