1316：【例4.6】数的计数(Noip2001)
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 16192 通过数: 6870
【题目描述】
我们要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一个自然数n(n≤1000)，然后对此自然数按照如下方法进行处理：
不作任何处理；
在它的左边加上一个自然数，但该自然数不能超过原数的一半；
加上数后，继续按此规则进行处理，直到不能再加自然数为止。
【输入】
自然数n(n≤1000)。
【输出】
满足条件的数。
【输入样例】
6
【输出样例】
6
【提示】
【样例解释】
满足条件的数为如下所示：
6
16
26
126
36
136
【分析】
方法1：用递归（深搜）
递归式：f（n）=1＋f（1）＋f（2）＋…十f（n/2），当n较大时会超时，时间应该为指数级。
【参考代码1】：最后一组超时。
#include <stdio.h>
long long ans;
void dfs(int m) //统计m所扩展出的数据个数
{
int i;
ans++; //每出现一个原数，累加器加 1;
for(i=1;i<=m/2;i++) //左边添加不超过原数一半的自然数，作为新原数
dfs(i);
}
int main()
{
int n;
scanf("%d",&n);
dfs(n);
printf("%lld\n",ans);
return 0;
}
方法2：用记忆化搜索
实际上是对方法一的改进。设 h[ i ] 表示自然数 i 满足题意三个条件的数的个数。如果用递归求解，会带来重复计算问题。 例如在求 h[ 4 ]时，需要再求 h[ 1 ] 和 h[ 2 ]的值。现在我们用 h 数组记录在记忆求解过程中得出的所有子问题的解，当遇到重叠子问题时，直接使用前面记忆的结果。
【参考代码2】：AC。
#include <stdio.h>
#include <string.h>
#define N 1010
long long h[N];
void dfs(int m) //统计m所扩展出的数据个数
{
int i;
if(h[m]!=-1) //说明前面已经求得 h[m]的值，直接引用即可，不需要再递归
return;
h[m]=1; //将 h[m]置为1，表示 m 本身为一种情况
for(i=1;i<=m/2;i++)
{
dfs(i);
h[m]+=h[i];
}
}
int main()
{
int i,n;
scanf("%d",&n);
memset(h,-1,sizeof(h));
dfs(n);
printf("%lld\n",h[n]);
return 0;
}
方法3：用递推
用 h（n）表示自然数 n 所能扩展的数据个数，则 h（1）=1，h（2）=2， h（3）=2，h（4）=4，h（5）=4，h（6）=6，h（7）=6，h（8）=10，h（9）=10。分析以上数据，可得递推公式∶h（i）=1＋h（1）＋h（2）＋…＋h（i/2）。此算法的时间度为 O（n*n）。 设h[ i ] - i，按照规则扩展出的自然数个数（1<=i<= n）。下表列出了h[ i ] 值及其方案∶
由于1 为最小自然数，因此1 无法扩展出其他自然数。自然数 i（2<=i=n）按照规则扩展出的自然数包括自然数 i ; i 左边加上 1; i 左边加上 2 按规则扩展出的 h[2]个自然数…; 由于 i 左邻的自然数不超过[ i/2]，因此直至i左边加上 h[ [i/2] ] 个自然数（这些自然数由[ i/2 ] 按规则扩展出）为止。由此得出递推的计数公式∶
从1出发，按照上述公式递推至自然数 n，便可得出 n按规则扩展出的自然数个数 h[ n ]。
【参考代码3】：AC。
#include <stdio.h>
#define N 1010
long long h[N];
int main()
{
int i,j,n;
scanf("%d",&n);
for(i=1;i<=n;i++) //按照递增顺序计算扩展出的自然数的个数
{
h[i]=1; //扩展出的自然数包括 i本身
for(j=1;j<=i/2;j++) //i左边分别加上 1…自然数[i/2]，按规则扩展出的自然数
h[i]+=h[j];
}
printf("%lld\n",h[n]);
return 0;
}
方法4：方法三改进
定义数组s，s（x）=h（1）＋h（2）＋…＋h（x），h（x）=s（x）- s（x-1），此算法的时间复杂度可降到 O（n）。
【参考代码4】：AC。
#include <stdio.h>
#define N 1010
long long h[N],s[N];
int main()
{
int i,j,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
h[i]=1+s[i/2];
s[i]=s[i-1]+h[i];
}
printf("%lld\n",h[n]);
return 0;
}
方法5：还是递推
还是用递推，只要作仔细分析，其实我们还可以得到以下的递推公式;（1）当 i 为奇数时，h（i）=h（i-1）;（2）当 i 为偶数时，h（i）=h（i-1）十h（i/2）。
【参考代码5】：AC。
#include <stdio.h>
#define N 1010
long long h[N];
int main()
{
int i,j,n;
scanf("%d",&n);
h[1]=1;
for(i=2;i<=n;i++)
{
h[i]=h[i-1];
if(i%2==0)
h[i]=h[i-1]+h[i/2];
}
printf("%lld\n",h[n]);
return 0;
}
http://ybt.ssoier.cn:8088/problem_show.php?pid=1316