java - 画面の最大平方を計算する

Question

重複の可能性:
正方形を長方形に詰め込む

画面を埋める最も効率的な正方形のサイズを計算する必要があります。

下の画像を見ると、さまざまな画面サイズと平方数があります。画面を最も効率的に埋めるx 軸の正方形数と y 軸の正方形数を計算するアルゴリズムが必要です(正方形で塗りつぶした後に最小の空き領域が残ります)。

以下の投稿を見ましたが、私の質問を解決する答えではありません

1 - 正方形の数を変更できます (3-5-10 など...)

2 - 画面サイズは異なる場合があります

例えば、

** 正方形の幅を計算するアルゴリズムが必要です (高さは幅と同じです) **

画像 3 と画像 3-1 の違いを見ると、画像 3-1 の方が未使用領域が少ないため、画面をより効果的に使用していることがわかります。

画像3

または、これは埋めるためのより良い方法かもしれません：

画像 3-1

画像 3-1

画像 4 と画像 4-1 の違いを見ると、画像 4-1 の方が未使用領域が少ないため、画面をより効果的に使用していることがわかります。

画像4

** 4. 画面の未使用領域が少ないため、画像は次のようにする必要があります **

画像 4-1

score 1 · Accepted Answer

「効率的」という言葉であなたが示唆しているのは、四角で覆われた面積が大きいほど良いということだと思います。

させて：

a : x 軸の平方数

b : y 軸の平方数

s : 正方形の大きさ（一辺の長さ）

w : 画面の幅

h : 画面の高さ

c : 配置する正方形の数

それから私たちは持っています

a * s <= w
b * s <= h
a * b >= c

これらの不等式を使用して、s の上限を見つけることができます。c = 20、w = 1280、h = 800 の 4 番目の例を調べると、

a * s <= 1280
b * s <= 800
a * b >= 20

a * b = (1280 / s) * (800 / s) >= 20 ---> s^2 <= (1280*800) / 20 ---> s <= 226,27..

s の上限により、a と b を次のように推定できます。

a * s <= 1280 ---> a ~= 5,6568 b * s <= 800 ---> b ~= 3,53

これらの値では、不等式 a * b >= 20 は成立しません。

ただし、a と b は両方とも整数でなければなりません。次に、a と b が取得できる 4 つの可能性を試します。

a = 5, b = 3 // round down both
a = 5, b = 4 // one down, one up
a = 6, b = 3 // one down, one up
a = 6, b = 4 // round up both

a * b >= 20 であるため、最初と 3 番目のケースは除外され、有効な答えになります。次のステップとして、a = 5、b = 4 の答えを選択します。これは、その積が目的の正方形数により近いためです。

score 0 · Accepted Answer

探しているのは、ディスプレイの幅と高さの最大公約数です。

ほとんどのディスプレイの比率は4：3または16：9であるため、最大公約数により、ディスプレイ領域を埋めるために使用できる最大の正方形が得られます。

400 x 400ピクセルのディスプレイでは、最大公約数は400であり、1つの正方形がディスプレイを埋めます。

1280 X 800ピクセルのディスプレイでは、最大公約数は160です。ディスプレイを埋めるには40個の正方形（8 x 5）が必要です。

すべてのディスプレイサイズの最大公約数を計算する場合、答えは1です。すべてのピクセルは正方形です。サポートするディスプレイサイズごとに、個別の最大公約数を計算する必要があります。

2 に答える 2