1316：【例4.6】数的计数(Noip2001)
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
我们要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一个自然数n（n≤1000），然后对此自然数按照如下方法进行处理：
不作任何处理；
在它的左边加上一个自然数，但该自然数不能超过原数的一半；
加上数后，继续按此规则进行处理，直到不能再加自然数为止。
【输入】
自然数n（n≤1000）。
【输出】
满足条件的数。
【输入样例】
6 满足条件的数为 6(此部分不必输出)
16
26
126
36
136
【输出样例】
6
【来源】
No
【方法一】 递归 f(n)=1+f(1)+f(2)+…+f(div/2)，当n较大时会超时，时间应该为指数级。
1. #include<bits/stdc++.h> 2. using namespace std; 3. int ans=0; 4. void dfs(int n){ 5. int i; 6. ans++; 7. for(i=1;i<=n/2;i++) dfs(i); 8. } 9. int main() 10. { 11. int n; 12. cin>>n; 13. dfs(n); 14. cout<<ans; 15. return 0; 16. }
【方法二】记忆化搜索 设s[i]表示自然数i满足题意三个条件的数的个数。如果用递归求解，会重复来求一些子问题。例如在求s[4]时，需要再求s[1]和s[2]的值。
现在我们用s数组记录在记忆求解过程中得出的所有子问题的解，当遇到重叠子问题时，直接使用前面记忆的结果。
1. #include<bits/stdc++.h> 2. using namespace std; 3. int s[1001]; 4. void dfs(int n){ 5. int i; 6. if(s[n]!=-1) return;//直接引用以求得的是s[n],不需要再次递归 7. s[n]=1;//n自身的一种情况 8. for(i=1;i<=n/2;i++){ 9. dfs(i); 10. s[n]+=s[i]; 11. } 12. } 13. int main() 14. { 15. int n; 16. cin>>n; 17. for(int i=1;i<=n;i++) s[i]=-1;//初始化 18. dfs(n);//由顶倒下记忆化递归求解 19. cout<<s[n]; 20. return 0; 21. }
【方法三】递推 用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)。
1. #include<bits/stdc++.h> 2. using namespace std; 3. int s[1001]; 4. int main() 5. { 6. int n; 7. cin>>n; 8. for(int i=1;i<=n;i++) { 9. s[i]=1; 10. for(int j=1;j<=i/2;j++) s[i]+=s[j]; 11. } 12. cout<<s[n]; 13. return 0; 14. }
【方法四】 改进方法三 我们定义数组s，s(x)=h(1)+h(2)+…+h(x),h(x)=s(x)-s(x-1)，此算法的时间复杂度可降到O(n)。
1. #include<bits/stdc++.h> 2. using namespace std; 3. int h[1001],s[1001]; 4. int main() 5. { 6. int n; 7. cin>>n; 8. for(int i=1;i<=n;i++) { 9. h[i]=1+s[i/2]; 10. s[i]=s[i-1]+h[i]; 11. } 12. cout<<h[n]; 13. return 0; 14. }
【方法五】 递推 我们还可以得到以下的递推公式: (1)当i为奇数时，h(i)=h(i-1)；(2)当i为偶数时,h(i)=h(i-1)+h(i/2)。
1. #include<bits/stdc++.h> 2. using namespace std; 3. int s[1001]; 4. int main() 5. { 6. int n; 7. cin>>n; 8. s[1]=1; 9. for(int i=2;i<=n;i++) { 10. if(i%2==0) s[i]=s[i-1]+s[i/2]; 11. else s[i]=s[i-1]; 12. } 13. cout<<s[n]; 14. return 0; 15. }
