题目描述：
-
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
- 输入：
-
输入包括一个整数N(1<=N<=1500)。
- 输出：
-
可能有多组测试数据，对于每组数据，
输出第N个丑数。
- 样例输入：
- 样例输出：
解题思路：
最简单的思路是，从1到大数，每个数都检测一遍是否是丑数，检测方法可以考虑
int ugly(int number){
if(number% == ){
return ugly(number/);
}else if(number% == ){
return ugly(number/);
}else if(number% == ){
return ugly(number/);
}else
return number==?true:false;
}
可是这种思路，会浪费大量的时间，最后就会超时。
我们考虑一个数组，数组存储的是当前的丑数，以后的每个丑数，都是用之前的数组的元素相乘的来的。接下来就是如何得到后面的丑数并保证它是有序的。
可以想到，数组的第一个元素是1,1与2 3 5分别相乘，可以得到三个值，这三个值里面最小的，肯定就是下一个丑数的最大值，接着max2的下标后移，继续比较。
void mkUglyNumber(){
gArr[top++] = ;
int *max2 = gArr;
int *max3 = gArr;
int *max5 = gArr;
while(top < ){
int min = getMin(*max2*,*max3*,*max5*);
gArr[top] = min;
while(*max2* <= gArr[top])
++max2;
while(*max3* <= gArr[top])
++max3;
while(*max5* <= gArr[top])
++max5;
++top;
}
}
比如，当前的数组元素只是1，那么与2 3 5 相乘得到2 3 5，显然得到的最小值是2。数组元素变为1 2。
下标这回变为2 1 1，继续与2 3 5相乘，得到4 3 5，找出其中最小的，再放进数组，元素变为1 2 3。
继续，直到找到1500个丑数之后，每次进行读取丑数即可。
全部代码：
#include <stdio.h>
#define MAXSIZE 1500
void mkUglyNumber();
int getMin(int max2,int max3,int max5);
int gArr[MAXSIZE];
int top;
int main(){
int n;
top = ;
mkUglyNumber();
while(scanf("%d",&n)!=EOF && n>= && n<=){
printf("%d\n",gArr[n-]);
}
return ;
}
void mkUglyNumber(){
gArr[top++] = ;
int *max2 = gArr;
int *max3 = gArr;
int *max5 = gArr;
while(top < ){
int min = getMin(*max2*,*max3*,*max5*);
gArr[top] = min;
while(*max2* <= gArr[top])
++max2;
while(*max3* <= gArr[top])
++max3;
while(*max5* <= gArr[top])
++max5;
++top;
}
}
int getMin(int max2,int max3,int max5){
int min = max2<max3?max2:max3;
return min<max5?min:max5;
}
/**************************************************************
Problem: 1214
User: xhalo
Language: C
Result: Accepted
Time:10 ms
Memory:920 kb
****************************************************************/