ケーキの問題
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
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...
です。
実際に組んでみると面白いので,試してみてください。
ではでは。
終了行:
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...
です。
実際に組んでみると面白いので,試してみてください。
ではでは。
ページ名: