半数集问题

[higer]

问题描述：
给定一个自然数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)中的元素个数。

输入

输入数据m行，每行给出一个整数n。(0〈n〈1000)

输出

输出只有m行，每行给出半数集set(n)中的元素个数。

输入样例

6
99

输出样例

6
9042

-------------------------------------------------
下面是南开大学的Online Judge，大家可以注册一个Id，完成这道题后可以在上面测试自己算法的正确性。（注：以后贴题的时候争取贴上能够测
试的网址）
http://acm.nankai.edu.cn/p1037.html

[higer]

/
************************************************************************/
/* 半数集问题 */
/
************************************************************************/
#include "stdio.h"
int count(int n){
if(n==1) return 1;
else{
int m=n/2;
int i=1,sum=1;
for (i=1;i<=m;i++) {
sum+=count(i);
}
return sum;
}
}
int main(){
int n;
scanf("%d",&n);
printf("%d\n",count(n));
return 0;
}

题目给出"注意半数集是多重集"，因此算法比较简单。（测试的网址页面中的题"半数集不是多重集。集合中已经有的元素不再添加到集合中。"，因此如果不
是多重集的话还要仔细考虑。）

[higer]

妙！！！！

算法改进（使用备忘录的方法）from 【http://blog.csdn.net/xqls_xqls/archive/
2008/11/21/3344267.aspx】：

l 使用递归算法效率较低，重复计算了先前已经计算过的值

set(6/2)

↙ ↓ ↘

set(1/2) set(2/2) set(3/2)

↓ ↓

set(1/2) set(1/2)

如上图，重复计算了set(0)与set(1)

为了解决上述问题，就应将已经计算的结果保存起来。

设p[n]表示自然数m产生半数集的个数，则有如下关系：

p[m] = 1+p[1]+p[2]+p[3]+ ... +p[n/2] ( p[0] = 0 )

l 定义一个整形数组p ，空间大小为自然数n的一半。用count来记录p[n]的值，即最终结果。这样做的好处可以使循环的次数大大减小。

while(fin>>N)

{

count = 0;

n = N/2;

p = new int [n+1];

for(i=0;i<=n;i++)

p[i] = 0;

for(i= 1;i<=n;i++)

{

int k = i/2;

for(int j = 1;j <= k;j++)

p[i] += p[j];

p[i] += 1;

count += p[i];

}

count += 1;

fout<<count<<"\n";

[李效云]

这道题我做过，你这样写，有重复的元素，违背了集合的根本性质，你再考虑考虑

2009/5/4 higer <higerin...@gmail.com>

[Ziyu Yu]

题目说了是多重集...
李效云 写道:

[zhong nanhai]

我都说明了。。。

On 5/4/09, 李效云 <lixiao...@gmail.com> wrote:
> 这道题我做过，你这样写，有重复的元素，违背了集合的根本性质，你再考虑考虑
>
> 2009/5/4 higer <higerin...@gmail.com>
>
>> 妙！！！！
>>
>> 算法改进（使用备忘录的方法）from 【http://blog.csdn.net/xqls_xqls/archive/

>> 2008/11/21/3344267.aspx<http://blog.csdn.net/xqls_xqls/archive/%0A2008/11/21/3344267.aspx>