题目:小明学算术

题目描述

小明最近接到了一项算数的作业。黑板上初始时只有一个数1。每次取在黑板上的任意两个数（可以相同）相加，得到另一个数，要求这个数比黑板上已有的任意一个数都大，并把所得的符合要求的和数也写在黑板上。这称为一次操作。当黑板上首次出现指定的整数n(2<=n<=1000)时，停止操作。
小明的加法学得很不好，算一次加法需要很长时间。他希望学编程的你找到一种方案，用最少的操作次数得出指定的数n。

输入格式

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

输出格式

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

很好的一道搜索题。

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

#include<iostream>
using namespace std;

int n;
int ans[20],a[20];

void update(int deep){
     for(int i=1;i<=deep;++i)
     ans[i]=a[i];
     ans[0]=deep;
     return ; 
     }


void Dfs(int deep){
     if(deep>=ans[0]||a[deep]>n) return ;
     if(a[deep]==n) 
     {update(deep);return ;}
     
     if(a[deep]>n/2)
     for(int j=deep-1;j>=1;--j)
     {
       a[deep+1]=a[deep]+a[j];
       if(a[deep+1]<a[deep]) continue;
       Dfs(deep+1);   
             }
     
     else 
     for(int i=deep;i>=deep/2;--i)
     for(int j=i;j>=1;--j)
     {
       a[deep+1]=a[i]+a[j];
       if(a[deep+1]<a[deep]) continue;
       Dfs(deep+1);     
             }
     }

int main()
{
    cin>>n;
    
    int i=1;
    a[1]=1;
    
    while(a[i]<=n/4)
    a[++i]=a[i-1]*2;
    
    if(i>=3)
    i--;
    
    ans[0]=14;
    Dfs(i);
    
    cout<<ans[0]-1<<endl;
    for(i=1;i<ans[0];++i)
    cout<<ans[i]<<" ";
    cout<<ans[ans[0]]<<endl;
    return 0;
    }