算法題——第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。