算法题——第1000000个数是多少？

原题在“两道TB面试题”文章中。今日在本文中，就个人的理解再阐述一遍。

　　题目1：有一个数列，它由3个数列复合而成，并升序排列。三个数列分别是2的n次，3的n次，5的n次，0≤n<∞。给出前几项：1,2,3,4,5,8,9,16,25,27………………即2⁰(3⁰, 5⁰) , 2¹, 3¹, 2², 5¹, 2³, 3², 4², 5², 3³。问你如何快速得到第1000000个数的值。
问题2：有一个数列，它由3个数列复合而成，并升序排列。三个数列分别是2的n次，3的n次，5的n次，1≤n<∞。给出前几项：2,3,4,5,8,9,16,25,27………………即2¹, 3¹, 2², 5¹, 2³, 3², 4², 5², 3³。问你如何快速得到第Index个数的值。

　　可以看出，问题2和问题1是同一个问题。只不过，问题2把问题1的第一个数去除而已。我们先从问题2解决。

　　不失一般性，假设在前Index个数中，2的n次的有X个，3的n次有Y个，5的n次有Z个。则X+Y+Z=Index
假设第Index个数是2^X。（也可能是3^Y和5^Z，后面再分类讨论）

　　可知　　　　　　　　3^Y＜2^X

　　两边取对数　　　　　lg3^Y＜lg2^X
Ylg3＜Xlg2

　　　　　　　　　　　　Y＜Xlg2/lg3

　　　　　　　　　　　　Y＜Xlog₃2

　　因为Y是整数　　　　Y=[Xlog₃2]

　　同理可知　　　　　  Z=[Xlog₅2]

　　则　　　　　　　　　Index=X+Y+Z=X+[Xlog₃2]+[Xlog₅2]<X+Xlog₃2+Xlog₅2

　　又因为　　　　　　Xlog₃2<Y+1、Xlog₅2<Z+1

　　所以　　　　　　　　Index<X+Xlog₃2+Xlog₅2<Index+2

　　所以　　　　　　　　Index/(1+log₃2+log₅2)<X<(Index+2)/(1+log₃2+log₅2)

　　由上式可知，如果第Index个数是2^X。则X满足Index/(1+log₃2+log₅2)<X<(Index+2)/(1+log₃2+log₅2)

　　再根据X的值计算Y和Z的值。若X+Y+Z=Index。说明第Index个数是2^X。若不满足说明第Index个数不是2^X。

　　同理，可以假设第Index个数是3^Y或5^Z。推理就不写了。

　　把代码贴于下方，用的是VB2005

　　Public Class clsFind
Private Shared LOG23 As Double = Math.Log(3, 2)
Private Shared LOG25 As Double = Math.Log(5, 2)
Private Shared LOG32 As Double = Math.Log(2, 3)
Private Shared LOG35 As Double = Math.Log(5, 3)
Private Shared LOG52 As Double = Math.Log(2, 5)
Private Shared LOG53 As Double = Math.Log(3, 5)

　　　　Private Shared S2 As Double = 1 + LOG32 + LOG52
Private Shared S3 As Double = 1 + LOG23 + LOG53
Private Shared S5 As Double = 1 + LOG25 + LOG35

　　　　Public Shared Function FindNumber(ByVal Index As Integer) As Long
Dim X1 As Integer, X2 As Integer

　　　　　　Dim i As Integer

　　　　　　'Index -= 1

　　　　　　'假设第Index个数是2^X

　　　　　　X1 = -Int(-Index / S2)
X2 = Int((Index + 2) / S2)

　　　　　　For i = X1 To X2
If i + Int(i * LOG32) + Int(i * LOG52) = Index Then Return i * 10 + 2
Next

　　　　　　'假设第Index个数是3^Y

　　　　　　X1 = -Int(-Index / S3)
X2 = Int((Index + 2) / S3)
For i = X1 To X2
If i + Int(i * LOG23) + Int(i * LOG53) = Index Then Return i * 10 + 3
Next

　　　　　　'假设第Index个数是5^Z

　　　　　　X1 = -Int(-Index / S5)
X2 = Int((Index + 2) / S5)
For i = X1 To X2
If i + Int(i * LOG25) + Int(i * LOG35) = Index Then Return i * 10 + 5
Next
       

　　　　　　Return -1
End Function
　　End Class

注意： 该函数返回的值还要再处理一下。

　　例如：clsFind.FindNumber(1000)得到的值是2095。表示第1000个数是5²⁰⁹

　　这个函数是解决问题2的。而问题2就和问题1相差一个数。故如果是问题1，将Index-=1这句话取消注释就可以了。

　　问题1的第1000000个数是3³⁰⁶⁰³⁸。

    本文转自万仓一黍博客园博客，原文链接：http://www.cnblogs.com/grenet/archive/2011/04/20/2021827.html，如需转载请自行联系原作者