题目描述

小明最近接到了一项算数的作业。黑板上初始时只有一个数1。每次取在黑板上的任意两个数（可以相同）相加，得到另一个数，要求这个数比黑板上已有的任意一个数都大，并把所得的符合要求的和数也写在黑板上。这称为一次操作。当黑板上首次出现指定的整数n(2<=n<=1000)时，停止操作。

小明的加法学得很不好，算一次加法需要很长时间。他希望学编程的你找到一种方案，用最少的操作次数得出指定的数n。

输入格式

只有一行。包含一个整数n(2<=n<=1000)，表示指定的整数。

输出格式

两行。第一行一个整数，表示最少操作次数。第二行若干个空格隔开的整数，表示操作结束时黑板上的所有数，按从小到大的顺序输出。若有多组符合要求的解，输出次大的数最大的一组；若还多解，输出第三大的数最大的一组；以此类推。

 

 

 

很好的一道搜索题。

因为所求解要长度最短，而且最后几个数和同长度解要大，所以可以由大到小搜索，得出解后，大于等于该长度的一律剪枝。而且通过观察得出，在数列后面几个数一定是 前一个数+较小的一个数 推出的，否则推出前面这个数干嘛呢，而推当下的这个数又是干嘛呢。

1 #include
     
       2 using namespace std; 3  4 int n; 5 int ans[20],a[20]; 6  7 void update(int deep){ 8      for(int i=1;i<=deep;++i) 9      ans[i]=a[i];10      ans[0]=deep;11      return ; 12      }13 14 15 void Dfs(int deep){16      if(deep>=ans[0]||a[deep]>n) return ;17      if(a[deep]==n) 18      {update(deep);return ;}19      20      if(a[deep]>n/2)21      for(int j=deep-1;j>=1;--j)22      {23        a[deep+1]=a[deep]+a[j];24        if(a[deep+1]
      
       =deep/2;--i)30      for(int j=i;j>=1;--j)31      {32        a[deep+1]=a[i]+a[j];33        if(a[deep+1]
       
        >n;41     42     int i=1;43     a[1]=1;44     45     while(a[i]<=n/4)46     a[++i]=a[i-1]*2;47     48     if(i>=3)49     i--;50     51     ans[0]=14;52     Dfs(i);53     54     cout<
        
         <