半数集问题 （C语言代码）

解题思路:

#include <stdio.h>       //递归动态规划
int Sum[1000];
int half(int );
int main()
{
	int n,i;
	while (scanf("%d",&n)!=EOF)
	{
		for (i=0;i<1001;i++)
			Sum[i]=-1;
		printf("%d\n",half(n));
	}
	return 0;
}

int half(int n)
{
	int i,sum=0;
	if (Sum[n]!=-1)
		return Sum[n];
	if (n==1)
	{
		Sum[n]=1;
		return Sum[n];
	}
	for (i=n/2;i>=1;i--)
		sum+=half(i);
	Sum[n]=sum;
	return ++Sum[n];
}

注意事项:





参考代码: