人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

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

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

●質問者: otobeck
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:C言語 いまいち はてな ソース ドン
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

1 ● kn1967
●27ポイント

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

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

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


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

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

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

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

◎質問者からの返答

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

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

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

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


2 ● つづきはid:yanbeで!
●27ポイント ベストアンサー

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

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

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

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

http://gist.github.com/130568

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

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

◎質問者からの返答

まさしくこれです!

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

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

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

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


3 ● nanoruhodono
●26ポイント

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

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

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

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

◎質問者からの返答

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

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

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

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

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

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ