学步园

题目：我们把只包含因子
2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。
分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。
所谓一个数m是另一个数n的因子，是指n能被m整除，也就是n % m == 0。根据丑数的定义，丑数只能被2、3和5整除。也就是说如果一个数如果它能被2整除，我们把它连续除以2；如果能被3整除，就连续除以3；如果能被5整除，就除以连续5。如果最后我们得到的是1，那么这个数就是丑数，否则不是。

//============================================================================<br /> // Name : 100题之寻找丑数.cpp<br /> // Author :<br /> // Version :<br /> // Copyright : Your copyright notice<br /> // Description : Hello World in C++, Ansi-style<br /> //============================================================================<br /> #include <iostream><br /> #include<vector><br /> using namespace std;<br /> vector<long int>v;<br /> const int MAX=10000;<br /> bool Isugle(int word)<br /> {<br /> while(word%2==0)<br /> word/=2;<br /> while(word%3==0)<br /> word/=3;<br /> while(word%5==0)<br /> word/=5;<br /> return (word==1)?true:false;<br /> }<br /> int computeugly2(int index)<br /> {<br /> int word=1;<br /> for(int i=1;i<=index;)<br /> {<br /> if(Isugle(word))<br /> {<br /> i++;<br /> }<br /> word++;<br /> }<br /> return word-1;<br /> }<br /> int computeugly(int index)<br /> {<br /> if(index<0)<br /> return -1;<br /> v.push_back(1);<br /> if(index==1)<br /> return v[index-1];<br /> int number=1;<br /> int min2=MAX;<br /> int min3=MAX;<br /> int min5=MAX;<br /> int min;<br /> while(number<=index)<br /> {<br /> int i;<br /> for( i=0;i<=number-1&&v[i]*2<=v[number-1];i++)<br /> ;<br /> min2=v[i]*2;<br /> for( i=0;i<=number-1&&v[i]*3<=v[number-1];i++)<br /> ;<br /> min3=v[i]*3;<br /> for( i=0;i<=number-1&&v[i]*5<=v[number-1];i++)<br /> ;<br /> min5=v[i]*5;<br /> min=min2<min3?min2:min3;<br /> min=min<min5?min:min5;<br /> v.push_back(min);<br /> number++;<br /> }<br /> return v[index-1];<br /> }<br /> int main() {<br /> cout << computeugly(1500)<< endl;<br /> cout<<computeugly2(1500)<<endl;<br /> return 0;<br /> }<br />