摘录


题目:我们把只包含因子
2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。
分析:这是一道在网络上广为流传的面试题,据说google曾经采用过这道题。
所谓一个数m是另一个数n的因子,是指n能被m整除,也就是n % m == 0。根据丑数的定义,丑数只能被2、3和5整除。也就是说如果一个数如果它能被2整除,我们把它连续除以2;如果能被3整除,就连续除以3;如果能被5整除,就除以连续5。如果最后我们得到的是1,那么这个数就是丑数,否则不是。
基于前面的分析,我们可以写出如下的函数来判断一个数是不是丑数:
bool IsUgly(int number)
{
    while(number % 2 == 0)
        number /= 2;
    while(number % 3 == 0)
        number /= 3;
    while(number % 5 == 0)
        number /= 5;
    return (number == 1) ? true : false;
}
接下来,我们只需要按顺序判断每一个整数是不是丑数,即:
int GetUglyNumber_Solution1(int index)
{
    if(index <= 0)
        return 0;
    int number = 0;
    int uglyFound = 0;
    while(uglyFound < index)
    {
        ++number;
        if(IsUgly(number))
        {
            ++uglyFound;
        }
    }
    return number;
}

点评

够丑的~

原文

点击这里查看原文

其它

本帖内容由21QA云收藏工具自动生成,欢迎使用。

系统消息 若觉得内容不错,请点击左上角的"赞"图标,以优化网站的内容呈现。 另外,请及时验证注册邮箱,否则收不到21QA发出的红包。 官方Q群:250203055

提问于 23 四月 '15, 21:01

%E8%B7%AF%E4%BA%BA%E7%94%B2's gravatar image

路人甲
131266457557

第一个回答这个问题
切换预览

你可以使用订阅来关注这个问题

使用邮箱订阅:

登录后可以订阅更新

使用RSS订阅:

回答

回答与评论

文字标记基础知识

  • *斜体文字* 或者 _斜体文字_
  • **黑体文字** 或者 __黑体文字__
  • 插入超链接: [链接文字](http://url.com/ "标题")
  • 插入图片: ![alt](/path/img.jpg "标题")
  • 编号排列: 1. Foo 2. Bar
  • 输入换行符前请输入两个空格(即:空空回车),仅敲回车无效。
  • 支持基本的HTML标签的使用

问题的标签:

×576
×33

问题发表于: 23 四月 '15, 21:01

问题被查看: 338 次

最近更新: 23 四月 '15, 21:01

powered by O*S*Q*A

粤ICP备14040061号-1