递归

当寒月还在读大一的时候，他在一本武林秘籍中发现了神奇的二进制数（ 秘籍名：计算机基础 ）如果一个正整数表示成二进制，它的位数为n(不包含前导0)，寒月称它为一个n二进制数，所有的n二进制数中，1的总个数被寒月称为n对应的月之数。 例如，3二进制数总共有4个，分别是4(100)、5(101)、6(110)、7(111)，它们中1的个数一共是1＋2＋2＋3=8，所以3对应的月之数就是8。 输入：一个整数T，表示输入数据的组数，接下来T行，每行包含一个正整数 n(1<=n<=20)输出：对于每个n ，在一行内输出n对应的月之数 

#include <stdio.h>     //穷举法求月之数
#include <windows.h>
int iCount(int n){     //计算n的二进制表示中1的个数
	int count=0;
  while(n){
  	if(n%2==1)
    	count++;
    n=n/2;
  }return count;
}
void moonNum(int f[]){     //计算n的二进制分别对应的月之数
	int n,i,k,count;
  f[1]=1;
  for(n=2;n<=20;n++){
  	count=0;
    for(i=1<<(n-1);,k=1<<n;i<k;i++)
    	count=count+iCount(i);
    f[n]=count;
  }
}
int main(){
	int f[21],i;
	long long start,end;
  start=GetTickCount();     //Windows API，获得毫秒为单位的开机时间
  moonNum(f);
  for(i=1;i<=20;i++)
  	printf("%d\n",f[i]);
  end=GetTickCount();
  printf("%d\n",end-start);
  return 0;
}

#include <stdio.h>    //递归法求月之数
#include <windows.h>
int main(){
	int f[21],i;
  long long start,end;
  start=GetTickCount();
  f[1]=1;
  for(i=2;i<=20;i++)
  	f[i]=2*f[i-1]+(1<<(i-2));
  //或者：
  //int k=1;
  //for(i=2;i<=20;i++){
  //	f[i]=2*f[i-1]+k;
  //	k=k*2;
  //}
  for(i=2;i<=20;i++)
  	printf("%d\n",f[i]);
  end=GetTickCount();
  printf("%d\n",end-start);
  return 0;
}