找到两个整数，使他们的产品接近给定的真实
我正在寻找一种算法来找到两个整数值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的差异也是最小的？
您必须查看相关数字的平方根。 对于21.5 sqrt（21.5）= 4.6368，实际上你找到的数字就在这个值附近。
你想最小化
- 因子X和Y的差异
- 产品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是非负数，用于定义您评估的目标值。
取平方根，一个整数，另一个整数。
#include #include 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=3且y=4 ，但乘积为12 。 如果你想在产品和实际价值之间取得更好的距离，你必须调整整数并增加它们的差异。
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; } }
-
让双给K.
-
从K楼开始，让它成为F.
-
取两个大小为F * F的整数数组。 让他们成为Ar1，Ar2。
-
像这样运行循环
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的arraysAr3。 然后，
for ( int i = 0 ; i <= F*F ; ++i ) { Ar3[i] = (Ar1[i] - K)* 1 + (Ar2[i] * .5) ; }
遍历Ar3以找到最大值，这将是您正在寻找的对。