丑数

作者: 鲨漠里的鱼 | 来源:发表于2017-10-14 15:39 被阅读0次

    把只包含因子2,3和5的数称作丑数(ugly number)。例如6,8都是丑数,但14不是,因为它包含了因子7。习惯上我们把1作为第一个丑数。求按从小到大的顺序的第N个丑数。

    int GetUglyNumber_Solution(int index) {

        if (index<0) return 0;

            if (index==1) return 1;

            vector<int>k(index);

            k[0]=1;

            int num2=0,num3=0,num5=0;

            for(int i=1;i<index;++i)

                {

                k[i]=min(k[num2]*2,min(k[num3]*3,k[num5]*5));

                if(k[i]==k[num2]*2) num2++;

                if(k[i]==k[num3]*3) num3++;

                if(k[i]==k[num5]*5) num5++;

            }

            return k[index-1];

        }

    注解:建立一个大小为N的数组或容器,前十个丑数是1,2,3,4,5,6,8,9,10,12。先从1的2倍,3倍,5倍中选一个最小数,作为第二个丑数,然后从1的3倍,5倍,2的2倍中选择最小的数作为第三个丑数,然后从1的5倍,2的2倍,3的2倍中选一个最小的数作为下一个丑数......

    每一个丑数都可以分解成一个或多个丑数的乘积。也可以看做之前已经存好的丑数的2倍或3倍或5倍的数。怎么选取前面哪一个数的2倍,哪一个数的3倍,哪一个数的5倍是关键。

    从最小的丑数开始,记录他的2倍,3倍,5倍都是要取的,而且只能取一次,当某个丑数的2倍取过之后,就更新改丑数,更新为下一个比它大的丑数;当某个丑数的3倍取过之后,就更新丑数为下一个比他大的丑数;当某个丑数的5倍取过之后,就更新丑数为下一个比它大的丑数。更新之后,记录的仍为丑数的相对应的倍数。依次更新数组或容器,最后返回第N和元素即可。

    相关文章

      网友评论

          本文标题:丑数

          本文链接:https://www.haomeiwen.com/subject/rwaxuxtx.html