题目
问题描述：
要求找出具有下列性质数的个数（包含原数n）
输入一个自然数n（1<=n<=1000），对此自然数按照如下方法进行处理：
- 不作任何处理；
- 在它的左边加上一个自然数，但该自然数不能超过原数的一半；
- 加上数后，继续按照这个规则进行处理，直到不能再加数为止
举个例子：
比如输入的自然数n为6
经过上述规则处理后，一共有6个数满足所需的性质，它们分别是：
6
16
26
126
36
136
因此，输出结果为6.
输入
有N个测试用例
【输入】 N+1 行
第一行一个数N，表示测试用例个数
以下N行，每行一个数，代表每一个用例的输入数字
输出
每行一个数，代表每一用例的结果
分析
首先，我们来看一下问题规模：
输入一个自然数n（1<=n<=1000）
最大规模是1000，可不可以用穷举呢?
注意到用穷举的话，问题的时间复杂度为O(n^2)，肯定会超时。所以不能用穷举。
思考一下用穷举算法时，哪些步骤是重复计算的。
假设当前输入是100，那么某个输出为：
100
1100
2100
12100
...
我们用“
,”号分隔一下新增的数字，如下：
100
1，100
2，100
1，2，100
注意到其中的：
2
1，2
正是我们求2的排列时的结果。也就是说：
f(1000) = 1 + f(500) + f(250) + f(125) + ... + f(1)
于是我们可以用递推来写。
注意到求f(250)时，会计算f(125)，如果算完之后遇到f(125)时（例如计算f(500)）再算一次的话，就重复计算了。所以我们可以用一个数组来保存中间结果，即
cache = [f(1), f(2), ... , f(1000)]
再注意到，问题规模最大为1000，就是说cache只需500就行了(f(1000)只会算一次，不用保存)。
再思考一下，由于题目要求“该自然数不能超过原数的一半”，所以当输入为奇数时，结果跟前一个数(偶数)的结果是相同的。所以cache可以再缩一半。
好了，我们可以用代码实现之。
代码实现：
#include<stdio.h>
int cache[251];
int process(int next) {
if(next != 1000 && cache[next/2] != 0) {
return cache[next/2];
}
int count = 1;
int i;
for(i = next/2; i >= 1 ; i--) {
cache[i/2] = process(i);
count += cache[i/2];
}
return count;
}
int main()
{
memset(cache,0,sizeof(cache));
int N;
scanf("%d", &N);
int i;
for(i = 0; i < N; i++) {
int cur;
scanf("%d", &cur);
printf("%d\n", process(cur));
}
return 0;
}