アルゴリズム

以下の問題教えて欲しいです。よろしくお願いします。
長さ100の棒を、100個の長さ1の断片に切り分ける必要がある。複数の棒の断片を同時に切断できるとすると、切断の最小回数はいくつか？また、長さ n の棒を 長さ1の断片に切り分ける回数はいくつか。アルゴリズムの概要についても説明しなさい。
# 回数なので整数になることに注意

No.2 ベストアンサー 回答者： yhr2 回答日時： 2020/11/20 10:48

具体的に考えれば

１回目の切断 → 50 が2本
２回目の切断 → 25 が4本
３回目の切断 → 25 は２等分できないので 12 と 13 に切断
　　　　　　→ 12 が４本、13が４本（合計 8本）
４回目の切断 → 12は2等分、13 は２等分できないので 6 と 7 に切断
　　　　　　→ 6 が12本、7が４本（合計 16本）
５回目の切断 → 6は2等分、7 は２等分できないので 3 と 4 に切断
　　　　　　→ 3 が28本、4が４本（合計 32本）
６回目の切断 → 4は2等分、3 は２等分できないので 1 と 2 に切断
　　　　　　→ 1 が28本、2が36本（合計 64本）
７回目の切断 → 2 のみを切断（１はもう切断不要）
　　　　　　→ 1 が100本

これを、どのようにアルゴリズム化するかですね。
単純に
　2^6 = 64 < 100 < 2^7 = 128
ということだと思いますけどね。

これを「長さ n」に拡張すれば
　2^(x - 1) < n < 2^x
となる「x」を求める、ということになると思います。

「結果」そのものよりも、「どのように考えればよいか」という「戦略の見つけ方」「着眼点」が大事です。

この回答へのお礼

分かりやすく説明ありがとうございます。頑張ってみます！

お礼日時：2020/11/20 14:10

No.1 回答者： Zincer 回答日時： 2020/11/19 11:01

1回切断すると2本になります。

ｋ回の切断で（最大）２＾ｋ本の断片に切り分けることが可能になるので、これが目標の個数以上に分けることができる回数が最小回数になるでしょう。