【转载】丑数humble numbers

转载地址：http://blog.csdn.net/qwerty_xk/article/details/12749961

题：只有2 3 5 这三个因子的数，求第1500个   设1为第一个丑数，求第1500个丑数

解法：

1 简单的暴力搜索，对每个数进行因子判别，直到搜到第1500个

评价：耗时 不可取

2 将得到的数保存在一个数组中，按从小到大的顺序进行存放，对该数组前面的数分别乘以2 3 5，每乘一个因子，先乘到刚好大于该数组最大的值，然后break

进行下一个因子相乘  ，得到三个数，比较得到这三个数中的最小值，push进当前数组最后。

这里可以用三个下标来分别保存2 3 5 在数组中开始相乘的起始下标位置，就避免了每次都从数组的开头开始相乘，每次更新的依据为：上面三个数哪个最小，对应的那个因子

的下标进行更新

    #include<iostream>  
    #include<vector>  
    using namespace std;  
      
    int min3(int a,int b,int c)  
    {  
        int tmp=(a<b?a:b);  
        return (tmp<c?tmp:c);  
    }  
    int main()  
    {  
        vector<int> uglyNum;  
        uglyNum.push_back(1);  //初始只有1在数组中  
        int t2=0,t3=0,t5=0; //每个因子开始相乘的下标位置  
        int i,j,k;  
        while(uglyNum.size()!=1500)  
        {  
            int m2,m3,m5;  //保存每个因子得到的值  
            for(i=t2;i<uglyNum.size();i++)  
                if(2*uglyNum[i]>uglyNum.back())  
                {  
                    m2=2*uglyNum[i];  
                    break;  
                }  
            for(j=t3;j<uglyNum.size();j++)  
                if(3*uglyNum[j]>uglyNum.back())  
                {  
                    m3=3*uglyNum[j];  
                    break;  
                }  
            for(k=t5;k<uglyNum.size();k++)  
                if(5*uglyNum[k]>uglyNum.back())  
                {  
                    m5=5*uglyNum[k];  
                    break;  
                }  
            int tmp = min3(m2,m3,m5);  
            uglyNum.push_back(tmp);  
            if(tmp==m2)  
                t2=i+1;  //下标位置进行更新  
            if(tmp==m3)  
                t3=j+1;  
            if(tmp==m5)  
                t5=k+1;  
        }  
        for(int i=0;i<uglyNum.size();i++)  
            cout<<uglyNum[i]<<" ";  
        cout<<endl;  
        return 0;  
    }  

 运行得到的值为 ： 859963392