数的分解

数的分解：任何数都能分解成2的幂，比如
  7=1+1+1+1+1+1+1
  =1+1+1+1+1+2
  =1+1+1+2+2
  =1+2+2+2
  =1+1+1+4
  =1+2+4
求任意整数n(n<100亿)的此类划分数

f(2m+1)=f(2m)，f(2m)=f(2m-1)+f(m)
其实是递归的思路。
奇数2m+1的划分，只要对应的2m的每隔划分，+1就可以了，所以f(2m+1)=f(2m)；
偶数2m的划分，分为两类，一类是划分中含有1的，这类等于f(2m-1)，因为只要这类前者
每个划分-1，都对应了。另一类是划分中不含有1的，这类等于f(m)，因为只要f(m)的每个
划分都乘以2，就对应了。

#include 

unsigned long f(long n)
{
  if (n <= 1) return 1;
  if ((n & 1) == 1) return f(n - 1);
  return f(n - 1) + f(n >> 1);
}

void main()
{
  long i;
  for (i = 1; i < 21; i++)
  {
    printf("f(%ld) = %lu\n", i, f(i));
  }
}