找到两个整数，使它们的乘积接近给定的实数。
找到两个整数，使它们的乘积接近给定的实数。
提问于 2012-11-05 12:16:17
我正在寻找一种算法来找到两个整数值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的差也很小？
回答 5
Stack Overflow用户
发布于 2012-11-05 12:20:25
你必须看看这个数字的平方根。对于21.5sqrt( 21.5 )= 4.6368，实际上您找到的数字就在这个值附近。
Stack Overflow用户
发布于 2012-11-05 12:59:12
你想要最小化
- 因子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是非负数，它定义了你所看重的目标。
Stack Overflow用户
发布于 2012-11-05 12:20:43
取平方根，地板一个整数，另一个整数。
#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=3和y=4，但是产品是12。如果您想要在产品和实际值之间取得更好的距离，就必须调整整数并增加它们之间的差异。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/13231940
复制相关文章
相似问题
腾讯云开发者
