使用递归查找最大公约数的Haskell程序

在 Haskell 中，我们可以使用递归以及递归情况语句来查找最大公约数。在第一个示例中，我们将使用递归以及基本情况和递归情况，而在第二个示例中，我们将使用 (case (x, y) of) 语句。

算法

  • 步骤 1 − 定义用户自定义的递归 gcd' 函数，如下所示：

  • 例如 1 −

gcd' x y
   | y == 0    = x
   | otherwise = gcd' y (x `mod` y).

  • 例如 2 −

gcd' x y = case (x, y) of
   (x, 0) -> x
   (x, y) -> gcd' y (x `mod` y).

  • 步骤 2 − 程序执行将从 main 函数开始。main() 函数控制整个程序。它被写成 main = do。在 main 函数中，程序将 x 和 y 设置为要查找最大公约数的数字，然后使用这些数字作为参数调用 gcd' 函数。然后将结果打印到控制台。

  • 步骤 3 − 初始化名为“x”和“y”的变量。它将保存要计算最大公约数的数字。

  • 步骤 4 − 函数调用完成后，使用 'print' 函数将结果的最大公约数值打印到控制台。

示例 1

在这个例子中，gcd' 函数接收两个整数 x 和 y 作为输入，并使用递归来查找它们的最大公约数。递归的基本情况是当 y 等于 0 时，此时最大公约数就是 x。在所有其他情况下，该函数使用参数 y 和 x 除以 y 的余数来调用自身，这将计算 x 除以 y 的余数。这将持续进行，直到余数为 0，此时函数将返回最大公约数。

gcd' :: Int -> Int -> Int
gcd' x y
   | y == 0    = x
   | otherwise = gcd' y (x `mod` y)

main :: IO ()
main = do
   let x = 48
   let y = 18
   print (gcd' x y)

输出

6

示例 2

在这个例子中，gcd' 函数接收两个整数 x 和 y 作为参数。该函数使用 case 语句检查 x 和 y 的值。如果 y 为 0，则函数返回 x 作为最大公约数。如果 y 不为 0，则该函数使用 y 和 x 除以 y 的余数作为新参数来调用自身。这将持续进行，直到 y 为 0，此时函数返回 x 作为最大公约数。

gcd' :: Int -> Int -> Int
gcd' x y = case (x, y) of
   (x, 0) -> x
   (x, y) -> gcd' y (x `mod` y)

main :: IO ()
main = do
   let x = 60
   let y = 48
   print (gcd' x y)

输出

12

结论

两个或多个非零整数的最大公约数 (GCD) 是能同时整除这些整数的最大正整数。它也被称为最大公因数 (GCF) 或最高公因数 (HCF)。两个整数的最大公约数可以使用欧几里得算法计算，欧几里得算法是一种递归方法，也可以将其转换为尾递归。多个整数的最大公约数可以通过迭代应用欧几里得算法来找到。最大公约数是数论中的一个重要概念，在计算机科学和数学中有着广泛的应用。在 Haskell 中，要使用递归查找数字的最大公约数，我们可以使用用户定义的函数以及 case 语句。

更新于: 2023年3月27日

129 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告