2012年5月14日 星期一

最大公約數

利用歐基里德輾轉相除法寫一個程式。輸入兩個正整數,輸出其最大公約數。輸入數值的大小限制於3到1000之間。

輸入說明:每一列由二個數字所組成,為一組測試資料。每個數字與數字間的區隔為一個空白符號,當為0 0時表示結束。(請參照輸入範例)
輸入範例:in.txt
78 64
26 39
0 0

輸出說明:對於每組測試資料,輸出最大公約數。(請參照輸出範例)
輸出範例:out.txt
2
13

4 則留言:

  1. Dim x%, y%
    Private Sub Form_Load()
    Me.Hide
    Open App.Path & "\in.txt" For Input As #1
    Open App.Path & "\out.txt" For Output As #2
    Do
    Input #1, x, y
    If x <> 0 And y <> 0 Then Call abc(x, y)
    Loop Until x = 0
    Close
    Close
    End
    End Sub
    Sub abc(a, b)
    If a = b Then
    Print #2, a
    Else
    If a > b Then Call abc(a - b, b)
    If b > a Then Call abc(a, b - a)
    End If
    End Sub

    回覆刪除
  2. Private Sub Form_Load()
    Me.Hide
    Open App.Path & "\in.txt" For Input As #1
    Open App.Path & "\out.txt" For Output As #2
    Do
    Input #1, X1, X2
    If X1 = X2 And X1 = 0 Then Exit Do
    r = X1 Mod X2
    If r <> 0 Then
    Y1 = X1
    Y2 = X2
    Do Until r = 0
    Y1 = Y2
    Y2 = r
    r = Y1 Mod Y2
    Loop
    End If
    Print #2, Y2
    Loop Until X1 = 0
    Close #2
    Close #1
    End
    End Sub

    回覆刪除
  3. 兩位程式正確 遞迴會更好做

    回覆刪除
  4. Private Sub Form_Load()
    Me.Hide
    Open App.Path & "\in.txt" For Input As #1
    Open App.Path & "\out.txt" For Output As #2
    Do
    Input #1, x, y
    If x = 0 And y = 0 Then Exit Do
    Call g(Val(x), Val(y))
    Loop
    Close #2
    Close #1
    End
    End Sub

    Sub g(a, b)
    t = a Mod b
    a = b: b = t
    If t <> 0 Then
    Call g(a, b)
    Else
    Print #2, a
    End If
    End Sub

    回覆刪除