首页 > 代码库 > 等边三角形---dfs
等边三角形---dfs
蒜头君手上有一些小木棍，它们长短不一，蒜头君想用这些木棍拼出一个等边三角形，并且每根木棍都要用到。 例如，蒜头君手上有长度为 11，22，33，33 的4根木棍，他可以让长度为11，22 的木棍组成一条边，另外 22跟分别组成 22 条边，拼成一个边长为 33 的等边三角形。蒜头君希望你提前告诉他能不能拼出来，免得白费功夫。
输入格式
首先输入一个整数 n(3 \le n \le 20)n(3≤n≤20)，表示木棍数量，接下来输入 nn 根木棍的长度 p_i(1 \le p_i \le 10000)p?i??(1≤p?i??≤10000)。
输出格式
如果蒜头君能拼出等边三角形，输出"yes"，否则输出"no"。
样例输入1
51 2 3 4 5
样例输出1
yes
样例输入2
41 1 1 1
样例输出2
no
这也是典型的dfs：
对每一根木棍，要么加到a边，要么加到b边，要么加到c边。（因为所有的木棍都要使用）。dfs搜索每一个木棍即可。
#include<bits/stdc++.h>using namespace std;int n;int l[25];int len;bool dfs(int a,int b,int c,int id){ if(a==b&&b==c&&id==n) return true; if(a>len||b>len||c>len) return false; if(id>=n) return false; if(dfs(a+l[id],b,c,id+1)||dfs(a,b+l[id],c,id+1)||dfs(a,b,c+l[id],id+1)) return true; return false;}int main(){ cin>>n; int sum=0; int maxn=-1; for(int i=0; i<n; i++) { cin>>l[i]; sum+=l[i]; maxn=max(maxn,l[i]); } if((sum/3*3)!=sum||maxn>(sum/3)) { cout<<"no"<<endl; return 0; } int a,b,c; a=b=c=0; len=sum/3; if(dfs(a,b,c,0)) cout<<"yes"<<endl; else cout<<"no"<<endl; return 0;}
错误的搜索，之前学dfs的时候，习惯用循环，导致喜欢套用这个模板。。。。。。。。
#include<bits/stdc++.h>using namespace std;int n;int a[25];int len;bool vis[25];bool dfs(int sum,int index){ if(sum==len) return true; if(sum>len) return false; if(index>=n) return false; if(dfs(sum+a[index],index+1)) { vis[index]=1; return true; } else { if(dfs(sum,index+1)) return true; } return false;}int main(){ cin>>n; int sum=0; int maxn=-1; for(int i=0; i<n; i++) { cin>>a[i]; sum+=a[i]; maxn=max(maxn,a[i]); } if((sum/3*3)!=sum||maxn>(sum/3)) { cout<<"no"<<endl; return 0; } len=sum/3; bool flag=false; memset(vis,0,sizeof(vis)); for(int i=0; i<n; i++) { if(!vis[i]) { flag=true; if(!dfs(0,i)) { cout<<i<<endl; for(int i=0; i<n; i++) cout<<vis[i]<<" "; cout<<"no"<<endl; return 0; } flag=false; } } if(!flag) cout<<"yes"<<endl; else cout<<"no"<<endl;}
等边三角形---dfs
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。