使用Haskell程式計算最大公約數

---

本教程將幫助我們使用Haskell程式語言計算最大公約數。最大公約數(HCF)，也稱為最大公因數(GCD)，是能夠同時整除兩個或多個整數的最大正整數。它是能夠同時整除兩個或多個整數的最大正整數的度量。

方法一：使用使用者自定義的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()`函式控制整個程式的執行。它寫成`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

方法二：使用`foldl1`函式

此方法接收一個整數列表作為輸入，並使用`foldl1`函式反覆將`gcd`函式應用於列表的元素，從前兩個元素開始，然後是結果和下一個元素，依此類推。

演算法

• 步驟1 − 使用`foldl1`和`gcd`定義`hcf`函式，應用於列表的元素，如：`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

方法三：使用`fix`函式

此方法使用`fix`函式定義一個自引用函式，該函式使用遞迴和取模運算子計算最大公約數。

演算法

• 步驟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()`函式控制整個程式的執行。它寫成`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)

輸出

HCF of 36 and 63 is:9

結論

可以透過使用使用者自定義的`hcf'`函式、`foldl1`函式或`fix`函式來計算在Haskell中傳遞的數字的最大公約數。結果透過呼叫定義的函式並在`print`函式中使用被列印到控制檯。