P1028 [NOIP2001 普及组] 数的计算

题目描述：

我们要求找出具有下列性质数的个数(包含输入的正整数 nn)。
先输入一个正整数 nn(n \le 1000n≤1000),然后对此正整数按照如下方法进行处理：
1.不作任何处理；
2.在它的左边加上一个正整数,但该正整数不能超过原数的一半；
3.加上数后,继续按此规则进行处理,直到不能再加正整数为止。

输入格式
1 个正整数 nn(n \le 1000n≤1000)

输出格式

1 个整数，表示具有该性质数的个数。

输入输出样例

输入
6
输出
6

说明/提示
满足条件的数为
6，16，26，126，36，136

【题目来源】
NOIP 2001 普及组第一题

分析

根据题干的意思，这道题可以通过递归做：

使用一个for循环，小于n/2, i++,count++
再使用递归
上代码

void sum(int n){
for(int i = 1;i <= n/2; i++){
count ++;
sum(i);
}
}

但是，这样时间会超过1s，所以暴力递规是不行的，接下来再分析一下

a[1] = 1
a[2] = 2
a[3] = 2
a[4] = 4
a[5] = 4
…
…
…

a[1] = 1
a[2] = a[1] + 1
a[3] = a[1] + a[2] + 1
a[4] = a[1] + a[2] + 1
a[6] = a[1] + a[2] +a[3] + 1

所以,先创建一个用于存放数据个数的数组a，使用两个for循环，根据这个递推公式可得：

for( i = 1;i <= n; i++){
for(j = 1; j <= i/2; j++){
a[i] = a[i] + a[j]; //递推公式a[4] = a[2] + a[1] + 1
}
}

最后

源代码

#include<stdio.h>
int main(){
//使用递推公式计算
int a[1001];//定义一个存放所有数个数的数组
for(int i = 0;i < 1001; i++){
a[i] = 1;
}//初始化存放数组
int i,j,n;
scanf("%d",&n);
//printf("%d",n);
for( i = 1;i <= n; i++){
for(j = 1; j <= i/2; j++){
a[i] = a[i] + a[j];//递推公式a[4] = a[2] + a[1] + 1
}
}
printf("%d\n",a[n]);
// for(int i = 1;i <= n; i++){
// printf("%d ",a[i]);
// }
return 0;
}