[quote]哎，我的第一题的错误还是没有找出来，如果我的想法是正确的话，那效率应该是比较高的。
我的想法是：对于整数m,先转换成2进制，（位数为Wei_Num）,则1到m所有的A类数是这样构成的:
 (1):位数比Wei_Num少的所有A类数；
 (2):位数为Wei_Num的A类数.
对于(1),判断从3位到Wei_Num中，每一种位数所存在的A类数，例如位数个数是5,则由5位二进制数组成的A类数个数为:C(3,4)+C(4,4)。
对于(2)，首先判断m本身是否是A类数,设置标记C_0=0,C_1=1(用于存储当前有的0,1的个数)，然后从第2位开始（高到低），遍历每一位，如果当前位为0,则C_0++;
否则，将当前位置为0，C_0,组合求出余下位有多少种A类数的可能。
例如:10010001,找到第一个1时，C_0=2;C_1=1;然后C_0=C_0+1;变成1000****;则由它构成的A类数个数为:C(2,4)+C(3,4)+C(4,4);即是:10000011,10000110,10001100.10001010,10001001,10000110, 10000001,10000010, 10000100,10001000,100000000；计算完成后再复为1,C_0--,C_1++。

程序在16383之前都正确(14位),到16384(15)时就错了,郁闷!大家看看是不是算法有漏洞。


int solve(int m)
{
    int count=0;
    int i,j,k,temp,C_0,C_1;;
    long temp1,temp2;
    int Label[33];
    int Wei_Num=0,Lef_Num;
    while(m)
    {
        Label[Wei_Num++]=m%2;
        m/=2;
    }

    for(i=0;i<Wei_Num/2;i++)
    {
        temp=Label[i];
        Label[i]=Label[Wei_Num-1-i];
        Label[Wei_Num-1-i]=temp;
    }

    for(i=3;i<Wei_Num;i++)
    {
        Lef_Num=i-1;
        for(j=i/2+1;j<=Lef_Num;j++)
        {
            temp1=1;
            temp2=1;
            for(k=j;k>=1;k--)
            {
                temp1*=(Lef_Num-k+1);
                temp2*=k;
            }
            count+=temp1/temp2;
        }
    }
    
    C_0=0;
    C_1=0;
    for(i=0;i<Wei_Num;i++)
    {

        if(Label[i]==0)C_0++;
        else C_1++;
    }
    if(C_0>C_1)count++;
    C_0=0;
    C_1=1;
    i=1;

    while(i<Wei_Num)
    {  
        if(Label[i]==0)C_0++;        
        else if(Label[i]==1)
        {  
            Lef_Num=Wei_Num-i-1;
            C_0++;
    
            if(C_0>=Wei_Num/2+1)
            {
                temp1=1;
                for(j=1;j<=Lef_Num;j++)
                    temp1*=2;                    
                count+=temp1;
            }
            else
            {
                for(j=Wei_Num/2+1-C_0;j<=Lef_Num;j++)
                {
                    temp1=1;
                    temp2=1;
                    for(k=j;k>=1;k--)
                    {
                        temp1*=(Lef_Num-k+1);
                        temp2*=k;
                    }
                    count+=temp1/temp2;
                }
            }

            C_0--;
            C_1++;
            
        }
        i++;
    }
    return count;
}
[/quote]
思路同上。你在求组合数的时候，大数相乘，可能会越界，因此，需要特殊处理，比如用组合公式。

我也是用组合数,不过我是把要用到的组合数先算出来存起来

第二题， wangfangbob  小黑骑DK ，能讲解一下你们的思路吗？？？

  

设函数A(n) = 2n + 1, 函数B(n) = 4n + 5
集合Q中除了1以外的所有的数,都是对1连续求有穷次函数A或B的值所得
比如:3是求一次A,7是求两次A,9是求一次B
这样我们可以对所有的数编码,求一次A就记一个0,求一次B就记1
那么:

1 3  7 9  15 17 19  31   33  35  36 41   63   65   67   71   73  79   81   
  0 00 1 000 01 10 0000 001 010 100 11 00000 0001 0010 0100 011 1000 101

 83   127   129   131   135   137  143   145  147  159   161  163  167
110 000000 00001 00010 00100 0011 01000 0101 0110 10000 1001 1010 1100

169   255     259    263    271   275    287   291   295
111 0000000 000001 000010 000100 00011 001000 00101 00110 .....
我发现了一个有趣的规律,编码全是0的数是分别是第2,3,5,8,13,21,33....! 于是,
我们把这些数分组,每两个编码全是0的数之间的所有数是一组,这样每组数的个数分别
是1,2,3,5,8,13,21,33....., 然后重新来看:

1 | 3 |  7 9 |  15 17 19 |  31   33  35  36 41 |   63   65   67   71   73  
  | 0 | 00 1 | 000 01 10 | 0000 001 010 100 11 | 00000 0001 0010 0100 011

 79   81  83 |   127   129   131   135   137  143   145  147  159   161
1000 101 110 | 000000 00001 00010 00100 0011 01000 0101 0110 10000 1001

 163  167 169 |   255     259    263    271   275    287   291   295
1010 1100 111 | 0000000 000001 000010 000100 00011 001000 00101 00110 .....

又一个规律出现了:每组数的前一部分是前一组数的每个数的编码前面加一个0,后一部
分是,再前一组数的每一个数的编码前面加一个1! 
这个规律已经足以通过递归将算法复杂度降到O(logn)的级别了

iAkiak第一题的算法最优?求组合数理论上应该是hash表最快呀
不知道lz对算法评价的标准是什么

慢慢研究楼上的思路~

思路真新颖，受教！！

我是把1当成n来做的(n>=1)。即求a*n+b. 第一项看成n+0. n前面的系数是1.
先看n的系数()里的数字代表个数：
1(1) -> 2 4
2(1) -> 4 8
再然后4有多少个呢 ？ 2个。 前两项各一个。
4(2) -> 8 16
.... 应该发现规律了吧， 就是菲波那切数列。1,1,2,3....
这是n 前面系数的求法.

加数b的求法就复杂一些。把n的系数分层，相同的在一层。
我是根据2层之间的关系确定最终加数的，把每一层加数保留下来。2p+1 2p+3 (p是上一层的元素) 
0....n系数为1,第0层
1....系数为2，第1层
1 3
1 3 1
1 3 1 1 3 这个1 3序列很有规律。 1生出1和3， 3只生出1。（可以证明的）
它的规律还不只这些， 它的前面所有项必然和前一层的相同，并且后面的项必然是上上一层的所有项（这个我不知道怎么证明）

由这个规律可以把每一层是1还是3确定下来， 直到第1层。

我是新手；说的不对的话请大家多指点。
我是刚看到这道题；刚才编了一下第一道题；感觉这道题很简单阿
没必要搞得那么复杂；
以下是我的简单C代码：

#include  <stdio.h>
#include  <math.h>
#include  <time.h>

int solve(int m)
{
    int i=0;
    int num=0;
    int numA=0;
    int k1, k2;

    for(i=4;i<=m;i++)
    {
        num = i;
        k1=0;
        k2=0;
        while(num > 0)
        {
            if((num %2) == 0)
            {
                k1++;
            }
            else{
                k2++;
            }
            num = num/2;            
        }
        if(k1> k2){
            numA++;
        }
    }
    return numA;
}




void main()
{
    clock_t time; 
    int i,num;
    time = clock();
      for(i=1;i<1000000;i++)
    {
        num=solve(100);
    }
    time = clock() - time;
    printf("time = %d ms\n",time);
    printf("num = %d \n",num);
}

还有关于那个对同一个数，进行重复测试其运行时间的；
这个我觉得没有太大必要，要想实际运行速度快，实用的话
最好还得建个HASH链表，用来存储已经处理过的m及其对应的A类个数；
这样速度才是最快的；但是在实际中假如这个函数很少调用的话；那根本就没有必要
只有在多次重复调用的情况下，最好还是需要建立哈希链表

两道题都有O(logn)的算法