主要内容 #

1. 问题描述
2. 递归法求解
3. 算法改进

1. 问题描述 #

找出具有以下性质数的个数。先输入一个自然数n(n <= 1000)，然后将此自然数按照以下方式进行处理：
（1）不做任何处理；
（2）在它的左边加上一个自然数，但该自然数不能超过原数的一半；
（3）加上数后继续按照此规则进行处理，知道不能再加自然数为止。
输入格式
自然数n(n <= 1000)
输入格式
满足条件的数
输入样例
6
输出样例
6
以下部分不必输出
6
16
26
126
36
136

2. 递归方法求解 #

用递归f(n)=f(1)+f(2)+···+f(n/2)，进行计算。
参考程序

#include < iostream >
using namespace std;
//定义全局变量计数
int ans;
void dfs(int m){
   int i;
   //每出现一个原数，累加器加一
   ans++; 
   //左边添加不超过原数的一半的自然数，作为新原数。
   for(i = 1; i <= m/2; ++i){
      dfs(i);
   }
}

int main(){
   int n;
   cin >> n;
   dfs(n);
   cout << ans << endl;
   return 0;
}

当n较大时，递归调用的计算方法耗时较大，时间是指数级的。

3. 算法改进 #

用记忆化搜索方法，实际上是对递归方法的改进。设h[i]是自然数i满足题意的三个条件的数的个数。如果用递归求解，会重复求一些子问题。力图在球h[4]时，需要再求h[1]和h[2]的值。现在用h数组记录在求解过程中的所有子问题的解，当遇到重叠子问题的时候，直接使用前面记忆的结果。
参考程序

#include < iostream >
using namespace std;
int h[1001];
void dfs(int m){
   int i;
   //说明前面已经求得h[m]的值，直接应用即可，不需要再进行递归
   if(h[m] != -1) return;
   h[m] = 1; //将h[m]设置为1，表示m本身也代表一种情况。
   for(i = 1; i <= m/2; i++){
      dfs(i);
      h[m] += h[i];
   }
}

int main(){
   int n;
   cin >> n;
   for(int i = 1; i <= n; ++i){
      h[i] = -1;
   }
   dfs(n);
   cout << h[n] << endl;
   return 0;
}