算法题——第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)
　　　　　　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个数是5209
　　
　　这个函数是解决问题2的。而问题2就和问题1相差一个数。故如果是问题1，将Index-=1这句话取消注释就可以了。
　　问题1的第1000000个数是3306038。
作者：万仓一黍

补充：综合编程 , 其他综合 ,