题目

问题描述：

要求找出具有下列性质数的个数（包含原数n）

输入一个自然数n（1<=n<=1000），对此自然数按照如下方法进行处理：

  1. 不作任何处理；
  2. 在它的左边加上一个自然数，但该自然数不能超过原数的一半；
  3. 加上数后，继续按照这个规则进行处理，直到不能再加数为止

举个例子：

比如输入的自然数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
...

我们用“

Compra Minocin Online

,”号分隔一下新增的数字，如下：

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;
}