深搜算法 经典题目四 选棒子构成等边三角形 题目描述 将n个棒子拼成一个等边三角形 可以拼接 不可以更改木棒本身长度 要求每一根棒子都要用到 样式输入 输入棒子的个数 n 在输入 每根棒子的长度
4 1 1 1 1样式输入 如果不可以拼成等边三角形
no样式输入
5 1 2 3 4 5样式输出
yes基本思路 从第一根木棍开始开始搜索 再到下面一根木棍 直到若干个木棍的长度等于等边三角形的某一条的长度 在继续搜索 再到三根棍子都找出来 或者直接输出no 代码如下
#include<iostream> using namespace std; int a[101],n,sum=0; bool f,vis[1001]; void dfs(int cnt,int s,int st){ //cnt 表示木棍的个数 当木棍的长度为sum/3（s）时 算一根木棍 // s 表示每个等边三角形的长度 也就是说sum/3 //st 表示实际输入数据 是第几根木棍 if(f){ return ; //假如找到了 就直接结束 } if(cnt==3) { f=true; // 当三根棍子都找到了 就直接使返回值变为trun return ; } if(s=sum/3){ //当每一边 达到了s长度 就可以考虑下一根棍子 dfs(cnt+1,0,0); return ; } for(int i=0;i<=n;i++) //一般的情况 没有使三角形某一条边长度等于s 则要搜索下一条棍子 放弃上一棍子 还要清除标记 { if(!vis[i]){ vis[i]=true; //标记被选用了 dfs(cnt,s+a[i],i+1); vis[i]=false; //清除标记 所有的木棍都要考虑到 } } } int main(){ cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; sum+=a[i]; } if(sum%3!=0) { cout<<"no"; } else { dfs(0,0,0); if(f){ cout<<"yes"; } else cout<<"no"; } return 0; }