1

x,y2 つの整数値を見つけて、それらの積が指定された double にできるだけ近く、kその差が小さいアルゴリズムを探しています。

例: 長方形の面積は、k=21.5その長方形のエッジの長さを、整数でなければならないという制約付きで見つけたいと考えています。この場合、可能な解決策のいくつかは (順列を除く)(x=4,y=5)で(x=3,y=7)あり、愚かな解決策です(x=21,y=1)

実際、カップルの場合、カップル(3,7)の場合と同じ違いがあります(21,1)

21.5-3*7=0.5 = 21.5-21*1

(4,5)カップル のために21.5-4*5=1.5

しかし、それらの差が であるため、カップルの(4,5)方が望ましいため1、長方形は「より正方形」になります。

x,y差が最小で、それらの積と k の差も最小である値を抽出する方法はありますか?

4

5 に答える 5

3

問題の数の平方根を見回す必要があります。21.5 sqrt(21.5) = 4.6368 の場合、実際に見つかった数値はこの値のすぐ近くです。

于 2012-11-05T12:20:25.707 に答える
2

最小化したい

  1. 係数XとYの差
  2. 積X × YとPの差。

これらの目的が互いに矛盾する例を示しました。3 × 7は4 × 5よりも21に近いですが、後者の係数はより正方形です。したがって、両方を同時に最小化するアルゴリズムは存在しません。

2 つの目的を重み付けして 1 つに変換し、非線形整数計画法を使用して問題を解くことができます。

       min c × |X × Y - P|  +  d × |X – Y|
subject to X, Y ∈ ℤ
           X, Y ≥ 0

ここで、c、dは、どの目標をどの程度評価するかを定義する負でない数値です。

于 2012-11-05T12:59:12.593 に答える
1

平方根を取り、1 つの整数を床にし、もう 1 つの整数を天井にします。

#include <iostream>
#include <cmath>

int main(){
    double real_value = 21.5;
    int sign = real_value > 0 ? 1 : -1; 
    int x = std::floor(std::sqrt(std::abs(real_value)));
    int y = std::ceil(std::sqrt(std::abs(real_value)));
    x *= sign;

    std::cout << x << "*" << y << "=" << (x*y) << " ~~ " << real_value << "\n";
    return 0;
}

このアプローチでは、 と の間の適切な距離しか得られないことに注意してくださいx。yたとえば、とのreal_value = 10場合ですが、積はです。積と実際の値の間の距離を改善したい場合は、整数を調整して差を大きくする必要があります。x=3y=412

于 2012-11-05T12:20:43.423 に答える
0 
double best = DBL_MAX;
int a, b;
for (int i = 1; i <= sqrt(k); i++)
{
    int j = round(k/i);
    double d = abs(k - i*j);
    if (d < best)
    {
        best = d;
        a = i;
        b = j;
    }
}
于 2012-11-05T12:57:19.727 に答える
0

  1. 与えられた double を K とします。

  2. K の床を取って、それを F とします。

  3. サイズ F*F の 2 つの整数配列を取ります。Ar1、Ar2とする。

  4. このようにループを実行します

    int z = 0 ;

for ( int i = 1 ; i <= F ; ++i )
{
   for ( int j = 1 ; j <= F ; ++j )           
   {
       Ar1[z] = i * j ;
       Ar2[z] = i - j ; 
       ++ z ;            
   }
}

これで、考えられるすべての数の差/積のペアが得られました。次に、値 K に近い製品に「優先値」を割り当て、差が小さいものに他の値を割り当てます。これらの配列を 0 から F*F までトラバースし、条件を確認して必要なペアを見つけます。

たとえば。K に近いほど優先順位が 1 で、差が小さいほど優先順位が .5 であるとします。サイズ F*F の別の配列 Ar3 を考えてみましょう。それで、

    for ( int i = 0 ; i <= F*F ; ++i )
    {
       Ar3[i] = (Ar1[i] - K)* 1 + (Ar2[i] * .5) ; 
    }

Ar3 をトラバースして、探しているペアとなる最大値を見つけます。

于 2012-11-05T12:43:51.390 に答える