使用庫函式查詢最大公約數的Haskell程式

---

在 Haskell 中，我們將使用庫函式（如 gcd、div 函式和遞迴）來查詢最大公約數。在第一個示例中，我們將使用 gcd (a b) 函式，在第二個示例中，我們將使用 (a `div` b) 函式。在第三個示例中，我們將使用遞迴。

方法 1：使用 gcd 函式查詢最大公約數

在這種方法中，gcd 函式以兩個整數作為輸入，並返回這兩個數字的最大公約數。此函式在 Prelude 庫中定義。

演算法

• 步驟 1 − 程式執行將從 main 函式開始。main() 函式控制整個程式。它寫成 main = do。它呼叫 gcd 函式並傳入值，並打印出兩個數的最大公約數。

• 步驟 2 − 變數“a”和“b”被初始化。它將儲存要查詢其最大公約數的值。

• 步驟 3 − gcd 函式被呼叫為 gcd a b。

• 步驟 4 − 函式呼叫後，使用‘putStrLn’語句將結果的最大公約數值列印到控制檯。

示例 1

在這個示例中，我們將看到如何找到給定數字的最大公約數。這可以透過使用 gcd 函式來完成。

main :: IO ()
main = do
   let a = 5
   let b = 25
   let gcdVal = gcd a b
   putStrLn $ "The GCD of " ++ show a ++ " and " ++ show b ++ " is: " ++ show gcdVal

輸出

The GCD of 5 and 25 is: 5

方法 2：使用 div 函式查詢最大公約數

在這種方法中，div 函式重複地除以數字，直到餘數為 0，此時最大公約數等於最後一個非零商，並返回兩個數字的最大公約數。

演算法

• 步驟 1 − gcd’’’ 函式使用 div 函式定義為，

gcd''' a b
| b == 0    = a
| otherwise = gcd''' b (a `div` b).

• 步驟 2 − 程式執行將從 main 函式開始。main() 函式控制整個程式。它寫成 main = do。它呼叫 gcd’’’ 函式並傳入值，並打印出兩個數的最大公約數。

• 步驟 3 − 變數“a”和“b”被初始化。它將儲存要查詢其最大公約數的值。

• 步驟 4 − 函式呼叫後，使用‘putStrLn’語句將結果的最大公約數值列印到控制檯。

示例 1

在這個示例中，我們將看到如何找到給定數字的最大公約數。這可以透過使用 div 函式來完成。

gcd''' :: Integral a => a -> a -> a
gcd''' a b
   | b == 0    = a
   | otherwise = gcd''' b (a `div` b)

main :: IO ()
main = do
   let a = 5
   let b = 20
   let gcdVal = gcd''' a b
   putStrLn $ "The GCD of " ++ show a ++ " and " ++ show b ++ " is: " ++ show gcdVal

輸出

The GCD of 5 and 20 is: 20

方法 3：使用 mod 函式和遞迴查詢最大公約數

在這種方法中，遞迴用於重複應用模運算子，直到餘數為 0，此時最大公約數等於最後一個非零餘數，並返回兩個數字的最大公約數。

演算法

• 步驟 1 − gcd' 函式使用 mod 函式定義為，gcd' a b = gcd' b (a `mod` b)。

• 步驟 2 − 程式執行將從 main 函式開始。main() 函式控制整個程式。它寫成 main = do。它呼叫 gcd’ 函式並傳入值，並打印出兩個數的最大公約數。

• 步驟 3 − 變數“a”和“b”被初始化。它將儲存要查詢其最大公約數的值。

• 步驟 4 − 函式遞迴呼叫後，使用‘putStrLn’語句將結果的最大公約數值列印到控制檯。

示例 1

在這個示例中，我們將看到如何找到給定數字的最大公約數。這可以透過使用 mod 函式遞迴來完成。

gcd' :: Integral a => a -> a -> a
gcd' a 0 = a
gcd' a b = gcd' b (a `mod` b)

main :: IO ()
main = do
   let a = 5
   let b = 10
   let gcdVal = gcd' a b
   putStrLn $ "The GCD of " ++ show a ++ " and " ++ show b ++ " is: " ++ show gcdVal

輸出

The GCD of 5 and 10 is: 5

結論

最大公約數 (GCD) 是可以除以兩個或多個數字而沒有餘數的最大正整數。換句話說，它是可以除以兩個或多個給定數字的最大數字。要找到給定數字的最大公約數，我們可以在 Haskell 中使用 gcd、div 或 mod 函式。它也可以使用遞迴獲得。