半数集问题

半数集问题

时间: 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;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注