Haskell程序计算最高公因数

本教程将帮助我们用Haskell编程计算最高公因数。最高公因数（HCF），也被称为最大公除数（GCD），是指除掉两个或多个整数而不留余数的最大正整数。它是衡量能将两个或多个整数相除而不留余数的最大正整数。

方法1：使用用户定义的hcf函数

在这个方法中，定义了一个函数 hcf’，它将两个整数作为输入，并使用递归和模运算符来重复计算大数除以小数的余数，直到小数变成0。

算法

第1步– 导入Data.Function模块。
第2步 – 用户定义的hcf’函数使用递归和模运算符反复计算大数除以小数的余数，直到小数变成0，如：hcf’ a b = if b == 0 then a else hcf’ b (a mod b)。而较大的数字将作为最高公因数返回。
第3步 – 程序的执行将从主函数开始。main()函数拥有程序的全部控制权。它被写成main = do。它接收两个整数作为输入，并打印出hcf’函数的输出。
第4步 – 变量 “a “和 “b “被初始化。最初，它将有一个垃圾值。然后，一个常数被分配给它，以找到它们的最高公因子。
第5步 – 在调用用户定义的hcf’函数时使用’print’函数将结果打印到控制台。

例子

在这个例子中，我们将看到我们如何计算最高公因数。这可以通过使用用户定义的hcf’函数来完成。

import Data.Function
import Text.Printf

hcf' :: Int -> Int -> Int
hcf' a b = if b == 0 then a else hcf' b (a `mod` b)

main :: IO ()
main = do
   let a = 36
   let b = 63
   printf "HCF of %d and %d is:" a b
   print (hcf' a b)

输出

HCF of 36 and 63 is:9

方法2：使用foldl1函数

这种方法将一个整数列表作为输入，使用foldl1函数对列表中的元素重复应用gcd函数，从前两个元素开始，然后是这个元素和下一个元素的结果，以此类推。

算法

第1步 – hcf函数是用foldl1和gcd来定义列表中的元素的，hcf = foldl1 gcd。结果将作为最高公因数返回。
第2步 – 程序的执行将从main函数开始。main()函数拥有程序的全部控制权。它被写成main = do。它接受一个整数列表作为输入，并打印出hcf函数的输出。
第3步 – 变量 “number “被初始化，以保存整数列表。
第4步 – 在调用hcf函数时，使用’print’函数将结果打印到控制台。

例子

在这个例子中，我们将看到我们如何计算最高公因数。这可以通过使用 foldl1 函数来完成。

import Data.Function
import Text.Printf

hcf :: [Int] -> Int
hcf = foldl1 gcd

main :: IO ()
main = do
   let numbers = [36, 63, 9]
   printf("HCF of ")
   print(numbers)
   print (hcf numbers)

输出

HCF of [36,63,9]
9

方法3：使用固定函数

这种方法使用fix函数来定义一个自述函数，使用递归和modulo运算符来计算最高公因子。

算法

第1步 – 使用Prelude模块中的Data.Function.fix和gcd。
第2步 – 使用fix函数定义hcf函数，hcf a b = fix (\f x y -> if y == 0 then x else f y (x mod y)) a b. 结果作为最高公因子返回。
第3步 – 程序的执行将从主函数开始。main()函数拥有程序的全部控制权。它被写成main = do。它接收两个整数作为输入，并打印出hcf函数的输出。
第4步– 名为 “a “和 “b “的变量被初始化。一个值被分配给它，以找到它们的最高公因子。
第5步 – 在调用hcf函数时，使用’print’函数将结果打印到控制台。

例子

在这个例子中，我们将看到我们如何计算最高公因数。这可以通过使用fix函数来完成。

import Prelude hiding (gcd)
import Data.Function
import Text.Printf
hcf :: Int -> Int -> Int
hcf a b = fix (\f x y -> if y == 0 then x else f y (x `mod` y)) a b

main :: IO ()
main = do
   let a = 36
   let b = 63
   printf"HCF of %d and %d is:" a b
   print (hcf a b)