学步园

思想为递归的思想。

注意半数集不是多重集。集合中已经有的元素不再添加到集合中。

必须注意重复问题！

由于0<n<201所以0<n/2<=100

故可能产生重复的是一个2位数

例如30->1230和30->230->1230相同。

或者60-(添加24)>2460-(添加1)>12460和60-(添加4)>460-(添加2)>2460-(添加1)>12460

在一位数y=x%10的半数集中已经产生。

这样就必须剔除重复的元素。

那么判断的条件就是i>10&&(i/10<=(i%10)/2)

#include <stdio.h><br /> #include <string.h><br /> long halfset(int n,int *a)<br /> {<br /> long k=1;<br /> long i;<br /> //如果已经求出此数的半数集，则直接返回<br /> if (a[n]>0)<br /> return a[n];<br /> for (i=1;i<=n/2;i++){<br /> k+=halfset(i,a);<br /> if (i>10&&(i/10<=((i%10)/2))<br /> {<br /> k-=a[i/10];<br /> }<br /> }<br /> a[n] = k;<br /> return k;<br /> }</p> <p>int main()<br /> {<br /> int n;<br /> int a[300];<br /> memset(a, 0, sizeof(a));<br /> while (scanf("%d", &n)!=EOF)<br /> printf("%d/n", halfset(n,a));<br /> return 0;<br /> }<br />