ある面積に図形をできるだけ多く配置するためには、どのように計算したらいいでしょうか?

(例えば195×450の中に94×64の図形をできるだけ多く配置するにはどのように計算しますか?)

また、この計算をC言語でプログラムした場合のソースも教えてください。

※いまいちはてなの使い方がわからないのですが…一番ドンピシャな回答を頂けた方に100ポイント差し上げます。

回答の条件
  • 1人2回まで
  • 登録:2009/06/16 11:13:41
  • 終了:2009/06/23 11:15:02

ベストアンサー

id:y_yanbe No.2

つづきはid:yanbeで!回答回数3ベストアンサー獲得回数12009/06/16 15:40:45

ポイント27pt

「与えられる領域と図形はともに矩形である」という前提をおいてよいのでしょうか。その場合の解法は比較的単純だと思います。以下の手順を踏みます。

  1. 与えられた領域に対して、左上から右下にかけて、与えられたサイズの矩形をぴったり隙間が出来ないように配置する
  2. 与えられた領域と図形のサイズによっては領域の右側あるいは下側が余るので、その部分に図形を90度回転して配置できないかチェックし、もし配置できるなら配置する
  3. 1.において最初に90度回転した状態で配置した方がより多くの図形を配置できる場合もあるので、その場合とどちらが多くの図形を配置できるかチェックし、より多く配置できる方を採用する
  4. 3.で採用した最終的な図形の配置を出力する

(配置できる図形の数が等しい複数のパターンが存在する場合は、それぞれのパターンを出力するようにしました)

上記の手続きを実現するC言語のソースコードは以下のようになります(長いのでリンク先に示しました)。

http://gist.github.com/130568

実際にコーディングする際は、ループの境界条件や図形の縦横のサイズが同じ場合などに注意する必要があります。

なお、問題文が「矩形以外、たとえば円や矩形以外の多角形も受け付ける」ということでしたら、当然アルゴリズムはずっと複雑になり、ちょっと今は解法を思いつかないので、その場合は他の回答者の方に譲ります。

id:otobeck

まさしくこれです!

手順についてもわかりやすくお答え頂きありがとうございました。

ループの境界条件についてですが、単純に縦横のサイズを超えたら止まるという条件だけでは問題が起きるのでしょうか…?

差し支えない範囲でヒントを頂けないでしょうか。

よろしくお願い致します。

2009/06/16 16:18:57

その他の回答(2件)

id:kn1967 No.1

kn1967回答回数2915ベストアンサー獲得回数3012009/06/16 12:21:08

ポイント27pt

下記が参考になるかと思います。説明とコードをよく見比べて学習してください。

http://books.google.co.jp/books?id=eS9EBhKmMzUC&pg=PA15&lpg=PA15...

書籍では縦横それぞれ数個の正方形などを使っていますが 94個 x 64個 と考えれば良いだけなので仕組みは同じです。


上記を買うとすれば・・・¥3150-

C言語逆引き大全 500の極意

C言語逆引き大全 500の極意

  • 作者: 平田 豊
  • 出版社/メーカー: 秀和システム
  • メディア: 単行本

id:otobeck

回答ありがとうございます。

確かにこの書籍を購入すれば理解できるとは思うのですが、できればWebで同じような解説をしているところはないでしょうか…。

当方あまりプログラムに関する知識はないため、単純化したわかりやすい解説をして頂けると、非常に有り難いです。また、計算機で簡単に算出する方法があれば、その計算方法も知りたいです。こういった計算はかなり面倒なのでしょうか…?上の質問で言葉が足りなくてすみません。

もう少し他の回答も待ってみたいと思います。よろしくお願いします。

2009/06/16 15:54:39
id:y_yanbe No.2

つづきはid:yanbeで!回答回数3ベストアンサー獲得回数12009/06/16 15:40:45ここでベストアンサー

ポイント27pt

「与えられる領域と図形はともに矩形である」という前提をおいてよいのでしょうか。その場合の解法は比較的単純だと思います。以下の手順を踏みます。

  1. 与えられた領域に対して、左上から右下にかけて、与えられたサイズの矩形をぴったり隙間が出来ないように配置する
  2. 与えられた領域と図形のサイズによっては領域の右側あるいは下側が余るので、その部分に図形を90度回転して配置できないかチェックし、もし配置できるなら配置する
  3. 1.において最初に90度回転した状態で配置した方がより多くの図形を配置できる場合もあるので、その場合とどちらが多くの図形を配置できるかチェックし、より多く配置できる方を採用する
  4. 3.で採用した最終的な図形の配置を出力する

(配置できる図形の数が等しい複数のパターンが存在する場合は、それぞれのパターンを出力するようにしました)

上記の手続きを実現するC言語のソースコードは以下のようになります(長いのでリンク先に示しました)。

http://gist.github.com/130568

実際にコーディングする際は、ループの境界条件や図形の縦横のサイズが同じ場合などに注意する必要があります。

なお、問題文が「矩形以外、たとえば円や矩形以外の多角形も受け付ける」ということでしたら、当然アルゴリズムはずっと複雑になり、ちょっと今は解法を思いつかないので、その場合は他の回答者の方に譲ります。

id:otobeck

まさしくこれです!

手順についてもわかりやすくお答え頂きありがとうございました。

ループの境界条件についてですが、単純に縦横のサイズを超えたら止まるという条件だけでは問題が起きるのでしょうか…?

差し支えない範囲でヒントを頂けないでしょうか。

よろしくお願い致します。

2009/06/16 16:18:57
id:nanoruhodono No.3

nanoruhodono回答回数28ベストアンサー獲得回数62009/06/16 17:54:29

ポイント26pt

この問題は図形の詰め込み問題と言って結構難しい問題です。

私はこの手の問題については門外漢なので手がかりだけしか提示できませんが以下参考にして下さい。

http://ja.wikipedia.org/wiki/Sequence-pair

http://www.orsj.or.jp/~archive/pdf/bul/Vol.50_12_837.pdf

id:otobeck

私も自分で調べていてナップサック問題まで辿り着いたものの、

かなり3次元の要素が含まれる複雑な内容だったため、もう少し

簡易的な方法がないかと今回質問した次第です。

Sequence-pairという言葉は知りませんでした。

やはりきちんと計算するとなると、相当ややこしい問題なんですね…。

勉強になりました。ありがとうございます。

2009/06/17 16:52:41

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません