2010年1月14日 星期四

第一次儲備選手選拔試卷第七題

Ugly number的定義為:該數之質因數必須為2,3,5的組合(Ugly number的質因數可分解為2^x * 3^y * 5^z ,其中x,y,z為正整數)。當x,y,z皆=0時,為第一個Ugly number,其值為1。
例:1,2,3,4,5,6,8,9,10,12,15,這些就是前11個Ugly number。
請從指定目錄"in.txt"讀取一數字N,求出第N個Ugly number,輸出至指定目錄"out.txt"。

輸入範例:15

輸出範例:24

3 則留言:

  1. 小提示:
    這個醜數,其實算法和質數也是類似。
    先試寫找出第幾個質數的程式後,
    和質數不同的是:
    質數在2到本身減1之間,沒有因數。
    醜數是找到因數後,再看是不是非2,3,5而已。

    回覆刪除
  2. Private Sub Form_Activate()
    Open App.Path & "\in.txt" For Input As #1
    Input #1, x
    ans = 0
    For i = 1 To 9999
    N = i
    For j = 2 To 5
    If N Mod j = 0 Then
    N = N / j
    j = 1
    End If
    If j = 3 Then j = j + 1
    If j = 5 And N = 1 Then ans = ans + 1
    Next j
    If ans = x Then
    Open App.Path & "/out.txt" For Output As #2
    Print #2, i
    Close #2
    Exit For
    End If
    Next i
    Close #1
    End Sub

    回覆刪除
  3. Public Sub Form_Load()
    Dim ans As Long
    Dim an As String
    Me.Hide
    Open App.Path & "/in.txt" For Input As #1
    Open App.Path & "/out.txt" For Output As #2
    Input #1, x
    k = 1: kk = 1
    Do Until kk = x + 1
    s = k
    Do
    m = 0
    If s Mod 2 = 0 Then s = s \ 2: m = m + 1
    If s Mod 3 = 0 Then s = s \ 3: m = m + 1
    If s Mod 5 = 0 Then s = s \ 5: m = m + 1
    Loop Until m = 0
    If s = 1 Then
    kk = kk + 1
    If x = (kk - 1) Then Print #2, k
    End If
    k = k + 1

    Loop
    Close #2
    Close #1
    End
    End Sub

    11分5X秒

    回覆刪除