用函數式編程解決邏輯難題 - Swift 版本
這篇翻譯的文章，用兩種方法解決了同一個邏輯難題。第一種方法的編程風格接近大多數 iOS 開發(fā)者，實現了指令式編程的解決方案。第二種方法利用了 Swift 的一些語言特性，實現了函數式編程的解決方案。
源代碼可以在這里下載：https://github.com/ijoshsmith/break-a-dollar
邏輯難題
前陣子朋友和我說起，把1美元分解成更小的面額，有293種方法。換句話說，如果一個哥們兒告訴你他有1美元，那么他的手里有293種可能的組合，有可能是兩個50美分，也可能是4個25美分。第二天，我就開始嘗試用代碼去解決這個問題。這篇博客回顧了當時想到的兩種解決方案。
美元硬幣
對于不熟悉美元硬幣的同學，可以先了解一下美元的硬幣。如下圖所示，1美元(dollar) = 100美分(cent)：
初探問題
思考后我發(fā)現用一種比較簡單骯臟的手段解決這個問題并不難，但是這還遠遠不夠。我想找到一種優(yōu)雅的解決方案，所以我嘗試從各個角度思考這個問題，最終得到了想要的答案。
解決這個問題的關鍵在于遞歸的分解問題。“如何用各種硬幣組合拼成1美元”，更寬泛點講，其實就是“如何用各種硬幣組合拼成指定金額”。
舉個人民幣的例子。你欠人家100塊，人家說你100塊都不給我。你說好，我給！于是掏出兩張50，這便是一個50+50的解決方案。
這時你發(fā)現有一張是嶄新的50，你不想給他這張50，于是你的問題變成了：如何用手里的碎錢組合出50面額的錢。
后來你把50換成了5張10塊，這便是一個50+10*5的解決方案，然后感覺有一張10塊是嶄新的，要不我換成硬幣給他。
于是問題又變成了：如何組合出10面額的錢。就是這樣慢慢拆分下去。
點擊 這里 查看完整的算法回顧。
先造硬幣
我多次提到“硬幣”這個詞，實際上一枚硬幣也就是一個整數值，代替了它價值多少美分。我寫一個枚舉類存儲所有的硬幣面額，然后再用一個靜態(tài)方法降序返回所有的值：
- enum Coin: Int {
- case SilverDollar = 100
- case HalfDollar = 50
- case Quarter = 25
- case Dime = 10
- case Nickel = 5
- case Penny = 1
- static func coinsInDescendingOrder() -＞ [Coin] {
- return [
- Coin.SilverDollar,
- Coin.HalfDollar,
- Coin.Quarter,
- Coin.Dime,
- Coin.Nickel,
- Coin.Penny,
- ]
- }
- }
解決方案1：指令式編程 - Imperative
指令式編程的一個重要觀點是：變量改變狀態(tài)。指令式的程序像是一種微型控制器，它告訴計算機如何完成任務。接下來的 Swift 代碼大家看起來應該都不陌生，因為 objc 就是一種指令式的編程語言：
- func countWaysToBreakAmout(amount: Int, usingCoins coins:[Coin]) -＞ Int{
- let coin = coins[0]
- if (coin == .Penny) {
- return 1
- }
- var smallerCoins = [Coin]()
- for index in 1..!=coins.count {
- smallerCoins.append(coins[index])
- }
- var sum = 0
- for coinCount in 0...(amount/coin.rawValue) {
- let remainingAmount = amount - (coin.rawValue * coinCount)
- sum += countWaysToBreakAmout(remainingAmount, usingCoins: smallerCoins)
- }
- return sum
- }
仔細看下上面的代碼，計算過程一共分三步：
首先取出可用數組中的第一個硬幣，如果這枚硬幣已經是 1 美分，也就是最小的面額，那沒有繼續(xù)拆分的可能性，直接返回1作為結束。
然后創(chuàng)建了一個數組 (smallerCoins) ，存儲比當前硬幣更小的硬幣，用來作為下次調用的參數。
最后計算除去第一次取出的硬幣之后，還有多少種解決方案。
這樣的代碼對于指令式編程來說再平常不過，接下來我們就來看下如何用函數式編程解決這個問題。
解決方案2：函數式編程 - Functional
函數式編程的依賴對象，是函數，而不是狀態(tài)變化。沒有太多的共享數據，就意味著發(fā)生錯誤的可能性更小，需要同步數據的次數也越少。 Swift 中函數已經是一等公民，這讓高階函數變成可能，也就是說，一個函數可以是通過其它函數組裝構成的。隨著 objc 中 block 的引入， iOS 開發(fā)者對這個應該并不陌生。
下面是我的函數式解決方案：
- func countWaysToBreakAmount(amount: Int, usingCoins coins:Slice) -＞ Int{
- let (coin, smallerCoins) = (coins[0], coins[1..<coins.count]) if (coin ="= .Penny) {" return 1="" }="" let coincounts =" [Int](0...amount/coin.rawValue)" return coincounts.reduce(0) { (sum, coincount) in="" let remainingamount =" amount - (coin.rawValue * coinCount)" return sum + self.countwaystobreakamount(remainingamount, usingcoins: smallercoins)="" }
- </coins.count])>
<="" pre="">
第二個參數是 Slice
我用元組的語法同時獲取了 coin 和 smallerCoins 這兩個數據，因為取頭取尾可以說是同一個操作。與其寫一堆代碼去解釋如何先取出第一個元素，然后再獲取剩下的元素，不如直接用“取出頭部和尾部”這樣語義化的方式一步到位。
接下來，也并沒有采用循環(huán)然后改變局部變量的方法來計算剩余的組合數，而是用 reduce 這個高階函數。如果你對 reduce 這個函數不太熟悉，可以看下這篇文章有個大概的了解。
首先 coin 指當前處理的硬幣， coinCounts 是一個數組，里面存儲了所有當前面額的硬幣的可能出現的數目。比如 amount 是10， coin 是3，那么 coinCounts 的值就是，面額為3的硬幣可能有多少。顯然應該最多出現3個，所以 coinCounts 是 [1,2,3] 這樣的一列數。然后在分別對每種情況進行分解計算。
思考
Swift 對于函數式編程的支持讓我感覺的興奮，Excited！換種方式思考或許是個不小的挑戰(zhàn)，但是這都是值得的。幾年前我自學了一些 Haskell ，我很欣喜的發(fā)現一些函數式思考習慣，讓我在 iOS 開發(fā)中也能受益匪淺。
示例項目的源代碼可以在這里下載。
