2 min to read
CIS 194 01 Homework
Source: CIS 194: Homework 1
解決作業時，不僅要努力創建有效的代碼，還要努力創建簡潔時尚的代碼。 有關一些一般準則，請參見網站上的樣式指南。 嘗試編寫僅執行單個任務的小型函數，然後將這些較小的部分組合以創建更複雜的函數。 不要重複自己：為每個邏輯任務編寫一個函數，並在必要時重複使用這些函數。
確保為每個練習編寫具有完全指定名稱和類型簽名的函數（以幫助我們測試您的代碼）。 您可以使用所需的任何名稱和類型簽名創建其他幫助程序功能。
▌驗證信用卡號 1
1 改編自 Doaitse Swierstra 教授於2008年至2009年在烏得勒支大學功能編程課程中分配的第一門實習課程。
您是否想知道網站在線購物時如何驗證您的信用卡號？ 他們不會檢查龐大的數字數據庫，也不會使用魔術。 實際上，大多數信用提供者都依賴校驗和公式來區分有效數字和數字的隨機集合（或鍵入錯誤）。
在本部分中，您將實現信用卡的驗證算法。 它遵循以下步驟：
- 從右邊開始，將第二個數字的值加倍。 也就是說，最後一位沒有變化； 倒數第二個數字翻倍； 倒數第三位保持不變； 等等。 例如，[1,3,8,6] 變為 [2,3,16,6]。
- 將雙精度值的數字和原始數字中的非雙精度數字相加。 例如，[2,3,16,6] 變為 2 + 3 + 1 + 6 + 6 = 18。
- 當總和除以 10 時，計算餘數。對於上面的示例，餘數為 8。如果結果等於 0，則該數字有效。
▌練習 1
我們需要首先找到一個數字。 定義函數
toDigits :: Integer -> [Integer]
toDigitsRev :: Integer -> [Integer]
toDigits 應該將正整數轉換為數字列表。 （對於 0 或負輸入，toDigits 應該返回空列表。） toDigitsRev應該執行相同的操作，但是數字要相反。
例如：
toDigits 1234 == [1,2,3,4]
toDigitsRev 1234 == [4,3,2,1]
toDigits 0 == []
toDigits（-17）== []
▌練習 2
一旦我們以正確的順序排列了數字，我們就需要將每兩個數字加倍。定義函數
doubleEveryOther :: [Integer]-> [Integer]
請記住，doubleEveryOther 應該將其他所有數字從右開始，即倒數第二個，倒數第四個。 。 。數字翻了一番。
例如：
doubleEveryOther [8,7,6,5] == [16,7,12,5]
doubleEveryOther [1,2,3] == [1,4,3]
▌練習 3
doubleEveryOther 的輸出包含一位數字和兩位數字的混合。定義函數
sumDigits :: [Integer] -> Integer
計算所有數字的總和，例如：
sumDigits [16,7,12,5] = 1 + 6 + 7 + 1 + 2 + 5 = 22
▌練習 4
定義函數
validate :: Integer -> Bool
指示整數是否可以是有效的信用卡號。這將使用先前練習中定義的所有功能。
例如：
validate 4012888888881881 = True
validate 4012888888881882 = False
▌河內塔 2
2 改編自本傑明·皮爾斯（Benjamin Pierce）教授的 UPenn CIS 552 中的作業
▌練習 5
河內塔是一個經典的難題，其解決方案可以遞歸描述。不同大小的磁盤堆疊在三個銷釘上。目標是從所有磁盤都堆疊在第一個銷釘上的開始配置，到所有磁盤都堆疊在最後一個銷釘上的結束配置，如圖1所示。
唯一的規則是
-
您一次只能移動一個磁盤，並且
-
較大的磁盤可能永遠不會堆疊在較小的磁盤上。
例如，作為第一個移動，您可以做的就是將最上面最小的磁盤移動到另一個釘上，因為一次只能移動一個磁盤。
從這一點來看，轉到圖 3 所示的配置是非法的，因為不允許將綠色磁盤放在較小的藍色磁盤上。
要使用釘 c 作為臨時存儲，將 n 個光盤（大小逐漸增加）從釘 a 移到釘 b，
- 使用 b 作為臨時存儲，將 n − 1 光盤從 a 移到 c
- 將頂部光盤從 a 移到 b
- 使用a作為臨時存儲，將 n − 1 張光盤從 c 移到 b。
在本練習中，使用以下類型定義函數 hanoi：
type Peg = String
type Move = (Peg, Peg)
hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
給定三個釘的碟片數量和名稱，河內應返回將碟片疊從第一個釘釘移至第二個釘釘的動作清單。
請注意，類型聲明與上面的類型 Peg = String 一樣，成為類型同義詞。 在這種情況下，Peg 被聲明為 String 的同義詞，並且 Peg 和 String 這兩個名稱現在可以互換使用。 以這種方式為類型賦予更多描述性名稱可以用於為複雜類型賦予較短的名稱，或者（如此處所示）只是為了幫助文檔。
例如：
hanoi 2 "a" "b" "c" == [("a","c"), ("a","b"), ("c","b")]
▌練習 6（可選）
如果釘子是四個而不是三個，該怎麼辦？ 也就是說，目標仍然是將一堆光盤從第一個釘移動到最後一個釘，而無需將較大的光盤放在較小的光盤上，但是現在有兩個額外的釘可以用作“臨時”釘 存儲而不是一個。 編寫與 hanoi 類似的函數，以盡可能少的動作解決此問題。
比起三釘，應該可以用更少的動作來做。 例如，對於三個銷釘，需要215 − 1 = 32767個移動才能傳輸15個光盤。 用四個釘子可以完成 129 個動作。 （請參見Graham，Knuth 和 Patashnik 的練習1.17，《具體數學》，第二版，Addison-Wesley，1994年。）
