私の状況
- 私はN個の長方形を持っています
- 長方形はすべて同じ形状です（たとえば、幅2インチx高さ1インチ）-幅と高さについては、このサイズをSwおよびShと呼びましょう。
- これらの長方形をグリッドに配置して、スプレッドシートに表示されるように、長方形が完全に上下に隣接するようにします。
- 私が必要としているのはこれです：N、Sw、Shが与えられた場合、これらの長方形を可能な限り最も正方形のような配置に積み重ねる行（R）と列（C）の数はいくつですか。
- R＆Cは、必要以上のセルを提供する可能性があることを理解しています（たとえば、N = 15、Sw = 1、Sh = 1の場合、R = 4、C = 4の場合、15個の長方形に対して16個の「スロット」が生成されます。これで問題ありません。
- Sw = Shの場合、私の謙虚な数学のスキルで十分です-長方形の幅と高さが異なる場合-率直に言って、それは私を超えています。
いくつかの注意事項
- はい、私はこの質問を読みました：長方形を積み重ねてスペースをできるだけ少なくし、いいえ、それは役に立ちませんでした。また、それは同じ質問ではありません。その質問は、サイズが異なる可能性のある長方形に関するものです。この質問では、長方形のサイズは同じです。
- はい、wolfram.comなどで検索しましたが、運がありません。
- 私は数学のバックグラウンドがないので、この問題の言い回し自体が答えを見つけるのを妨げている可能性があります-タイリング、解剖、分解に関連する検索を試しましたが、そこでも成功しませんでした
いくつかの例
the * indicates the edges of the rects
the | indicates that a cell is "filled-in"
Notice that not all R*C cells are filled in, but only and exactly N cells
IF N=1, Sw=2, Sh=1 THEN R=1, C=1
********
*||||||*
********
IF N=2, Sw=2, Sh=1 THEN R=2, C=1
********
*||||||*
********
*||||||*
********
IF N=3, Sw=2, Sh=1 THEN R=2, C=2
***************
*||||||* *
***************
*||||||*||||||*
***************
IF N=4, Sw=2, Sh=1 THEN R=2, C=2
***************
*||||||*||||||*
***************
*||||||*||||||*
***************
IF N=5, Sw=2, Sh=1 THEN R=3, C=2
***************
*||||||* *
***************
*||||||*||||||*
***************
*||||||*||||||*
***************
AaronofTomorrowの回答の実装
# Implementation of AaronofTomorrow's answer
# implemented in python 2.6
# reasonable output
# works in constant time
import math
def f( N, Sw, Sh ) :
cols = math.sqrt( float(N) * float(Sh) / float(Sw) )
cols = round(cols)
rows = float(N) / float(cols)
rows = math.ceil(rows)
return (int(cols),int(rows))
ウィルの答えに触発された別の実装（2008年12月8日に更新）-これは私が最終的に使用したものです
# Another implementation inspired by Will's answer
# implemented in python 2.6
# reasonable output - a bit better in yielding more squarelike grids
# works in time proportional to number of rects
#
# strategy used it to try incrementaly adding a rect.
# if the resulting rect requires more space then two
# possibilities are checked - adding a new row or adding a new col
# the one with the best aspect ratio (1:1) will be chosen
def g( N, Sw, Sh ) :
slope = float(Sh)/float(Sw)
cols = 1
rows = 1
for i in xrange( N ) :
num_to_fit =i+1
allocated_cells= cols* rows
if ( num_to_fit <= allocated_cells ) :
pass # do nothing
else :
hc,wc = float(Sh * rows), float(Sw * (cols+1))
hr,wr = float(Sh * (rows+1)), float(Sw * cols)
thetac = math.atan( hc/wc)
thetar = math.atan( hr/wr)
alpha = math.pi/4.0
difr = abs(alpha-thetar)
difc = abs(alpha-thetac)
if ( difr < difc ) :
rows = rows +1
else:
cols = cols + 1
return (cols,rows)