コインの両替

最近見かけたブログの記事。

cf. Haskell/Clojureで数学パズル：コインの両替 – Programmer’s Note

同じような問題はずっと前に Haskell でやったことがあるんだけど、今回は Go でやってみる。はじめに思い付いたのはリンク記事の後半に出てくる再帰を使ったほうなんだけど、まずはリンク記事と同じ順で for を使ったやり方で。

package main

import (
    "fmt"
)

func main() {
    fmt.Println(change_coin(1000, 15))
}

func change_coin(money, max_coins int) int {
    patterns := 0
    for m10 := 0; m10 <= max_coins; m10++ {
        for m50 := 0; m50 <= max_coins; m50++ {
            for m100 := 0; m100 <= max_coins; m100++ {
                for m500 := 0; m500 <= max_coins; m500++ {
                    if m10 + m50 + m100 + m500 <= max_coins && 10 * m10 + 50 * m50 + 100 * m100 + 500 * m500 == money {
                        patterns += 1
                    }
                }
            }
        }
    }
    return patterns
}

ああ、ネストした for 文が美しくない!!

で、こっちが再帰を使ったほう。

package main

import (
    "fmt"
)

func main() {
    coins := []int{ 10, 50, 100, 500 }
    fmt.Println(change_coin2(1000, coins, 15))
}

func change_coin2(money int, coins []int, max_coins int) int {
    if money == 0 {
        return 1
    } else if len(coins) == 0 {
        return 0
    } else if max_coins == 0 {
        return 0
    } else {
        patterns := 0
        for use := 0; use <= max_coins; use++ {
            patterns += change_coin2(money - coins[0] * use, coins[1:], max_coins - use) } return patterns
    }
}

だいぶマシだけど else if がなあ。改めて Haskell のパターンマッチの美しいことを思い知る。