Ugly Numbers
Time Limit:1000MS Memory Limit:32768K
Description:
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... shows the first 11 ugly numbers. By convention, 1 is included. Write a program to find and print the n’th ugly number.
Input:
Every integer number (≤1500)describing position of ugly number from 1.If integer number is 0,the process should ended. Maybe there are 10000 integer numbers on input data.
Output:
Every integer given should output a line as shown below, The <n>th ugly number is <number>. with <n> replaced by the integer number and <number> replaced by the number computed.
Sample Input:
5 16
Sample Output:
The 5th ugly number is 5.The 16th ugly number is 25.
Source:
ZJUT1089
本题最开始的想法是使用set容器,将1插入容器后,利用循环,将容器中的每一位从小到大分别乘以2,3,5,利用set容器的特性去重并自动排序,
虽然代码Accept,但很容易看出,这种算法有大量的数据重复,且需要比题目给出的数目1500循环更多次数,极大地增加了算法的时间复杂度,因此应寻找一种更简便的算法,思路如下:
定义一个集合,该集合中有元素1,如果x在集合中,并且y是x的下一个丑数,那么x*2,x*3,x*5也在集合中,其它数不再集合中,这三个数中必定是2x最小,因此首先放入数组中,而此时*2最小的应该是x的下一个丑数y*2,此时应该找出y*2,x*3,x*5中最小的数放入数组,以此类推,具体操作如下:
1
*2
*3
*5
选出乘积最小的,加入到结果集中,相应指针右移
1 2
*3 *2
*5
选出乘积最小的,加入到结果集中,相应指针右移
1 2 3
*5 *2
*3
选出乘积最小的,加入到结果集中,相应指针右移
1 2 3 4
*5 *3 *2
选出乘积最小的,加入到结果集中,相应指针右移
1 2 3 4
*3 *2
*5
以此类推,直到获得1500的结果集,实现代码如下:
原文地址(本人博客):http://lanfei.sinaapp.com/2012/03/242.html
欢迎访问交流。
分享到:
相关推荐
ACM_算法模板集史上最完整收藏版223页全免费版.pd
杭电hdu acm资料所用杭电的acm题
noi试题和解析,对于参加acm非常有帮助
浙江大学ACM题解JU_ACM_All_Anwer,里面一本非常好的chm电子书,浙大的所有ACM题及题解都在了,对学习ACM的朋友非常的好~还等什么呢?
ACM_基础篇
Pascal acm_timus_ural_1148.pas
Pascal acm_timus_ural_1099.pas
ACM__ICPC__重要补充知识.doc
ACM,竞赛题目,我已经在上面测试过了,可以用,题目是ARGUS,希望大家可以喜欢,花了长时间才弄好的
ACM_竞赛试题,对于那些参加各种比赛,特别是ACM大赛的人会有很大帮助
ACM的重要PPT资料,对初学者非常有益处
一些关于ACM算法的资料,包括5种算法的详细讲解和ACM题型分类以及一些基础题目
ACM_计算几何_源码.pdf
ACM_String.
ACM_贪心.
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.
ACM_Java 速成,重点讲述了JAVA的基本运用和大数类,以及JAVA中进制转化函数,对ACMer学习JAVA大有帮助
The 2014 ACM-ICPC Asia Beijing Regional Contest
ACM_算法模板集史上最完整收藏版223页 ACM_算法模板集史上最完整收藏版 ACM_算法模板集史上最完整收藏版
2004ACM国际大学生程序设计决赛题目