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

　　题目1：有一个数列，它由3个数列复合而成，并升序排列。三个数列分别是2的n次，3的n次，5的n次，0≤n<∞。给出前几项：1,2,3,4,5,8,9,16,25,27………………即20(30, 50) , 21, 31, 22, 51, 23, 32, 42, 52, 33。问你如何快速得到第1000000个数的值。

　　问题2：有一个数列，它由3个数列复合而成，并升序排列。三个数列分别是2的n次，3的n次，5的n次，1≤n<∞。给出前几项：2,3,4,5,8,9,16,25,27………………即21, 31, 22, 51, 23, 32, 42, 52, 33。问你如何快速得到第Index个数的值。

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

　　不失一般性，假设在前Index个数中，2的n次的有X个，3的n次有Y个，5的n次有Z个。则X+Y+Z=Index

　　假设第Index个数是2X。（也可能是3Y和5Z，后面再分类讨论）

　　可知　　　　　　　　3Y＜2X

　　两边取对数　　　　　lg3Y＜lg2X

　　　　　　　　　　　　Ylg3＜Xlg2

　　　　　　　　　　　　Y＜Xlg2/lg3

　　　　　　　　　　　　Y＜Xlog32

　　因为Y是整数　　　　Y=[Xlog32]

　　同理可知　　　　　  Z=[Xlog52]

　　则　　　　　　　　　Index=X+Y+Z=X+[Xlog32]+[Xlog52]<X+Xlog32+Xlog52

　　又因为　　　　　　Xlog32<Y+1、Xlog52<Z+1

　　所以　　　　　　　　Index<X+Xlog32+Xlog52<Index+2

　　所以　　　　　　　　Index/(1+log32+log52)<X<(Index+2)/(1+log32+log52)

　　

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

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

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

　　把代码贴于下方，用的是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)

　　　　　　　　If i + Int(i * LOG23) + Int(i * LOG53) = Index Then Return i * 10 + 3

　　　　　　'假设第Index个数是5^Z

　　　　　　X1 = -Int(-Index / S5)

　　　　　　X2 = Int((Index + 2) / S5)

　　　　　　　　If i + Int(i * LOG25) + Int(i * LOG35) = Index Then Return i * 10 + 5

　　　　　　Return -1

　　　　End Function

　　End Class

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

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

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

　　问题1的第1000000个数是3306038。