首页 > 代码库 > 1415.数的计数

1415.数的计数

1415. [NOIP2001]数的计数

☆   输入文件:nums.in   输出文件:nums.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】

  我们要求找出具有下列性质数的个数(包含输入的自然数n):

先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理

l·不作任何处理:

2·在它的左边加上一个自然数,但该自然数不能超过原数的一半;

3·加上数后,继续按此规则进行处理,直到不能再立生自然数为止。

 

【输入格式】

       自然数n

【输出格式】

       满足条件的数的个数

【样例输入】

6

【样例输出】

6

【数据范围及提示】

       如题中所说,1<=n<=1000

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int f[1000];
 5 int main()
 6 {
 7     freopen("nums.in","r",stdin);
 8     freopen("nums.out","w",stdout);
 9     int n;
10     cin>>n;  
11     f[0]=1;  //数字是0时只有本身所以f【0】=1;
12     for(int  i=1;i<=n;++i)  
13     {
14         if(i%2==0)f[i]=f[i-1]+f[i/2];  //如果i是偶数,则i不超过i的一半的数会增加一个i/2,增加的就是i/2的所有情况;
15         else f[i]=f[i-1];  //i是奇数时则i不超过i的一半的数不变,不增加;
16     }
17     cout<<f[n];
18     fclose(stdin);fclose(stdout);
19     return 0;

 

1415.数的计数