数的计数

 数的计数

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 708  Solved: 333

Description

要求找出具有下列性质数的个数（包括输入的自然数n): 先输入一个自然数n( n <= 1000),然后对此自然数按照如下方法进行处理：（1）不作任何处理（2）在它的左边加上一个自然数，但该数不能超过原数的一半（3）加上数后，继续按此处理，直到不能再加自然数为止

Input

多个测试案例，每个测试案例输入一个自然数n

Output

输出满足以上条件的所有数的个数

Sample Input

6

Sample Output

6

HINT

对于6，满足条件的数有
6
16
26
126
36
136

#include<stdio.h>
int main()
{
    int n;
    int i,j,k;
    int dp[1001];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<=n;i++)
            dp[i]=0;
        dp[1]=1;
        for(i=2;i<=n;i++)
        {
            dp[i]=2;
            for(j=2;j<=i/2;j++)
            {
                dp[i]+=dp[j];
            }
        }
        printf("%d
",dp[n]);
    }
    return 0;
}