NetaTaneMenu >>>> ケーキの問題
 *ケーキの問題
 ----
 何年か前のプログラミングのコンテストに出た問題からです。
 
 あるケーキ屋さんがロールケーキを出荷します。
 ただし，ロールケーキ（切り口は真円）のサイズはまちまちで，
 半径が3から10までの整数値でできあがってきます。
 これらを7個から12個ずつまとめて箱に並べて出荷します。
 
 問題は，箱の幅とケーキの数とそれぞれの寸法が与えられた時に，
 ケーキが上手く箱に収まるかどうか判定するプログラムを書きなさい，
 というものです。
 
 （以下，考える手間を省くための説明）
 例えば，4,4,4,5,5,6,8という寸法のケーキが与えられた時，
 必要な箱の幅は(4+4+4+5+5+6+8)×2というわけではありません。
 半径8のケーキの横に半径4のケーキを並べると，
 2つのケーキの幅は，明らかに(8+4)×2よりは小さくなります。
 
 さて，結局ケーキの並べ方によって，必要な寸法が変わります。
 そのうち，与えられた箱の幅よりも小さくなるような並べ方が見つかれば可，
 全て調べて無理なら不可。
 
 となるわけです。
 
 いわゆる「同じものを含む順列」で，逆順は省いて検証するというのが，
 すぐに思いつく解法ですが，
 
 + 「同じものを含む順列」の場合，ある順番の「次」を見つけるアルゴリズムって？
 
 (例) 上の例で，5,4,6,4,8,5,4の次の並べ方は？
 
 + 更に逆順を省くアルゴリズムは？
 
 (例) 昇順で調べていく場合，5,4,6,4,8,5,4は既に4,5,8,4,6,4,5で調べているのでパスすべきですが・・・
 
 です。
 実際に組んでみると面白いので，試してみてください。
 
 ではでは。
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS