どうも、小野氏です。

前回に引き続き、プログラム脳を鍛える数学パズルの問題を解いていきたいと思います。

作者:増井敏克
発売日: 2015/10/16
メディア: Kindle版

今週は本書のQ5について紹介いたします。

正直答えを見ながら解いたので、ほとんど模範解答をなぞる形になってしまう気がしますが、頑張って解説していきます。

Q5 いまだに現金払い？

問題(要約)

1000円札を10円玉、50円玉、100円玉、500円玉で両替するとき、両替後の硬貨の枚数が15枚以下に組み合わせは何通りか。

(なお、使わない硬貨があっても構わない。)

また、問題には拡張性を意識した実装を行ってくださいとの記載がありました。

(正直、両替後の金額が1000円であることを固定してしまえるなら、簡単だと思います。)

回答

書籍に記載があった模範解答のうち、私の考えに近かったものを記載します。

ざっくり処理の流れを説明すると以下の通りです。

変数の宣言
repeated_combinationメソッドを配列の要素の重複組み合わせを作成
- 後に説明を記載
それぞれの配列の合計値を計算し、1000になるものの個数を数え上げる

解説

repeated_combinationメソッドは、引数の長さの配列の重複組み合わせを作るメソッドです。

(重複組み合わせなので、取り出した元の並びは考慮しないが、同じ元を複数取り出すことが許容する)

具体例として、引数を2とした場合を書き出します。

[500, 100, 50, 10].repeated_combination(2).to_a 
#=> 
　[
        [500, 500], [500, 100], [500, 50], [500, 10],
        [100, 100], [100, 50],  [100, 10],
        [50, 50], [50, 10],
        [10, 10]
    ]

上述の処理を行うことで、硬貨2枚の重複を許す全ての組み合わせが洗い出さます。

そして、戻り値となる配列の元のうち和が1000になるものを探すことで、硬貨2枚の場合に1000円となる組み合わせを洗い出すことが出来ます。 (上述の具体例だと、[500, 500]が相当します。)

上述の処理を硬貨2枚～15枚の場合にわたって行うことによって、硬貨15枚以下で1000円となる通りを全て洗い出すことができます。

所感

本問題を解くうえで、上述のメソッドを知らなかったので、以下の方法で実装しようと考えました。

coinの種類を配列で宣言
- 上述のコードの[500, 100, 50 , 10]にあたる部分
コイン枚数の配列を宣言し、配列の和が2~15となるパターンを全て洗い出す
- 具体的には長さ4の配列[0 ,0 ,0 ,0 ]の要素に対して値を加算することで、全パターンを洗い出そうと考えておりました。
coinの種類の配列のi番目とコイン枚数の配列のi番目をかけ合わせ、1000円となるものの個数を数える(0≦i≦3)

自分のプログラミングスキルだと上述の2にあたる処理を実装することができず、今回はあきらめてしまいました。

おそらくrepeated_combinationメソッドのソースコードでは、上述の2の処理のようなことをやっているとは思うので、復習のために確認しようと思います。

また、本問題の回答として再帰メソッドを使った以下の方法も紹介されておりました。

行っている処理は以下の通りです。

(十分に理解できていない中で記載を行っているので、わかりにくいかもしれません。。。)

変数targetを配列coinsの要素を変数usable個までつかって実現するメソッドとしてchange(target, coins, usable)メソッドを宣言
- 今回のケースとしては、target=1000, coins=[500, 100, 50, 10], usable = 15である
配列coinsの最初の要素を抜き出し、変数coinに代入する
- shiftメソッドは破壊的メソッドなので、本処理を行った後に配列coinsから最初の要素は消える
配列coinsの要素が0ではない場合、0を下限にtarget/coinの回数を上限に硬貨の枚数を変え、changeメソッドを呼び出す
- 例えば、coinが500でiが1の場合、change(500, [100, 50, 10], 14)を呼び出す
  - つまり、500円を100円玉、50円玉、10円玉を14枚以下で実現するメソッドを呼び出す
- coinsはcloneすることで別オブジェクトとして生成する(つまり、元の配列coinsに影響を与えないよう処理を進める)
配列coinsの要素が0の場合、変数targetを変数coinで割った数がusable以下になる場合、条件を満たす通りとしてカウントする
- 配列coinsは、処理の中で[500, 100, 50, 10]→[100, 50, 10]→[50, 10]→[10]と変化するため、coins.sizeが0となる場合coinはかならず10となる。
  - target/coin = 0/10 = 0 <= usable を満たす場合には、条件を満たすものとしてのカウントが行われますため、10円を使わない場合でも条件を満たすものとしてカウントされるものは存在する。

正直、上述の方法はなにたべてたら思いつくのかわからないくらい異次元の回答に見えました。。。

ただ本記事を書くために処理を追うなかで、何をやっているのかは大体わかるようになりました。

自分でコードを実装する際に、上述の方法も考慮できるようになれるよう、学習を進めていければと思いました。プログラミングは奥が深いなぁ。。。。

以上

小野氏の学習日記

プログラミングや書評を徒然と記載していくブログです

プログラム脳を鍛える数学パズル　第二弾

Q5 いまだに現金払い？

問題(要約)

回答

解説

所感