質問: 再帰の勉強中である問題を解いているのですが解答を見ても分かりません。 分かる方おしえていただけないでしょうか? 問題 長さn(cm)の1本の棒を1(cm)単位に切り分けることを考えます。ただし1本の棒を一度に切る ことができるのは1人だけです。切り分けられた棒が3本あれば、同時に3人で切ることができます。 最大m人の人がいるとき、最短何回で切り分けられるかを求めてください。 解答 def cutbar(m, n, current) #current 現在の棒の数 if current >= n then 0 #切り終えた elsif current < m 1 + cutbar(m, n, current * 2) #次は現在の2倍になる else 1 + cutbar(m, n, current + m) #はさみの数だけ追加 end end puts cutbar(3, 20, 1) puts cutbar(5, 100, 1) 質問は次の2つです。 まず3行目ですが0とはいったい何をしているのでしょうか? よく再帰の例題にある階乗を求める問題などではreturn文などが 書いてありますが、return文の省略と考えていいのでしょうか? 次に5行目の1 + cutbar(m, n, current * 2) の1の意味が分かりません。この1は何の意味があるのでしょうか? 分かる方教えてください。 よろしくお願いいたします。
回答: > > 長さn(cm)の1本の棒を1(cm)単位に切り分けることを考えます。ただし1本の棒を一度に切る > > ことができるのは1人だけです。切り分けられた棒が3本あれば、同時に3人で切ることができます。 > > 最大m人の人がいるとき、最短何回で切り分けられるかを求めてください。 > > > トンチのクイズかな? 初期の棒が2cmなら何人居ようとハサミ1回。 初期の棒が101cmなら何人居ようとハサミ100回。 つまり、`n - 1`を返す関数にすれば解決。 いやいや、1行で済んで良かったね。 でもまぁ、これだと再帰使う意味ないし、 下記のように言い換えてみたら問題としては納得出来るんだけど... > > 1人の作業者は1秒に1度のペースでハサミを入れる事ができます。 > > m人の作業者で切り分けると最低何秒かかるでしょう? > > > これかなり複雑だね。 作業者は1回ハサミを入れる度に倍の人数(1, 2, 4, 8...)が投入出来るようになるわけだね。 でも5人ならどうするの? 2回ハサミ入れたら次は4人で、1人余ってる状態になるから... もし100cmを5人で担当するなら初手で40cm地点にハサミを入れないと綺麗な5等分にはできない。 うーん......再帰は棒の分割に注力というロジックならいけるか? 引数は下記の3個 * 経過時間: 0秒 * 担当人数: (自分含めて)5人 ← でもハサミを入れられるのは自分だけ * 棒の長さ: 100cm 担当人数が5人なので`(100 * (5 / 2).floor / 5).ceil`の位置にハサミをいれて棒を分断、 下記2つの配列を作成してそれぞれ再帰関数にかける。 そして受け取った経過時間秒数のMAXを返させる。 (二回目以降は配列っぽく記載、経過時間, 担当人数, 棒の長さの順) * [1, 2, 40] -> [[2, 1, 20], [2, 1, 20]] * [1, 3, 60] -> [[2, 1, 20], [2, 2, 40]] 次のループも同じ事をやり、それぞれ下記条件の配列になりループが回る 担当人数が1人になったら長さ-1回だけハサミを入れてバラバラにすればいい * [2, 1, 20] -> 2 + (20 - 1) = 21s * [2, 1, 20] -> 2 + (20 - 1) = 21s * [2, 1, 20] -> 2 + (20 - 1) = 21s * [2, 2, 40] -> [[3, 1, 20], [3, 1, 20]] -> [22s, 22s] -> 22s お、これなら確かに再帰で書けるね。 もし待ち作業担当者がまだ居る状態で棒が1cmになってしまったら今の経過時間をそのまま返せば良い。 でも、持ち替えNGとは書いてないんだよね。 なら毎秒一番長い順から順番に担当者に半分にカットさせていくと、 最終的に2cmの棒きれが50個弱出来るから、2cmの棒きれ50個弱を5人皆がそれぞれ手にとって半分にカットしていく光景が見れるわけだね。 でもそうなると、5人揃うまでに3秒かかるから、`1 + 2 + 4 = 7回`ハサミを入れることが可能。 100cmの棒きれは99回ハサミを入れれば1cm毎になるので、後92回ハサミを入れればバラバラになる。 つまり`3秒+ (92回 / 5人).ceil`で答えが出てしまう。 なんてことだ......やはり再帰は不要だったのだ! あ、でもでも3秒で7回刻むロジックは再帰で書くのが一番スッキリするね! そこかよ!って感じで正直微妙だけど...