每天算法一丁点（3）--递归算法应用：半数集

半数集问题

题意：给定一个自然数n，由n开始依次产生半数集 set(n)，set(n) 的定义如下：

1. n 是 set(n) 中的元素
2. 在 n 的左边添加一个自然数，但该自然数不能超过最近添加的数的一半
3. 按此规律添加，直到不能添加自然数为止

例如：set(6) = {6，16，26，126，36，136}

求半数集中元素的个数

分析：给定一个数n，那么在其前可以添加的数有从 1 到  m = n/2 。在这 m 个数中，m 前可以添加的数又有从 1 到 s = m/2 。

因此，用递归+循环解决。循环 1 到 m 。 递归每一层前面可添加的数： n -> n/2 => m -> m/2

代码如下：

#include <iostream>
using namespace std;

// 输入n，计算其半数集中有多少数
// eag： set（6）={6，16，26，36，126，136} 有6个
// ps：半数集：元素每次生成都不大于最近添加的数的一半

int half_set(int n)
{
    int sum = 1;
    if (n > 1)
    {
        for (int i = 1; i <= n / 2; i++)
        {
            sum += half_set(i);
        }
    }
    return sum;
}

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        printf("%d的半数集中有%d个数\n",n,half_set(n));
    }
}

上面的代码有重复性的计算，比如 set(8)={8，18，28，38，48，128，138，148，248，1248}, 其中 8 前面可以添加 4 的半数集。 4 的半数集是确定的。因此利用数组来记住计算结果，可以避免不必要的计算：

代码优化如下：

#include <iostream>
using namespace std;
#define N 1100
int result[N];

int half_set(int n){
    int sum=1;
    if(result[n])
        return result[n];
    for(int i=1; i<=n/2; i++)
        sum += half_set(i);
    result[n] = sum;                    //记录已经计算过的数，避免重复计算；
    return sum;                         //比如8前面有1、2、3、4.这四个数前面可添加的数是都是固定的。
}
int main(){
    int n;
    while(scanf("%d",&n)){
        memset(result,0,sizeof(result));
        printf("%d的半数集元素个数为：%d\n",n,half_set(n));
    }
}