时间戳

首页 > 解决方案 > 如何最小化两个整数，使它们的乘积小于某个值？

pixel - 如何最小化两个整数，使它们的乘积小于某个值？

问题描述

给定两个整数，我怎样才能最小化它们，使它们的乘积小于其他值，同时保持它们的相对比率？

那是形式问题。实际问题是这样的：我的宽度/高度像素分辨率包含随机值（任一维度从 1 到 8192）。我想调整成对的值，使其乘积不超过某个像素总数（例如：1000000），并且我需要确保调整后的分辨率的纵横比保持不变（例如：1.7777）。

天真的方法是运行一个循环，每次我从宽度中减去 1，调整高度以匹配纵横比，直到它们的乘积低于阈值。前任：

int wid = 1920;
int hei = 1080;
float aspect = wid / (float)hei;
int maxPixels = 1000000;
while (wid * hei > maxPixels)
{
    wid -= 1;
    hei = wid / aspect;
}

当然，对于这个问题，必须有一种更具分析性的方法吗？

标签： pixelresolutionsquare

解决方案

编辑：误读了原始问题。

另一种表达你的问题的方法是用 aW和H什么是最大的a，b这样你a/b = W/H的限制在a*b < C哪里。C

为此，求 和 的最大公约数D = gcd(W,H)或最大公约数。最大公分母通常使用欧几里得算法找到。WH

设置x = W/D和y = H/D，这是具有相同比率的最小解。

要在 下产生最大值C，请从不等式开始，F*x*F*y <= C其中 F 将是我们的比例因子x和y

代数：

F^2 <= C/(x*y)

F <= sqrt(C/(x*y))

由于我们希望 F 是一个整数并且严格小于上述值，

F = floor(sqrt(C/(x*y)))

这将为您提供一个新的解决方案A = x*F以及B = y*FwhereA*B < C和A/B = W/H.

推荐阅读