• WEB

Swiftとバグバグ 〜 両替問題 〜

  • エイチ
    エイチ システムちーむ
  • このエントリーをはてなブックマークに追加
Swiftとバグバグ 〜 両替問題 〜

両替問題は、例えば
「500円玉を100円玉、50円玉、10円玉、5円玉、1円玉で両替する」
とき、何通りの両替パターンがあるかを調べる問題です。

今回はSwiftで両替問題のプログラムを
日々大量のバグを生み出し続けるWebプログラマー「エイチ」と
バグが大好物なエイチのペット「バグバグ」とともに実装してみます。

バグバグ 「zzz zzz zzz」

エイチ  「バグバグ ねぇ バグバグ 起きなよ
      Swiftで両替問題のプログラムを作るよ」

バグバグ 「!!」

エイチ  「A円をN種類の通貨で両替するパターン数は次で求められるぞ」

N種類の通貨でA円を両替するパターン数

N種類から1種類を除いた(N-1)種類の通貨でA円を両替するパターン数

上で除いた1種類の通貨の金額をBとしたとき、N種類の通貨で(A-B)円を両替するパターン数
の合計になる

エイチ  「両替問題は、
      (N-1)種類と(A-B)円のより小さな両替問題
      に再帰的に置き換えられるんだね    」

エイチ  「両替パターン数の数え方は次になるよ」

  • A == 0 のとき、1としてカウントする
  • A < 0 のとき、0としてカウントしない
  • N == 0 のとき、0としてカウントしない

エイチ  「プログラムを実装するとこんな感じになるよ」

カチャカチャッ タンッ!



    let currencyList = [1, 5, 10, 50, 100, 500, 1000, 5000, 10000]

    func countCurrencyExchangePattern(amount: Int) -> Int64 {

        let currencyNumber = currencyList.indexOf(amount)

        return calculateCurrencyExchangePattern(amount: amount, currencyNumber: currencyNumber!)

    }

    func calculateCurrencyExchangePattern(amount amount: Int, currencyNumber: Int) -> Int64 {

        if amount == 0 {
            return 1
        }
        else if amount < 0 {
            return 0
        }
        else if currencyNumber == 0 {
            return 0
        }
        else {
            return calculateCurrencyExchangePattern(amount: amount, currencyNumber: currencyNumber - 1) + calculateCurrencyExchangePattern(amount: amount - currencyList[currencyNumber - 1], currencyNumber: currencyNumber)
        }

    }

エイチ  「500円玉の両替パターン数を求めてみるよ」

カチャカチャッ タンッ!



    countCurrencyExchangePattern(500)

    19161

エイチ  「500円玉の両替パターン数は、19161通りあるんだ
      計算時間は、563.15秒かぁ 約10分だね 結構かかるね
      ちょっと改良してみよう 新しい数え方の条件を加えるよ」

N == 1 のとき、1としてカウントする

エイチ  「プログラムにも条件を追加してっと」

カチャカチャッ タンッ!



    func calculateCurrencyExchangePattern(amount amount: Int, currencyNumber: Int) -> Int64 {

        if amount == 0 {
            return 1
        }
        else if amount < 0 {
            return 0
        }
        else if currencyNumber == 1 {
            return 1
        }
        else if currencyNumber == 0 {
            return 0
        }
        else {
            return calculateCurrencyExchangePattern(amount: amount, currencyNumber: currencyNumber - 1) + calculateCurrencyExchangePattern(amount: amount - currencyList[currencyNumber - 1], currencyNumber: currencyNumber)
        }

    }

エイチ  「今度はどうかな 実行してみよっと」

カチャカチャッ タンッ!



    countCurrencyExchangePattern(500)

    19161

エイチ  「500円玉の両替パターン数は、19161通りでさっきと同じ
      計算時間は、4.97秒かぁ だいぶ早くなったね    」

エイチ  「よしっ これでおしまいっと」

エイチ  「さあ バグバグ ソースコード 全部お食べ」

バグバグ 「バグバグ バグバグ バグバグ」

エイチ  「美味しかったろう バグバグ」

このエントリーをはてなブックマークに追加

エイチが最近書いた記事

WRITERS POSTS もっと見る

他にもこんな記事が読まれています!

  • WEB
  • マーケティング
  • サーバー・ネットワーク
  • ライフスタイル
  • お知らせ