使用遞迴將二進位制數轉換為格雷碼的Haskell程式

---

在 Haskell 中，我們可以使用遞迴以及輔助函式來將二進位制數轉換為格雷碼。在第一個示例中，我們將使用基本情況（grayCode "" = "" 和 grayCode [x] = [x]）和遞迴情況，grayCode (x:y:xs) = x : grayCode (xs ++ [if x == y then '0' else if x == '0' then '1' else '0'])）。而在第二個示例中，我們將使用兩個輔助函式以及遞迴。

方法 1：使用遞迴將二進位制數轉換為格雷碼

在此方法中，定義了 grayCode 函式來處理三種情況：

• 當輸入字串為空時，函式返回一個空字串。

• 當輸入字串只有一個字元時，函式返回不變的字串。

• 當輸入字串有兩個或多個字元時，函式獲取前兩個字元 x 和 y，並使用它們來計算格雷碼中的下一個字元。如果 x 和 y 相等，則下一個字元為 '0'。如果 x 為 '0'，則下一個字元為 '1'。否則，下一個字元為 '0'。然後，函式使用字串的其餘部分 (xs) 遞迴呼叫自身，並將此遞迴呼叫的結果附加到當前字元。

演算法

• 步驟 1 - 定義使用者自定義的 grayCode 函式，其中包含基本情況和遞迴情況，如下所示：

grayCode "" = ""
grayCode [x] = [x]
grayCode (x:y:xs) = x : grayCode (xs ++ [if x == y then '0' else if x == '0' then '1' else '0']).

• 步驟 2 - 程式執行將從 main 函式開始。main() 函式控制整個程式。它寫成 main = do。在 main 函式中，定義了一個名為 n 的變數，其值為 "1101100111"，並將 grayCode n 的結果列印到控制檯。輸出將是二進位制數 n 的格雷碼錶示。

• 步驟 3 - 初始化名為“n”的變數。它將儲存要從二進位制轉換為格雷碼的數字。

• 步驟 4 - 在呼叫函式後，使用‘print’函式將生成的格雷碼數字列印到控制檯。

示例 1

在此示例中，我們定義了一個名為 grayCode 的函式，該函式使用遞迴將二進位制數轉換為其對應的格雷碼錶示。

grayCode :: String -> String
grayCode "" = ""
grayCode [x] = [x]
grayCode (x:y:xs) = x : grayCode (xs ++ [if x == y then '0' else if x == '0' then '1' else '0'])

main :: IO ()
main = do
   let n = "1101100111"
   print (grayCode n)

輸出

“1010100010”

方法 2：使用兩個輔助函式和遞迴將二進位制數轉換為格雷碼

在此方法中，grayCode 函式處理輸入字串只有一個字元的情況，並返回不變的字串。當輸入字串有兩個或多個字元時，函式獲取第一個字元，並將其與字串的其餘部分一起傳遞給 grayCodeR 函式。grayCodeR 函式使用當前字元和前一個字元計算格雷碼錶示中的下一個字元。如果當前字元和前一個字元相等，則下一個字元為 '0'。如果當前字元為 '0'，則下一個字元為 '1'。否則，下一個字元為 '0'。然後，函式使用字串的其餘部分和當前字元作為前一個字元遞迴呼叫自身。

演算法

• 步驟 1 - 定義使用者自定義的 grayCode 函式，其中包含基本情況和遞迴情況，如下所示：

grayCode "" = ""
grayCode [x] = [x]
grayCode (x:xs) = x : grayCodeR (xs, x).

• 步驟 2 - 輔助函式定義如下：

grayCodeR ("", prev) = ""
grayCodeR ([x], prev) = [if x == prev then '0' else '1']
grayCodeR (x:xs, prev) = (if x == prev then '0' else '1') : grayCodeR (xs, x).

• 步驟 3 - 程式執行將從 main 函式開始。main() 函式控制整個程式。它寫成 main = do。在 main 函式中，定義了一個名為 n 的變數，其值為 "1101100111"，並將 grayCode n 的結果列印到控制檯。輸出將是二進位制數 n 的格雷碼錶示。

• 步驟 4 - 初始化名為“n”的變數。它將儲存要從二進位制轉換為格雷碼的數字。

• 步驟 5 - 在呼叫函式後，使用‘print’函式將生成的格雷碼數字列印到控制檯。

示例 1

在此示例中，遞迴 grayCode 函式使用兩個輔助函式 grayCode 和 grayCodeR 將二進位制數轉換為其對應的格雷碼錶示。

grayCode :: String -> String
grayCode "" = ""
grayCode [x] = [x]
grayCode (x:xs) = x : grayCodeR (xs, x)

grayCodeR :: (String, Char) -> String
grayCodeR ("", prev) = ""
grayCodeR ([x], prev) = [if x == prev then '0' else '1']
grayCodeR (x:xs, prev) = (if x == prev then '0' else '1') : grayCodeR (xs, x)

main :: IO ()
main = do
   let n = "1101100111"
   print (grayCode n)

輸出

“1010100010”

結論

在 Haskell 中，可以實現將二進位制數轉換為格雷碼數的遞迴函式，該函式採用以字串表示的二進位制數，並返回其對應的格雷碼錶示（字串）。該函式可以對位執行異或運算並將二進位制數向右移位，直到處理完所有位。