1

整数の面積 A が与えられたとき、w*h = A で w+h ができるだけ小さくなるように、長方形の整数の辺 w と h をどのように見つけることができますか? 私はアルゴリズムが効率的であるよりも単純であることを望みます (合理的な効率の範囲内ではありますが)。

これを達成するための最良の方法は何ですか？

A の素因数を見つけて、w と h のバランスを取ろうとする何らかの方法でそれらを組み合わせますか? A に最も近い面積を持つ整数の辺を持つ 2 つの正方形を見つけて、それらの間を何らかの方法で補間しますか? 私が考えていない他の方法はありますか？

4

2 に答える 2

2

あなたはただ見つける必要があります：

  • sqrt(A) より大きくない A の最大因数、および
  • sqrt(A) 以上の A の最小因数

2 つの積は常に A であるため、これらの係数はあなたwのh

そしてもちろん、それらの 1 つを検索するだけで済みwます。h = A / w

于 2012-06-02T10:38:25.460 に答える
1

ここに私の頭から離れた何かがあります、

皮切りにw=1; h=A;

次に、 を繰り返してw増やします。が増加するたびにw、 まで減少hしてみてくださいw*h>A。また、aw/h-combination のサイズを決定するある種のヒューリスティック関数が必要になります。と呼びましょうsize(x,y)。

各ステップで、これまでに遭遇したおよびの最適な値であるsize(w,h)<size(bestW,bestH)かどうかを確認する必要があります。bestWbestHwh

の実装に関する限り、次のsize(x,y)ことができますreturn x+y。return Math.abs(x-y)

>=wまで増加し続ける必要があるため、最初は複雑さが次の行に沿ったどこかにあると思いますwhh=AO(A/2) <= true complexity <= O(2A)

そして今、いくつかの擬似コードに：

w=1;
h=A;

bestW=w;
bestH=h;

while(2*w<=A){
    w++;
    while(w*h>A) {
        h--;
    }
    if(w*h==A && size(w,h)<size(bestW,bestH)){
        bestW=w;
        bestH=h;
    }
}
于 2012-06-02T09:54:59.393 に答える