162-求第N个丑数的值

我会带着你远行 2022-10-24 13:27 307阅读 0赞

## 什么是丑数？ ##

把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。 习惯上我们把1当做是第一个丑数。

前20个丑数为:1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36

## 求第n个丑数是多少 ##

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    int GetUglyNumber(int index)
    {
        
        //第N个丑数
        //丑数思想   2 3 5为因子    丑数j = 丑数i*(2或者3或者5得到)
        if (index < 7)
            return index;
        vector<int> ivec(index, 0);
        ivec[0] = 1;
        int t2 = 0, t3 = 0, t5 = 0;
        for (int i = 1; i < index; ++i)
        {
        
    		ivec[i] = min(min(ivec[t2] * 2, ivec[t3] * 3), ivec[t5] * 5);
            if (ivec[i] == ivec[t2] * 2)
                t2++;
            if (ivec[i] == ivec[t3] * 3)
                t3++;
            if (ivec[i] == ivec[t5] * 5)
                t5++;
        }
        return ivec[index - 1];
    }
    
    int main()
    {
        
    	cout<<GetUglyNumber(10)<<endl;
    	return 0;
    }

**运行截图如下**  
![在这里插入图片描述][20210129214740168.png_pic_center]

[20210129214740168.png_pic_center]: /images/20221024/ded2346b86624dc79d653baa61d535bf.png

发表评论取消回复

表情：

评论列表（有 0 条评论，307人围观）

还没有评论，来说两句吧...

相关阅读

相关求N个数的最大值，最小值，和（C语言）

入格式第一行为整数 n，表示数的个数。第二行有 n 个数，为给定的 n 个数，每个数的绝对值都小于 10000。如输入： Entern:5 -159322 ...

末蓝、/ 2024年04月18日 14:54/ 0 赞/ 258 阅读

相关找到第n个数，

find the nth digit Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K

「爱情、让人受尽委屈。」/ 2024年02月18日 23:15/ 0 赞/ 130 阅读

相关 N33_丑数

题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到

た入场券/ 2023年08月17日 17:36/ 0 赞/ 171 阅读

相关寻找第n个丑数

寻找第n个丑数应用案例案例分析丑数的概念过程分析代码实现应用案例编写一个程序，找出第n个丑

骑猪看日落/ 2023年07月10日 14:27/ 0 赞/ 126 阅读

相关 83 - 找到第n个丑数

只包含2、3、5中的1个或多个因子的数称为丑数，要求按从小到大的顺序找到第n个丑数 ''' 2, 3, 5 6: 是丑数 14: 不是丑数，包含7 下一个丑数必定

电玩女神/ 2023年05月28日 05:26/ 0 赞/ 19 阅读

相关 C++程序设计：求n个数的最大值、最小值

【问题描述】求键盘上输入的n个整数的最大值、最小值。【输入形式】第一行输入正整数n 第二行输入n个整数【输出形式】输出最大值和最小值，使用空格

- 日理万妓/ 2023年03月06日 05:55/ 0 赞/ 122 阅读

相关 162-求第N个丑数的值

什么是丑数？把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。习惯上我们把1当做是第一个丑数。

我会带着你远行/ 2022年10月24日 13:27/ 0 赞/ 308 阅读

相关给定n个数，求n个数的两两异或和

给定n个数，求n个数的两两异或和 include <bits/stdc++> using namespace std; define ll long

悠悠/ 2022年08月30日 04:10/ 0 赞/ 359 阅读

相关求阶梯状数组的层数和第n行的第一个数和第n个数？

<?php header('content-type:text/html;charset=utf-8;'); $max_num

亦凉/ 2022年05月31日 12:09/ 0 赞/ 347 阅读

相关 JavaScript求n个数的最大值

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document</

╰+攻爆jí腚メ/ 2022年05月20日 02:57/ 0 赞/ 351 阅读