题目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]
又因为 Xlog32
由上式可知，如果第Index个数是2X。则X满足Index/(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。
最新评论