学步园

64.  寻找丑数。
题目：我们把只包含因子 2、3  和 5  的数称作丑数（Ugly Number）。例如 6、8  都是丑数，
但 14  不是，因为它包含因子 7。习惯上我们把 1  当做是第一个丑数。求按从小到大的顺序
的第 1500  个丑数。
分析：这是一道在网络上广为流传的面试题，据说 google  曾经采用过这道题。

/*
64.  寻找丑数。
题目：我们把只包含因子 2、3  和 5  的数称作丑数（Ugly Number）。例如 6、8  都是丑数，
但 14  不是，因为它包含因子 7。习惯上我们把 1  当做是第一个丑数。求按从小到大的顺序
的第 1500  个丑数。
分析：这是一道在网络上广为流传的面试题，据说 google  曾经采用过这道题。
*/
#include<iostream> 
#include<stdio.h>  
using namespace std;   
int ugly[2000];
     
int Min(int a, int b)   
{    
    return a<b?a:b;   
}  
 
void FindUgly(int n)
{   
    
    ugly[0]=1;   
    int index2 = 0;   
    int index3 = 0;   
    int index5 = 0;   
    int index = 1;   
    while (index<=n)   
    {   
        int val=Min(Min(ugly[index2]*2,ugly[index3]*3),ugly[index5]*5); //竞争产生下一个丑数   
        if (val==ugly[index2]*2) //将产生这个丑数的index*向后挪一位；  
            ++index2;   //这里不能用elseif，因为可能有两个最小值，这时都要挪动；
        if (val==ugly[index3]*3)   
            ++index3;   
        if (val==ugly[index5]*5)   
            ++index5;   
        ugly[index++]=val;   
    }   
}   
 
int main()   
{   
    int num=1;
    
    FindUgly(1500);
    while(1)
    {
    	printf("input the number(0 end): \n");
		scanf("%d", &num);
		if(num==0) break;
    	printf("%d \n",ugly[num]); 	
    }
    return 0;   
}