这道题和以前做过的求和是一个思路,凑数(求和)题目如下:
链接:https://blog.nowcoder.net/n/a6b71a5651874650a65945e9bae8e5bf
这个题是一维的,直接把一段数字进行遍历,然后把能构成的都输出出来就行。
在遍历解空间过程中,适当剪枝可以增大程序的时间效率。
#include<iostream> #include<vector> using namespace std; int n,m; vector<int> vec; void dfs(int i,int sum){ if(sum==m){//凑够数了,进行输出 for(int j=0;j<vec.size();j++){ if(j==vec.size()-1){ cout<<vec[j]<<endl; }else{ cout<<vec[j]<<" "; } } }else{//没凑过数,继续进行遍历 for(int j=i;j<=n&&sum<m&&j<=m;j++){//sum<m&&j<=m对树进行剪枝 vec.push_back(j); dfs(j+1,sum+j); vec.pop_back();//凑够了就弹出,没凑够说明加上这个数不可能凑够,所以也弹出 } } } int main(){ while(cin>>n>>m){ dfs(1,0); } return 0; }
而这道题,更像是二维的一个递归,因为有两条线要走,要分别同时凑够两条线,
可以这么想,把5的倍数加起来存到sum5,把3的倍数加起来存到sum3,剩下的数存到vector数组里。
然后取sum5-sum3的绝对值,这样只需看数组里的数能否凑出两部分,使其差值是abs(sum5-sum3)。
如果可以构成,就说明可以。
但是重点是怎么用递归表示两条线呢?
我们可以这样想,先把所有的数都加起来,然后再依次减去所有的数,
可以看代码进行分析:
#include<iostream> #include<vector> #include<math.h> using namespace std; vector<int> elsevec; int n,m,sum3,sum5,dis0; bool f(int i,int dis){ if(i==elsevec.size()){ return abs(dis)==dis0; }return (f(i+1,dis+elsevec[i])||f(i+1,dis-elsevec[i])); //**重点** } int main(){ while(cin>>n){ sum3=sum5=0; elsevec.clear(); int t=n; while(t--){ cin>>m; if(m%5==0){ sum5+=m; }else if(m%3==0){ sum3+=m; }else{ elsevec.push_back(m); } }dis0=abs(sum5-sum3); if(f(0,0)){ cout<<"true"<<endl; }else cout<<"false"<<endl; } return 0; }
代码的重点在于我标记的那个递推式:
我们可以画出解空间:
以
1 5 -5 1为例