数的计算(数的计数)
题目描述
我们要求找出具有下列性质数的个数(包含输入的自然数n)。先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:
- 不作任何处理;
- 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
- 加上数后,在新加上数的左边继续按此规则进行处理,直到不能再加自然数为止.
例如:
输入: 6
满足条件的数为 6 (此部分不必输出)
16
26
126
36
136
输出: 6
输入
只有一行一个整数，为自然数n（n<=1000）
输出
输出满足条件数的个数
样例输入
6
样例输出
6
分析
手动按照上述过程进行计算，会发现这是个递归的过程，对每一个原始数字m，在前面加i(1,2,3,...m/2)，即
h(n)=1+h(1)+f(2)+...+h(n/2)，对于每一个i，要按照同样的规则进行，这用递归可以实现（见例程1），递归过程中，每遇到一个原始数，计数器加1，用来统计个数。例程1在OJ中会显示超时，这是必然的，当n很大时，递归的过程就会很长，这主要源于其中会做大量的重复计算，每次计算h(n)，都要重复计算h(1)....h(n/2)，这样的问题在使用递归计算斐波那契数f(n)时，也会遇到，程序效率很低。解决的一个途径是使程序具有记忆功能，已计算出的数字就无需再次计算，直接使用即可。例程2使用数组实现了带记忆功能的递归，可以通过OJ系统。
也可以使用递推的方法来解决问题：已知
h(n)=1+h(1)+h(2)+...+h(n/2)，这就是一个递归式，程序写起来很容易（见例程3），两层for循环就可完成，递推比起无记忆的递归来效率要高得多。例程1是指数级的时间复杂度，而例程3的时间复杂度为O(n2)。问题可以进一步简化。通过对上面的公式进行推导可以发现：n为奇数时，
h(n)=h(n-1)，n为偶数时，h(n)=h(n-1)+h(n/2)，看懂了吗，使用这两个公式，可以将时间复杂度降低到O(n)，见例程4。
例程1
#include<iostream>
using namespace std;
int ans; //计数器
void dfs(int m){
ans++; //每出现一次原始数，ans++
for(int i=1; i<=m/2; i++){
dfs(i); //递归
}
}
int main(){
int n;
cin>>n;
dfs(n);
cout<<ans;
return 0;
}
例程2
#include<iostream>
using namespace std;
int h[1001]; //记忆数组，存储计算出的h[m]
void dfs(int m){
if(h[m]!=0) return; //有记忆，不再递归
h[m]=1; //无记忆，初始化为1，递归累加计算
for(int i=1; i<=m/2; i++){
dfs(i); //递归
h[m]+=h[i]; //累加
}
}
int main(){
int n;
cin>>n;
dfs(n);
cout<<h[n];
return 0;
}
例程3
#include<iostream>
using namespace std;
int h[1001];
int main(){
int n;
cin>>n;
h[1]=1; //初始化第一项h[1]
for(int s=2;s<=n;s++){ //对第s项
h[s]=1; //数字s自己算一个
for(int i=1;i<=s/2;i++) h[s]+=h[i];
}
cout<<h[n];
return 0;
}
例程4
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
h[1]=1; //初始化第一项
for(int i=2; i<=n; i++){
h[i]=h[i-1]; //递推
if(i%2==0) h[i]+=h[i/2]; //i为偶数时
}
cout<<h[n];
return 0;
}