Question

这是一道找规律的编程题，但是我想不太清楚，请各位帮忙，谢谢。

如果一个10进制数转化为二进制之后，1的个数多余0的个数，那么这个数就是A类数。
给第一个n，输出[1,n]范围内A类数的个数。

Answer 1

转换二进制的过程你要清楚，一个十进制数除以2，得到的余数就是当前数字的二进制的最后一位数，
拿得到的商再除以2得到的就是二进制的倒数第二位数，依次类推，当除以2的结果为1的时候就完全转换成二进制。我们可以用%运算得到余数，/运算得到商。

a=0;设置一个变量记录1的数量

b=0;设置一个变量记录0的数量
c=0;设置一边变量记录一个数除以2之后的商；
以下是计算每个n的二进制中1和0个数的程序
for（c!=1） //当商不等于1的时候说明没有完全转换成二进制，仍需要循环计算
{
if(n%2=1) //n%2是将十进制转化成二进制的过程，每%2一次得到二进制的一位
{
a+=1;
}

else

{
b+=1;

}
c=n/2; //c保存n/2只后的商
}
a=a+1；由于二进制数第一位一定是1，而且在循环中并没有统计这个1，所以需要另外加上。

追问

但是那个n十分的大，是5*10^7的那么大，那么我们肯定不能一个一个去求出每一个数的二进制数了。

追答

如果不能一个一个算，你就需要先推导出一个能够快速算出A类数个数的公式，然后根据这个公式编程。
具体的方法我也不太清楚，我觉得大概可以用排列组合的思想，比如
1010011这个数小于这个数的二进制数有0XXXXXX 100XXXX 101000X 1010010（其中X表示可以是1可以是0的位）。可以看出，只要找出这些条件的排列组合中的符合A类数定义的数，就能找出所有的A类数。也就是从右往左，只要看到1，就把1替换为0，1后面的位数替换为X，就找出了所有的排列组合。然后从这些排列组合中就比较容易找出A类数。但是第一个排列组合有点特殊因为可能会出现00XXXXX的组合，这就需要你与其他的排列组合区分。具体的你再想想。