長さ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回刻むロジックは再帰で書くのが一番スッキリするね!
そこかよ!って感じで正直微妙だけど…
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。