大佬教程收集整理的这篇文章主要介绍了Swift学习——寻找丑数,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
参考自:http://www.cnblogs.com/python27/archive/2011/11/24/2261550.html
题目:我们把只包含因子2、3和5的数称作丑数(Ugly number)。例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。
分析:寻找一个数是不是满足某种数(质数,水仙数)等,最简单的方法就是遍历,对于任意一个丑数必定可以写成2^m*3^n*5^p,因而对于一个丑数,只含有2,3,5因子,也就意味着该数number%2==0;number%3==0;number%5==0,如果一个数能被2整除,我们就连续除以2;能被3整除,我们就连续除以3;能被5整除,我们就连续除以5;如果最后得到1,则该数是素数,否则是丑数。
代码如下:
func isUglynumber(number:int)->Bool
{
var number1 = number
while number1 % 2 == 0
{
number1 /= 2
}
while number1 % 3 == 0
{
number1 /= 3
}
while number1 % 5 == 0
{
number1 /= 5
}
if number1 == 1
{
return true
}
else{
return false
}
}
func getUglynumber1(index:int)->Int{
if index <= 0{
return 0
}
var number:Int = 0
var count:Int = 0
while(count < indeX)
{
++number
if isUglynumber(number){
++count
}
}
return number
}
上面计算中主要的不足在于,逐一遍历,这样对于不是丑数的数的判断会造成大量的时间浪费,如果能够根据已经计算好的丑数,计算出下一个丑数就可以避免这种情况,实现从丑数到丑数的高效算法,根据定义可知,后面的丑数肯定是前面已知丑数乘以2,3,5得到的。
我们假设一个数组中已经有若干丑数,并且这些丑数是按顺序排列的,我们把现有的最大丑数记为max,则下一个丑数肯定是前面丑数乘以2,3,5得到的。不妨考虑乘以2得到的情况,我们把数组中的每一个数都乘以2,由于原数组是有序的,因为乘以2后也是有序递增的,这样必然存在一个数M2,它前面的每一个数都是小于等于max,而@L_502_14@m2在内的后面的数都是大于max的,因为我们还是要保持递增顺序,所以我们取第一个大于max的数M2。同理对于乘以3的情况,可以取第一个大于max的数M3,对于乘以5的情况,可以取第一个大于max的数M5。
最终下一个丑数取:min{M2,M3,M5}即可
(相当于将之前得到的丑数放到一个数组array里,然后分别将数组array里的丑数乘以2,将其与数组array的最后一个丑数b相比,一旦大于b,就称其为上述中的M2,同理可得M3,M5)
代码如下:
func getUglynumber2(index:int)->Int{
var uglyNum:Int = 1
if index <= 0{
return 0
}
var uglyArray:Array<Int> = [1]
var m2Array:Array<Int> = Array()
var m3Array:Array<Int> = Array()
var m5Array:Array<Int> = Array()
while uglyArray.count < index{
var m2:Int = 0
var m3:Int = 0
var m5:Int = 0
m2Array = uglyArray
m3Array = uglyArray
m5Array = uglyArray
for (index,value) in enumerate(m2Array){
m2ArraY[index] = value*2
if m2ArraY[index] > uglyArray.last{
m2 = m2ArraY[index]
break
}
}
for (index,value) in enumerate(m3Array){
m3ArraY[index] = value*3
if m3ArraY[index] > uglyArray.last{
m3 = m3ArraY[index]
break
}
}
for (index,value) in enumerate(m5Array){
m5ArraY[index] = value*5
if m5ArraY[index] > uglyArray.last{
m5 = m5ArraY[index]
break
}
}
uglyNum = min(m2,m3,m5)
uglyArray.append(uglyNum)
}
return uglyNum
}
在此感谢http://www.cnblogs.com/python27/的每日一算法的分享
以上是大佬教程为你收集整理的Swift学习——寻找丑数全部内容,希望文章能够帮你解决Swift学习——寻找丑数所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。