133 递归 - 数的计数

主要内容

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;
}