首页 > 代码库 > 九度-题目1214:丑数
九度-题目1214:丑数
http://ac.jobdu.com/problem.php?pid=1214
- 题目描述:
-
把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
- 输入:
-
输入包括一个整数N(1<=N<=1500)。
- 输出:
-
可能有多组测试数据,对于每组数据,
输出第N个丑数。
- 样例输入:
-
3
- 样例输出:
-
3
一开始的想法是递增遍历足够多的数字,得到长度为1500的数组。数组中每个元素对应一个丑数。
这将产生问题:数组中靠后的一些元素是无法遍历得到的,或者说非常不有效。
因此换一种方法:数组中的后一个元素必然是前面某个元素的2倍/3倍/5倍。每次只要获得对应的元素即可。#include <iostream> using namespace std; int min3(int a, int b, int c){ int min=(a<b)?a:b; if(min>c) return c; else return min; } int getUglyNum(int index){ if(index<=0) return 0; int a[index]; a[0]=1; int idx1=0; int idx2=0; int idx3=0; for(int i=1; i<index; i++){ int min=min3(a[idx1]*2, a[idx2]*3, a[idx3]*5); a[i]=min; if(min==a[idx1]*2) idx1++; if(min==a[idx2]*3) idx2++; if(min==a[idx3]*5) idx3++; } return a[index-1]; } int main(){ int n; while(cin>>n){ int Ugly=getUglyNum(n); cout << Ugly << endl; } return 0; }
九度-题目1214:丑数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。