c++ - 找到两个整数，使得它们的乘积接近给定的实数

Question

我正在寻找一种算法来找到两个整数值x,y，以使它们的乘积尽可能接近给定的双精度值，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 的差异也最小的值？

Answer 1

您必须查看相关数字的平方根。对于 21.5 sqrt(21.5) = 4.6368，实际上你找到的数字就在这个值附近。

Answer 2

你想最小化

1. 因子X和Y的差异
2. 乘积X × Y和P的差。

您提供了一个示例，其中这些目标相互矛盾。3 × 7比4 × 5更接近21，但后者的因子更平方。因此，不可能有任何算法同时最小化两者。

您可以加权两个目标并将它们转换为一个，然后通过非线性整数规划解决问题：

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

其中c, d是非负数，用于定义您重视哪个目标。

Answer 3

取平方根，取一个整数，取另一个整数。

#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请注意，这种方法只能在and之间提供一个很好的距离y，例如 if real_value = 10then x=3and y=4，但产品 is 12。如果您想在产品和实际值之间获得更好的距离，您必须调整整数并增加它们的差异。

Answer 4

1. 让给定的 double 为 K。

2. 取K的地板，让它成为F。

3. 取 2 个大小为 F*F 的整数数组。让他们成为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，而差异较小的优先级为 0.5。考虑另一个大小为 F*F 的数组 Ar3。然后，

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

遍历 Ar3 以找到最大值，这将是您正在寻找的对。

Answer 5

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;
    }
}