`
kmplayer
  • 浏览: 508841 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

寻找丑数

阅读更多
1,题意:
把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。
习惯上我们把1当做是第一个丑数。
返回第n个丑数.

2,分析: //类似于筛法寻找素数
创建一个数组,里面的数字是排好序的丑数。里面的每一个丑数是前面的丑数乘以2、3或者5得到的。
我们假设数组中已经有若干个丑数,排好序后存在数组中。现在我们来生成下一个丑数,该丑数肯定是前面某一个丑数乘以2、3或者5的结果。

从1开始,每个数分别乘以一次2,3,5,会贡献3个丑数.
贡献后,对应的index2或index3或index5就右移一位.

3,实现代码:
#include <iostream>
using namespace std;

int mymin(int a, int b, int c)
{
    int temp = (a < b ? a : b);
    return (temp < c ? temp : c);
}
int FindUgly(int n) //返回第n个丑数
{
    int* ugly = new int[n];
    ugly[0] = 1;
    int index2 = 0;
    int index3 = 0;
    int index5 = 0;
    int index = 1;
    while (index < n)
    {
        int val = mymin(ugly[index2]*2, ugly[index3]*3, ugly[index5]*5);
        if (val == ugly[index2]*2) //看哪个被选中
            ++index2;
        if (val == ugly[index3]*3)
            ++index3;
        if (val == ugly[index5]*5)
            ++index5;
        ugly[index++] = val;
    }
    for (int i = 0; i < n; ++i)
        cout << ugly[i] << endl;
    int result = ugly[n-1];
    delete[] ugly;
    return result;
}

int main()
{
    FindUgly(100);
    return 0;
}
分享到:
评论

相关推荐

    经典数据算术----丑数

    丑数,又称“好看数”或“优美数”,在数学领域中是指仅包含质因数2、3和5的正整数。这类数的特点是它们可以...通过对这些知识点的理解和应用,我们可以有效地解决寻找一定范围内丑数的问题,例如在边界值1500以内。

    丑数c语言丑数c语言丑数c语言

    理解丑数的概念和C语言实现丑数判断及寻找第n个丑数的算法,有助于提升编程能力和算法思维。在实际应用中,这样的问题可能会出现在数据结构、算法或编程竞赛题目中,熟练掌握丑数相关的知识对于提升编程能力大有裨益...

    丑数实验报告C语言.docx

    4. **寻找前n个丑数**: - 在`main`函数中,使用一个循环结构,从1开始逐个判断每个数是否为丑数。 - 用一个计数器`count`记录已找到的丑数个数,直到找到第1500个丑数为止。 - 如果当前数`num`是丑数,就输出它...

    丑数(最小堆)1

    本文将深入探讨如何使用最小堆来解决寻找第n个丑数的问题。 首先,我们需要定义丑数的概念。一个数如果仅包含质因子2、3和5,那么它就是丑数。例如,1、2、3、4、5、6、8、9、10和12都是前10个丑数。丑数序列的特点...

    《算法设计与分析》课程笔记(无水印文字可选中版) by 浅若清风cyf

    《算法设计与分析》课程笔记主要涵盖了算法设计与分析的基础知识,包括算法的重要性和五大特性,以及具体的算法实例,如辗转相除法求最大公约数和寻找丑数的方法。以下是这些知识点的详细说明: 1. **算法的重要性*...

    数据结构与算法题解

    - 寻找丑数。 - **PlusOne** - 数组表示的数字加1。 **5. 链表(LinkedList)** - **RemoveDuplicatesfromSortedList** - 删除排序链表中的重复元素。 - **RemoveDuplicatesfromSortedListII** - 删除排序链表中...

    丑数c语言,两种解法,详细过程

    这种方法虽然直观,但效率较低,因为需要对每一个数进行判断,尤其是在寻找较大的丑数时,会浪费大量时间。 ```c int ugly(int number){ while (number % 2 == 0) number /= 2; while (number % 3 == 0) number /...

    世界500强面试题.pdf

    1.2.2. 下排每个数都是先前上排那十个数在下排出现的次数 ..........................11 1.2.3. 设计包含 min 函数的栈 ...................................................................... 14 1.2.4. 求子...

    leetcode跳跃-learnning_algorithm:算法学习

    getNumber--寻找丑数 所谓丑数,就是只含有2、3或5这3个素因子的自然数。如果认为1是一个合法的丑数,那么1就是第一个丑数 leetcode 动态规划 五、最长回文子串 十、正则表达式匹配--动态规划 六十二、不同路径 六十...

    求第1500个只有2,3,5因子的数

    根据给定文件的信息,我们可以总结出以下相关的IT知识点: ...综上所述,这段代码通过简洁而高效的逻辑实现了寻找第1500个丑数的功能。通过动态规划的思想和合理的数据结构选择,使得程序运行效率高且易于理解。

    [宫水三叶的刷题日记]:多路归并1

    初始将1放入堆中,每次从堆中取出最小的丑数x,然后将其与2、3、5相乘得到新的丑数,再将这些新丑数加入堆中。重复此过程,直到堆中的元素个数等于n。这种方法能够确保始终优先处理最小的丑数,从而达到找到第n个丑...

    usaco3.1解题报告1

    【USACO/humble】此题是关于“丑数”的问题,丑数是指仅包含特定素因子的正整数。题目给出一个素数集合S,求集合S生成的丑数集合中的第N个数。解决这个问题可以采用动态规划的方法,维护一个数组hum,依次计算由S中...

    华南农业大学计算智能期末复习.docx

    代码中的`It is not ugly number`程序生成并存储了前4000个丑数,然后根据用户输入查询特定位置的丑数。这里使用了动态规划和排序技术,动态规划的核心是避免重复计算,提高效率。在计算过程中,每次生成新的丑数时...

    算法合集解析_275.pdf

    数学问题包括计算阶乘、斐波那契数列、逆波兰表达式的计算、丑数(只包含质因数2、3、5的数)的生成、2的幂次的计算等。处理数学问题时,通常需要对数学规律有深刻理解,如动态规划或递归的思想。 海量数据处理则是...

    戳气球leetcode-leetcode-solution:实践

    寻找第n个丑数(动态规划) 寻找唯一重复数字(Floyd判圈法) 链表环路检测(Floyd判圈法) 链表按位求和 超级丑数(动态规划,这次是k个质因子) 戳气球(动态规划,找出状态转移方程最关键) 按字典序去重(利用进栈出栈) 盛...

    《算法最优解(第一版)》剑指Offer题解校招求职刷题必备.docx

    13. **输出第n个丑数**:丑数是指仅包含质因数2、3、5的数,可以通过动态规划或三个指针维护三个质因数状态来计算。 14. **数字在排序数组中出现的次数**:在有序数组中查找元素的出现次数,可以直接双指针法解决。...

    剑指Offer---Java版代码

    8. 回溯算法:如丑数,二叉搜索树与双向链表等。 9. 字符串操作:包括字符串的排列,表示数值的字符串等。 10. 高级数据结构:例如复杂链表的复制,平衡二叉树,构建乘积数组等。 11. 序列化与反序列化:如序列化...

    前端大厂最新面试题-heap.docx

    21. **丑数 II**:丑数是指只包含质因数2、3、5的正整数,可能需要用到动态规划。 22. **根据字符出现频率排序**:字符串处理和排序算法的结合,可以使用计数排序或基数排序。 23. **重构字符串**:字符串操作和...

    leetcode跳跃-LeetCode:力码

    丑数 009 Easy fizz buzz 013 Easy 字符串查找 014 Easy 二分查找 028 Easy 搜索二维矩阵 031 Medium 数组划分 046 Easy 主元素(贪心) 050 Easy 数组剔除元素后的乘积 055 Medium 比较字符串 056 Medium 两数之和 ...

Global site tag (gtag.js) - Google Analytics