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

凯发app官方网站-凯发k8官网下载客户端中心 | | 凯发app官方网站-凯发k8官网下载客户端中心
  • 博客访问: 752906
  • 博文数量: 144
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1150
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-17 14:32
个人简介

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

文章分类

全部博文(144)

相关博文
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·

分类: 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个丑数瞬间完成!

阅读(3517) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
")); function link(t){ var href= $(t).attr('href'); href ="?url=" encodeuricomponent(location.href); $(t).attr('href',href); //setcookie("returnouturl", location.href, 60, "/"); }
网站地图