Chinaunix首页 | 论坛 | 博客
  • 博客访问: 423361
  • 博文数量: 134
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1039
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-17 14:32
个人简介

小公司研发总监,即当司令也当兵!

文章分类

全部博文(134)

分类: LINUX

2016-08-01 14:29:18

题目:我们把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。

分析:
按丑数定义,一个丑数只包含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个丑数瞬间完成!

阅读(1598) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册