标题: [原创代码] 无忧公主编程挑战003 [打印本页]
作者: happy886rr 时间: 2016-4-12 18:09 标题: 无忧公主编程挑战003
本帖最后由 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-13 10:58
数学差的人表示看不明白
作者: CrLf 时间: 2016-4-13 12:57
思路很赞，不过感觉指数运算花的时间太多了，空间换时间应能压缩到0.01秒以下
作者: happy886rr 时间: 2016-4-13 14:55
回复 3# CrLf
最好的解法是用图论，三叉树，1分叉为2、3、5，每个2、3、5再分叉。只要遍历第1000个节点就行。
| 欢迎光临 批处理之家 (http://bathome.net./) |
Powered by Discuz! 7.2 |