net网站建设/北京公司排名seo
题目：我们把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数，但14不是，因为它包含因子7。
习惯上我们把1当做是第一个丑数。 求按从小到大的顺序的第1500个丑数。
分析：这是一道在网络上广为流传的面试题，据说Google曾经采用过这道题。
方法一：从小到大的遍历，这是我们最容易想到的方法了吧。不过这种方法很耗时间，用下面的代码查找第1500个丑数，Win7+VS2010用了33.067秒，效率很低。
#include <iostream>
#include <ctime>
using namespace std;long findUglyNum(long willfindnum)
{long findednum = 0;long currentnum = 1, tmp;while(true){tmp = currentnum;while(!(tmp%2))tmp /= 2;while(!(tmp%3))tmp /= 3;while(!(tmp%5))tmp /= 5;if(tmp == 1)++findednum;if(findednum == willfindnum)break;else ++currentnum;}return currentnum;
}int main()
{time_t begin,end; begin=clock(); cout<<findUglyNum(1500)<<endl;end=clock(); cout<<"runtime: "<<double(end-begin)/CLOCKS_PER_SEC<<endl;return 0;
}
方法二：直接生成Ugly Numbers
接下来我们换一种思路来分析这个问题，试图只计算丑数，而不在非丑数的整数上花费时间。根据丑数的定义，丑数应该是另一个丑数乘以2、3或者5的结果（1除外）。因此我们可以创建一个数组，里面的数字是排好序的丑数。里面的每一个丑数是前面的丑数乘以2、3或者5得到的。这种思路的关键在于怎样确保数组里面的丑数是排好序的。我们假设数组中已经有若干个丑数，排好序后存在数组中。我们把现有的最大丑数记做M。现在我们来生成下一个丑数，该丑数肯定是前面某一个丑数乘以2、3或者5的结果。我们首先考虑把已有的每个丑数乘以2。在乘以2的时候，能得到若干个结果小于或等于M的。由于我们是按照顺序生成的，小于或者等于M肯定已经在数组中了，我们不需再次考虑；我们还会得到若干个大于M的结果，但我们只需要第一个大于M的结果，因为我们希望丑数是按从小到大顺序生成的，其他更大的结果我们以后再说。我们把得到的第一个乘以2后大于M的结果，记为M2。同样我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M3和M5。那么下一个丑数应该是M2、M3和M5三个数的最小者。前面我们分析的时候，提到把已有的每个丑数分别都乘以2、3和5，事实上是不需要的，因为已有的丑数是按顺序存在数组中的。对乘以2而言，肯定存在某一个丑数T2，排在它之前的每一个丑数乘以2得到的结果都会小于已有最大的丑数，在它之后的每一个丑数乘以2得到的结果都会太大。我们只需要记下这个丑数的位置，同时每次生成新的丑数的时候，去更新这个T2。对乘以3和5而言，存在着同样的T3和T5。
int Min(int number1, int number2, int number3)
{int min = (number1 < number2) ? number1 : number2;min = (min < number3) ? min : number3;return min;
}
int findUglyNum2(int index)
{int *pUglyNumbers = new int[index];pUglyNumbers[0] = 1;int nextUglyIndex = 1;int *pMultiply2 = pUglyNumbers;int *pMultiply3 = pUglyNumbers;int *pMultiply5 = pUglyNumbers;while(nextUglyIndex < index){int min = Min(*pMultiply2*2, *pMultiply3*3,*pMultiply5*5);pUglyNumbers[nextUglyIndex] = min;while(*pMultiply2*2 <= pUglyNumbers[nextUglyIndex])++pMultiply2;while(*pMultiply3*3 <= pUglyNumbers[nextUglyIndex])++pMultiply3;while(*pMultiply5*5 <= pUglyNumbers[nextUglyIndex])++pMultiply5;++nextUglyIndex;}int ugly = pUglyNumbers[nextUglyIndex - 1];delete[] pUglyNumbers;return ugly;
}int main()
{time_t begin2,end2; begin2=clock(); cout<<findUglyNum2(1500)<<endl;end2=clock(); cout<<"runtime: "<<double(end2-begin2)/CLOCKS_PER_SEC<<endl;return 0;
}运行结果：第1500个丑数：859,963,392， 第1690个丑数2,123,366,400，第1691个丑数int就越界了。
int表示的最大整数是2,147,483,647，由cout<<(std::numeric_limits<int>::max)()<<endl;可知。
方法三：使用STL set
int main()
{long long n=1500,cur;set<long long>s;s.insert(1);cur = *s.begin();while( --n ) { s.insert( cur * 2 );s.insert( cur * 3 );s.insert( cur * 5 );cur = *s.erase( s.begin() );}cout<<cur<<endl;return 0;
}运行时间是0.046秒，只有5行代码。
方法四：这种方法没看懂，但是运行结果是正确的。注释掉check()速度还不错。来自http://www.iteye.com/topic/832545之方法五
#include <iostream>
using namespace std; int nums5(int val)
{ int n=0 ; while (val >= 5) { n++ ; val /= 5; } return n;
}
int nums35(int val)
{ int n=0 ; while (val >= 3) { n += 1+nums5(val); val /= 3; } return n;
}
//基于因数分解求出val以内有多少个丑数（不包含1)
int nums235(int val)
{ int n=0 ; while (val >= 2) { n += 1+nums35(val); val /= 2 ; } return n;
}
//用二分法查找第n个丑数
//对于X，如果X以内的丑数个数是n,而X-1以内的丑数个数是n-1，那么X就是第n个丑数
int numOfIndex(int n)
{ if(n == 1) return 1; n--; int val1 = 1; int nums1 = 0; int val2 = 2; int nums2 = nums235(val2); //nums2为val2的因数个数 while( nums2 < n ) { val1 = val2; nums1 = nums2; val2 = val1*2; nums2 = nums235(val2); } if( nums1 == n ) return val1; if( nums2 == n ) return val2; while(true) { long mid = (val1 + val2)/2; int nums = nums235(mid); if(val2 == mid+1 && nums == n-1 && nums2==n) return val2; if(mid == val1+1 && nums1 == n-1 && nums==n) return mid; if(nums >= n) { val2 = mid; nums2 = nums; } else { val1 = mid; nums1 = nums; } }
}
int check(int val)
{ long v = val; while( v%2==0 ) v/=2; while( v%3==0 ) v/=3; while( v%5==0 ) v/=5; if( v != 1 ) cout << " v is not an ugly number! " << endl; return val;
} void calc(int n)
{ long val = numOfIndex(n); cout << n << " : " << val << endl;; check(val);
} int main(int argc ,char *argv[])
{ int Number; cout << "Please input a number : " ; cin >> Number ; calc(Number); return 0;
}