質問: 2 ```
回答: 「用意された種類のお金を組み合わせて x 円払いたい。お金の枚数を最小にしつつ払うにはどれを何枚払えば良いだろうか?」という問題を解くことを考えます (どんな枚数でも良いのなら、1 円玉をたくさん払えば良くなってしまいます)。 ご提示のような種類のお金の場合、これは貪欲法で求めることができます。つまり、額面の大きな種類のお金で払えるだけ払ってしまい、払えなくなったら次に大きな種類のお金で払うことを考えていけば良いです。これで良いことの証明はここに書くには長いので省略しますが、興味があれば投稿末尾にリンクしたページをご覧ください。 部分的な例として「x 円払うのに、5000 円札で払えるだけ払うと 5000 円札を何枚使って、その後何円残るか」を計算する Ruby のコードを示しておきます。 ``` $ irb irb(main):001:0> x = 9532 # 今払いたいお金が変数 x に代入されているとします。 => 9532 irb(main):002:0> n5000 = x / 5000 # 5000 円札何枚まで払えるかは、整数として割り算をすれば分かります。ここでは変数 n5000 に代入してみます。 => 1 irb(main):003:0> x = x - 5000 * n5000 # 残金は、上で求めた枚数分の金額を引けば分かります。 => 4532 ``` 尚、硬貨の種類によっては貪欲法で解けないことがあるので注意してください。より詳細な情報は以下のサイトが参考になるかと思います (「硬貨 貪欲法」などで検索すると出てきます)。 * 硬貨の問題が貪欲法で解けるための条件 -- Qiita * 欲張り法 (greedy strategy) -- M.Hiroi's Home Page * Change-making problem -- 英語版 Wikipedia