本帖最后由 happy886rr 于 2016-4-12 18:31 编辑
无忧公主说这是超难题，所谓丑数，就是不能被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年前的破赛扬。- # Python解无忧公主编程挑战003
- print("第1500个丑数是",end=" ")
- U=[]
- U.append(1) #顶位
- for a in range(0,30):
- for b in range(0,19):
- for c in range(0,13):
- Ugly_Num=(2**a)*(3**b)*(5**c)
- U.append(Ugly_Num)
- R=sorted(U);print(R[1500])
这么快就解决问题了，真搞不明白网上其他人为何会写几十行去解决问题。 | 
发表于 2016-4-12 18:09
| 
发表于 2016-4-13 12:57
| 