经典c面试题 -凯发app官方网站

分析：
按丑数定义，一个丑数只包含2、3、5这三个因数，因此，如果一个数是丑数，那么我们循环除以2、3、5直到最后肯定能够除尽。那么判断一个数是否是丑数就比较容易了（采用碾除法）：
static int isuglynum(unsigned long long key)
{
     unsigned long long num = key;
     if (num == 0)
         return 0;

     while(num % 2 == 0)
         num /= 2;

     while(num % 3 == 0)
         num /= 3;

     while (num %5 == 0)
         num /= 5;

      return (num == 1);
}

在此基础上，按最通常的做法就是依次遍历正整数，验证每个数是否是丑数，然后统计验证成功的个数：

void printuglynumbers(int cnt)
{
        unsigned long long key = 1;
        int cntsum = 0;

        while (cntsum <= cnt)
        {
                if (isuglynum(key))
                {
                        cntsum ;
                        if (cntsum % 10 == 0)
                        {
                                printf("\t-->%d\n", cntsum);
                        }
                        printf("%lld ", key);
                }
                key ;
        }
}

上面实现把前@cnt个丑数打印出来。

分析到此，此题已经解了。so easy？ 如果有人和笔者一样编译运行过，那么会发现一个问题：打印前1500个会花分几秒钟的时间，打印前2000个会花费1分钟左右的时间，打印3000个笔者已经没有耐心等待它运行完毕......不错，上面的实现在@cnt较大时效率很低！

原因很简单：不难想象，丑数在数轴上是离散分布的，越是到大数部分，丑数分布越是分散。举个例子，假如a,b,c是数轴上三个相邻的丑数，那么由a,b,c的为基础的“发展出来”的新的丑数为【2a，2b,2c,3a,3b,3c,5a,5b,5c】，即使不考虑2c，3b，5a可能存在重复，就下界2a和上界5c所确定的域已经较之前a和c确定的域宽了很多（实际上是不平滑的指数级增长）。

重新考虑丑数的定义，可以推导出：一个丑数，必然是[2,3,5]这三个因子的其中一个，进过一步或多步因子[2,3,5]相乘得来的。比如10，就是因子2进过一步乘因子5得来的。我们把【2,3,5】作为基本集合，那么在此基础上经过一步因子乘操作可得集合（实际上【2,3,5】可以看做是【1】经过一次乘操作得来的，所以我们把【2,3,5】定为1阶集合，在此基础上做因子乘得2阶集合）：
2阶：【4,6,10,  6,9,15,  10,15,25】，排序出重复后为【4,6,9,10,15,25】
在2阶的基础上，进过一步因子相乘操作可得3阶集合：
3阶：【8,12,18,20,30,50,   12,18,27,30,45,75,   20,30,45,50,75,125】，排序、去重复后为【8,12,18,20,27,30,35,45,50,75,125】
......
k阶：是（k-1）阶集合中每个元素依次乘2,3,5后的集合经过排序去重，k阶元素都可以分解为（k 1）个因子相乘。

为了对比我们重列一下前几阶的丑数：
0阶：【1】
1阶：【2,3,5】
2阶：【4,6,9,10,15,25】
3阶：【8,12,18,20,27,30,35,45,50,75,125】

通过观察分析，可以发现以下几个特征：
1. 低阶和高阶之间不会有重复的元素（因为每一阶因子个数不一样）；
2. 低阶和高阶元素之间大小存在交叉，且交叉部分是高阶的较小的部分；
3. 每一阶集合域的下界是2^(k)，上界是5^(k)；
4. 如果，第i阶集合的上界小于第j阶集合的下界，那么第i阶集合与第j阶集合必然不会出现元素大小交叉。

回到我们题目，要求找出第n个丑数，假设我们已经依次求解k阶集合，且每一阶集合元素个数为len[k]，如果这k阶集合满足：
        （1）前i阶集合元素个数累加和大于等于n；
       （2）i阶集合的上界小于（k 1）阶集合的下界（即（k 1) 阶和i阶不存在交叉，那么在前k阶集合中，包含了由i阶集合上界所确定的范围【1，2，...，5^i】的所有丑数）
那么，我们将前k阶集合进行归并排列，sum（len[0]....len[i]）长度的数组所包含的丑数一定是连续递增的，且个数大于等于n。于是我们从该数组中取出第n个即可。

根据分析，不难写出实现代码：
unsigned long long printuglynumbersv2(int cnt)
{
    unsigned long long *prcd;
    unsigned long long *pstep;
    unsigned long long *pass;
    unsigned long long *ptemp;

    int idxr;
    int idxs;
    int step = 0;
    int stepi = 0;  // 记录第i阶时满足 sum（len[i]) >= cnt
    int steplen; 

    // 用于归并合并
    int idx2,idx3,idx5,index;
    unsigned long long key2, key3, key5, keys,keyr; 

    int i,j;

    int lencnt = 0;
    unsigned long int memsizebyte = 0;

    prcd = (unsigned long long*)calloc(cnt 1, sizeof(unsigned long long));
    pstep = (unsigned long long*)calloc(cnt 1, sizeof(unsigned long long));
    pass = (unsigned long long*)calloc(cnt 1, sizeof(unsigned long long));

    memsizebyte = sizeof(unsigned long long ) * (cnt 1);

    prcd[0] = 1;
    lencnt = 1;

    pstep[0] = 1;
    steplen = 1;

    while(lencnt < cnt || (stepi != 0 && power(2, step) < power(5, stepi)))
    {
        // 遍历上一阶集合元素，归并排列下一阶集合
        idxs = 0;
        idx2 = idx3 = idx5 = 0;
        pstep[steplen] = pstep[steplen -1] * 30; // add a max determinant, as the end flag

        while( (idx2 < steplen || idx3 < steplen || idx5 < steplen) && idxs < cnt)
        {
            key2 = pstep[idx2] * 2;
            key3 = pstep[idx3] * 3;
            key5 = pstep[idx5] * 5;

            if (key2 <= key3 && key2 <= key5)
            {
                pass[idxs ] = key2;
                idx2 ;

                if (key2 == key3)
                    idx3 ;

                if (key2== key5)
                    idx5 ;
            }
            if (key3 <= key5 && key3 < key2)
            {
                pass[idxs ] = key3;
                idx3 ;

                if (key3 == key5)
                    idx5 ;
            }


            if (key5 < key2 && key5 < key3)
            {
                pass[idxs ] = key5;
                idx5 ;
            }
        }

        // 新一阶统计完毕，交换指针
        steplen = idxs;
        ptemp = pass;
        pass = pstep;
        pstep = ptemp;
        bzero(pass, memsizebyte);
        step ;

        // 合并新生成的一阶元素到记录中
        idxr = idxs = 0;
        index = 0;
        while( (idxr < lencnt || idxs < steplen) && index < cnt)
        {
            if (idxr == lencnt)
            {
                while(idxs < steplen)
                    pass[index ] = pstep[idxs ];

                break;
            }
            if (idxs == steplen)
            {
                while(idxr < lencnt)
                    pass[index ] = prcd[idxr ];

                break;
            }

            if (prcd[idxr] < pstep[idxs])
            {
                pass[index ] = prcd[idxr ];
            }
            else // 没有相等的
            {
                pass[index ] = pstep[idxs ];
            }
        }

        // 新一阶集合合并完毕，交换指针
        lencnt = index;
        if (lencnt >= cnt)
        {
            if (!stepi)
            {
                stepi = step;
                printf("mr.i : %d\n", stepi);
            }
        }

        ptemp = pass;
        pass = prcd;
        prcd = ptemp;

        bzero(pass, memsizebyte);
    }

    //
    for(i = 0; i< cnt; i )
    {
        if (i !=0 && i % 10 == 0)
            printf("\t--%d\n", i);

        printf("%lld ", prcd[i]);
    }
    printf("\t--%d\n", i);

    keyr = prcd[cnt-1];
    free(prcd);
    free(pass);
    free(pstep);
    return keyr;
}

经测试，打印前4000个丑数瞬间完成！