使用库函数查找最大公约数的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 函数。它也可以使用递归获得。