无忧公主编程挑战003

happy886rr

　　无忧公主说这是超难题，所谓丑数，就是不能被2，3，5以外的其他素数整除的数。1，2，3，4，5，6，8，9，10，12，15是最前面的11个丑数。找出第1500个丑数。
　　百度一下，才知道，原来此题被诸如谷歌、微软、西门子等多家知名IT公司作为面试必考题目。个别博客更是贴出长达几十行的代码来解决该问题。看得我一头雾水。自认跟数颇有缘的我，经过一番推敲，发现一个捷径，怎么就没人想到啊！
　　好吧，直接说思路。丑数不就是只能被２、3、5整除的数吗,那么这个数一定能表示成为几个2乘几个3乘几个5。这不就是丑数的生成公式吗！即丑数Ugly=(2^a)*(3^b)*(5^c)。看着好眼熟，还可以等价成四维空间的立体的质量，看来我抽象能力太好了，毕竟经常想象四维空间的样子。直接四维空间求质度。其实for循环就足够用的，把a、b、c各循环30次，30*30*30将会产生27000个丑数，一排序，打印第1500个完事。但是能省就省是我喜欢做的事，取对数，变乘法为加法。循环步数估值lg3*b=lg2*30；lg5*c=lg2*30.好吧，看来b需要循环19次，c只需13次，省得真不多。不过运行速度给力啊，0.06秒，还是N年前的破赛扬。

1. # Python解无忧公主编程挑战003
   
2. print("第1500个丑数是",end=" ")
   
3. U=[]
   
4. U.append(1) #顶位
   
5. for a in range(0,30):
   
6.         for b in range(0,19):
   
7.                 for c in range(0,13):
   
8.                         Ugly_Num=(2**a)*(3**b)*(5**c)
   
9.                         U.append(Ugly_Num)
   
10. R=sorted(U);print(R[1500])

复制代码

这么快就解决问题了，真搞不明白网上其他人为何会写几十行去解决问题。

虫子樱桃

数学差的人表示看不明白

CrLf

思路很赞，不过感觉指数运算花的时间太多了，空间换时间应能压缩到0.01秒以下

happy886rr

回复 3# CrLf
最好的解法是用图论，三叉树，1分叉为2、3、5，每个2、3、5再分叉。只要遍历第1000个节点就行。