问题描述

问题描述：
给定一个自然数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

// mycode ,这里是“多重集”，非多重集有点麻烦

#include <stdio.h>

int a[1000],aj;

void get(int n){
 int i,j,k;
 for(i=aj+1; i <= n; i++){
  k = i/2;
  for(a[i]=j=1; j <= k; j++)
   a[i] = a[i] + a[j];
 }
 aj = n;
}
int main(){
 int n;
 aj = a[0] = a[1] = 1;
 while(scanf("%d",&n)!=EOF){
  if(n > aj)
   get(n);
  printf("%d\n",a[n]);
 }
 return 0;
}

评论