Afutseng's Blog

　　燈怪被關在阿拉丁神燈裡已經好幾十萬年了，這使得燈怪的脾氣變得有點奇怪。他不再對所有釋放他離開神燈的人都一視同仁地給三個願望，反而要求得到願望前必須正確回答他所問的問題，如果回答不出來，就要代替燈怪被關在神燈裡。他的問題是一個數列問題，題目如下：

　　數列A(n)為一組最簡分數所形成的數列，這些最簡分數的值都大於0小於1，且分母小於等於n，同時數列中的數值依由大到小的方式排序之。例如：
A(3) = 2/3, 1/2, 1/3
A(4) = 3/4, 2/3, 1/2, 1/3, 1/4
A(5) = 4/5, 3/4, 2/3, 3/5, 1/2, 2/5, 1/3, 1/4, 1/5
　　燈怪要問的問題是這個數列是由幾個最簡分數所組成的？數列中倒數第n個最簡分數為何？請寫一個方程式回答燈怪的問題。

輸入資料(Input Data)

輸入檔第一行有一個正整數n，n最少為2，最多為70。

請由螢幕印出兩行資料，說明如下：
1.第一行列出數列共有幾個最簡分數。
2.第二行列出倒數第n個最簡分數，如果最簡分數個數小於n，則請列出最大數字(即第一個最簡分數)。

範例一

輸入
4
輸出
5
2/3

範例二

輸入
5
輸出
9
1/2

Option Explicit

'自訂型態
Private Type myFraction
   mathValue As Single  '分數實際的數學數值(小數)
   exprStr As String    '分數字串(觀看用)
End Type

Private Sub Command1_Click()
   Dim i%, j%, n%, cnt%, iniDeno%, iniNumer%
   Dim aFraction(100) As myFraction
  
   n = 4         ' n
  
   If n < 2 Or n > 70 Then Exit Sub
  
   cnt = 0
   iniDeno = n   '分母
   iniNumer = n  '分子

   Do
      '分子遞減
      iniNumer = iniNumer - 1
     
      '分母子都是偶數則直接跳過
      If (iniDeno Mod 2 <> 0) Or (iniNumer Mod 2 <> 0) Then
     
         If (iniDeno Mod iniNumer = 0) And (iniNumer > 1) Then
        
         Else
            '只處理最簡分數
            cnt = cnt + 1
            aFraction(cnt).mathValue = iniNumer / iniDeno
            aFraction(cnt).exprStr = iniNumer & "/" & iniDeno
           
            'Debug.Print aFraction(cnt).exprStr
           
            '分子遞減至 1 後, 將分母減1, 並使分子與分母相等
            If iniNumer = 1 Then
               iniDeno = iniDeno - 1
               iniNumer = iniDeno
            End If
           
         End If
      End If
     
      If iniDeno <= 1 And iniNumer <= 1 Then Exit Do
   Loop
  
   '印出數列有幾個最簡分數
   Print cnt
  
   '數列遞減排序
   For i = 1 To cnt - 1
      For j = i + 1 To cnt
         If aFraction(i).mathValue < aFraction(j).mathValue Then
            Dim temp As myFraction
            temp = aFraction(i)
            aFraction(i) = aFraction(j)
            aFraction(j) = temp
         End If
      Next
   Next

   If cnt < n Then
      Print aFraction(1).exprStr
   Else
      '印出倒數第 n 個最簡分數
      Print aFraction(cnt - n + 1).exprStr
   End If

End Sub