这个程序利用公式a[n]=a[1]+a[2]+...a[n/2]+1,代码较短，时间可能稍长一点。要缩短时间算至a[n/2]就可以直接算a[n]了

AC代码

#include <iostream>
using namespace std;
int main()
{
    int a[1001], n, i;//输入n输出a[n]
    a[1] = 1;//相当于结尾+1 
    cin >> n;
    for (i = 2; i <= n; i++)//依次从a[2]算到a[n] 
    {
        a[i] = 1;
        for (int j = 1; j <= i / 2; j++)//算出a[i]的值 
            a[i] += a[j];
    }
    cout << a[i - 1];//减去i多加的1
    return 0;
}

实际上，这道题非常简单，只要把题目读清楚就行了。 我们不需要把每一个添加过后的数算出来，只需要把添加到左边的数求出来就可以了。每一次，n都会在原数前面添加新数（不超过原数一半），不知道会重复多少次，此时可以用简单的递归做出来。 不懂？代码放出来得了。

``

/*
实际我们不需要直接将数添加在原数左边
 我们只需要把添加的数算出即可
*/
void add(int n)  //向左边添加数字的函数
{
    ans++;  //每次结果都是一个合法的数字，ans加1
    //判断能不能继续加，因为1整除2得0，不能继续添加
    if (n == 1)
        return;  //停止递归
    //遍历每一个能够添加的数
    for (int i = 1; i <= n / 2; i++)
        add(i);  //继续将i赋值于n递归
}

scanf("%d", &n);
add(n);  //输入输出后一个函数就解决了
printf("%d", ans);
return 0;

*tip:抄答案是不可能滴，你还得老老实实敲代码唷~~