一道非常好的搜索题目。 要将任意一个数拆分成斐波那契数的和，想到用搜索从前往后依次拆分验证，因为输出要求，我们可以巧妙地用字符串的形式储存结果。 考虑到dfs的可行性和最优性剪枝，我们可以增加一个变量t储存当前已经拆分的个数，如果当前拆分的个数已经大于了所求的最小值，那就没必要再搜索了，具体细节见注释。 小技巧：用读入流stringstream 进行整数到字符串的转化
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<sstream> using namespace std; int f[50],n,minn; string ans; void dfs(int x,int t,int sum,string str){//x表示当前位置，t表示已经拆分的个数，sum表示当前的值，str用于更新ans； if (sum==0){//退出条件：当前的数已经拆分完。 if (t<minn){ minn=t; ans=str; } return ; } if (t>minn||sum<f[x]) return ;//剪枝，如果当前的sum小于要拆分的斐波那契数，显然是不合法的； stringstream ss;//数字转换成字符串 string s; ss<<f[x]; ss>>s; if (n!=f[x]||n==1){//拆分条件 dfs(x+1,t+1,sum-f[x],str+" "+s); dfs(x+1,t,sum,str); } } int main(){ f[0]=0;f[1]=1; for (int i=2;i<=45;i++) f[i]=f[i-1]+f[i-2]; while(cin>>n){ minn=1e9; if (n<1){ cout<<"Illegal"<<endl;continue; } dfs(1,0,n,""); if (ans[0]==' ') ans.erase(0,1);//删除多余空格 cout<<ans<<endl; } return 0; }