半数集问题

半数集问题

时间： 1ms        内存：64M

描述：

给定一个自然数n，由n 开始可以依次产生半数集set(n)中的数如下。 (1) n∈set(n)； (2) 在n 的左边加上一个自然数，但该自然数不能超过最近添加的数的一半； (3) 按此规则进行处理，直到不能再添加自然数为止。 例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6个元素。 注意半数集是多重集。 对于给定的自然数n，计算半数集set(n)中的元素个数。

输入：

多组测试数据，每组一个整数n。(1≤n≤1000)

输出：

输出n的半数集set(n)中的元素个数。

示例输入：

6
1

示例输出：

6
1

提示：

参考答案（内存最优[1100]）：

#include <stdio.h>
#define MAX 1000
int arrays[MAX]= {0};
int HalfSet(int n)
{
    if(arrays[n]>0)  return arrays[n];
    else
    {
        arrays[n]=1;
        for(int i=1; i<=n/2; i++)
            arrays[n]+=HalfSet(i);
        return arrays[n];
    }
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int sum=HalfSet(n);
        printf("%d\n",sum);
    }
}

参考答案（时间最优[0]）：

#include<iostream>
using namespace std;
int f[1000]={0};
int set(int n)
{
int a=1;
int i;
if(f[n]>0) return f[n];
for(i=1;i<=n/2;i++)
a+=set(i);
f[n]=a;
return a;
}
int main()
{
int n;
while(cin>>n)
cout<<set(n)<<endl;
return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。