はじめに
ProjectEulerのProbem31についてです。
再帰関数での他の人の解答を参考にして、再帰関数初心者が解説してみました。
下で図解もしているので、そちらもぜひ見てください。
（※追記）
また、他の方がコメント欄で別の解答を提示してくれています。
是非他にも解いた方いらっしゃいましたら教えてください。
問題
Problem 31 「硬貨の和」
イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である.
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
以下の方法で£2を作ることが可能である．
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
これらの硬貨を使って£2を作る方法は何通りあるか?
方針
coins = [1,2,5,10,20,50,100,200]の中から任意の一枚ずつ取り出していく作業を、200になるまで繰り返す。
人間の手で行ってたらとてもじゃないけど、数えきれないのでこういう時は「再帰関数」!
再帰関数とは？
def ~ endで定義した関数内で自分自身を呼び出す関数のことをいいます。
有名なものだとフィボナッチ関数などはよく再帰関数の入門として扱われたりします。
初めて聞いたよという方は検索してみてください。
別の解説記事：【図解】階乗の再帰関数【Ruby】
解答
def coin_count(coins, goal, last = 0)
if goal == 0
return 1
end
total = 0
coins.each do |c|
if c < last
next
end
if goal >= c
total += coin_count(coins, goal - c, c)
end
end
total
end
coins = [1,2,5,10,20,50,100,200]
puts coin_count(coins,200)
恥ずかしながら自力では解けなかったのでこちらを元に作成しました。
この解法を日本語で解説しようと思います。
解説
今回作りたいのは200という数値。
そこでgoal = 200と設定して、硬貨一つの値
まず関数内のeach文内から説明を始めます。
if c < last
next
end
これは直近で足した数lastを超える数は足さないようにしています。
つまり、50 + 50 + 100と50 + 100 + 50は今回の問題では同じなので、昇順に足していくパターンのみを採用するようにしています。
nextはブロック内のnext以降の処理をスキップするという処理になります。
次に、再帰関数を用いている関数内の3つ目のif文内です。
if goal >= c
total += coin_count(coins, goal - c, c)
end
今回、cはcoins = [1,2,5,10,20,50,100,200]の要素のいずれかなので1 <= cです。
ですのでcoin_count(coins, goal, last)の引数として渡されるgoalはgoal - cで0に向かって減っていきます。
仮にc = 50、 goal = 200の時は下のようになります。
例）
再帰関数で goal - c が繰り返されていくと、引数の goal は
1回目: 150 ※coin_count(coins, 150, 50)で呼び出し
2回目: 100 ※coin_count(coins, 100, 50)
3回目: 50 ※coin_count(coins, 50, 50)
4回目: 0 ※coin_count(coins, 0, 50)
4回目にcoin_count(coins, 0, 50)で関数が呼び出されたとき、
if goal == 0
return 1
end
になるので、ここまできてようやく、
total += coin_count(coins, goal - c, c)
のcoin_count関数が戻り値 1 を持つことになります。
そこででようやくtotal += 1となり、１プラスされます。
-
goal > 0の時 -
goal < 0の時
この場合は、total = 0が0のまま戻り値に渡されます。
最終的に組み合わせの総数がtotalの値として得られます。
図解
この、関数が繰り返し呼び出されていく状態を図にしてみました。
終わりに
説明の足りない点や、間違っている点、よりわかりやすい説明があればどしどし教えてください。
読んでいただきありがとうございました。