使用遞迴查詢兩個給定數字的最大公約數的Haskell程式

---

在Haskell中，我們可以使用遞迴以及gcd函式和尾遞迴來查詢兩個給定數字的最大公約數。在第一個和第二個示例中，我們將使用基本情況（gcd a 0 = a）和遞迴情況（gcd a b = gcd b (a `mod` b)），在第三個示例中，我們將使用尾遞迴函式。

在以下示例中，我們定義了一個gcd函式，它接受兩個Int引數a和b。該函式使用模式匹配來處理兩種情況：

• 如果b為0，則函式返回a，因為a和0的最大公約數是a。

• 如果b不為0，則函式遞迴呼叫自身，引數為b和a模b。

演算法

• 步驟1 - 匯入Prelude庫以隱藏gcd函式。

• 步驟2 - 定義使用者自定義的gcd函式，包含基本情況和遞迴情況，如下所示：

• 對於示例1和2：

gcd a 0 = a
gcd a b = gcd b (a `mod` b).

• 對於示例3：

| a < b     = gcd b a
| b == 0    = a
| otherwise = gcd b (a `mod` b).

• 步驟3 - 程式執行將從main函式開始。main()函式控制整個程式。它被寫成main = do。在main函式中，我們定義了兩個變數a和b，其值分別為36和63。最後，我們將gcd a b的結果列印到控制檯。

• 步驟4 - 變數“a”和“b”被初始化。它們將儲存需要計算最大公約數的數字。

• 步驟5 - 呼叫函式後，使用‘print’函式將給定兩個數字的最大公約數結果列印到控制檯。

示例1

在這個例子中，使用gcd函式查詢兩個數字a和b的最大公約數，以計算這兩個數字的最大公約數。

import Prelude hiding(gcd)
gcd :: Int -> Int -> Int
gcd a 0 = a
gcd a b = gcd b (a `mod` b)

main :: IO ()
main = do
   let a = 36
   let b = 63
   print (gcd a b)

輸出

9

示例2

在這個例子中，使用減法和除法運算來計算最大公約數。這種方法背後的思想是利用gcd(a, b) = gcd(b, a - b * floor(a / b))這一事實，並不斷從a中減去b * floor(a / b)，直到b變為0，此時a將是最大公約數。

import Prelude hiding(gcd)
gcd :: Int -> Int -> Int
gcd a 0 = a
gcd a b = gcd b (a - (a `div` b) * b)

main :: IO ()
main = do
   let a = 36
   let b = 63
   print (gcd a b)

輸出

9

示例3

在這個例子中，使用gcd函式的尾遞迴方法查詢兩個數字a和b的最大公約數，以計算這兩個數字的最大公約數。

import Prelude hiding(gcd)
gcd :: Int -> Int -> Int
gcd a b
   | a < b     = gcd b a
   | b == 0    = a
   | otherwise = gcd b (a `mod` b)

main :: IO ()
main = do
   let a = 36
   let b = 63
   print (gcd a b)

輸出

9

結論

在Haskell中，gcd函式用於計算兩個數字的最大公約數。實現gcd函式的方法有很多，其中最常見的一種方法是使用歐幾里得演算法，該演算法指出兩個數字a和b的最大公約數等於b和a模b的最大公約數。它也可以使用遞迴實現。