符合比例的最小尺寸

Question

我需要找到与某个值完全相等（或在0.001内）的长宽比的最小尺寸。有没有快速的数学技巧或框架技巧可以做到这一点？

这是我目前想到的一个效率不高的解决方案的伪代码，时间复杂度为O(n^2)：

epsilon = 0.001;

from x = 1 to MAX_X
{
  from y = 1 to MAX_Y
  {
    if(Abs(x / y - aspectRatio) <= epsilon)
    {
      return new Size(x, y);
    }
  }
}
return Size.Empty;

- TheCloudlessSky

---

为什么要使用 Abs(..)？这个数字从来不会是负数... - Abel

基本上，您想找到十进制值的最小分数（=最小宽高比）。我确定这是GCSE数学问题，但现在我实际上不记得了，哈哈。 - Codesleuth

首先，我认为你的伪代码是错误的，除非我误解了它，因为它从未涉及到一个纵横比值。 - Jimmy Hoffa

仔细看来，您正在寻找一个等于 0.001 的分数（例如，x = 1，y = 1000）。但根据您的描述，我想您有一个比率，比如 3.8，并找到等于该比率的 x 和 y，即 x = 38，y = 10（假设只需要整数），最大偏差为 epsilon（即 38001 和 1000 也是一个好答案）。这正确吗？如果是这样，一个问题是偏差不是相对于因子的。我认为它应该是一个百分比。 - Abel

Answer 1

这是一个不寻常的问题。要解决它，你需要找到最大公约数并将宽度和高度除以它。该算法由欧几里得发明，已有两千三百年历史。详情可以参见这里。

- Hans Passant

---

什么值的最大公约数？宽度和高度吗？ - TheCloudlessSky

Answer 2

一种更快的方法，但仍不是公式化的方法是仅查看可能的y值，而不是迭代到MAX_Y。例如：

    static Size FindMinSize(double requiredRatio, double epsilon)
    {
        int x = 1;
        do
        {
            int y = (int)(x * requiredRatio);
            if (Test(x, y, requiredRatio, epsilon))
            {
                return new Size(x, y);
            }

            y = (int)((x + 1) * requiredRatio);
            if (Test(x, y, requiredRatio, epsilon))
            {
                return new Size(x, y);
            }
            x++;
        } while (x != int.MaxValue);

        return new Size(0, 0);
    }

    static bool Test(int x, int y, double requiredRatio, double epsilon)
    {
        double aspectRatio = ((double)y)/x;
        return Math.Abs(aspectRatio - requiredRatio) < epsilon;
    }

- Mike

Answer 3

不要测试所有可能的组合，只需增加能让你更接近纵横比的一侧：

public static Size GetSizeFromAspectRatio(double aspectRatio) {
  double epsilon = 0.001;
  int x = 1;
  int y = 1;
  while (true) {
    double a = (double)x / (double)y;
    if (Math.Abs(aspectRatio - a) < epsilon) break;
    if (a < aspectRatio) {
      x++;
    } else {
      y++;
    }
  }
  return new Size(x, y);
}

- Guffa

Answer 4

你可以将 aspectRatio 写成一个分数（如果你想精确到 0.001，那么可以使用 round(aspectRatio,3)/1000）

然后，简化这个分数。得到的分数就是你要找的 x/y。

- Ofri Raviv

---

这并不一定会得到最小的结果。例如，对于 aspectRatio=0.3333333，你会四舍五入为 333/1000，但无法简化它。然而，1/3 是更好的解决方案。 - stevemegson

@steve - 是的，这就是我在测试他的想法时遇到的问题。 - TheCloudlessSky

Answer 5

长宽比是x和y之间的比率。您可以将长宽比定义为x / y或y / x。

最小长宽比为0/0。

必须定义其他一些最小值，包括最小x或最小y。

最小x =（最小y * x）/ y

最小y =（最小x * y）/ x

- Gilbert Le Blanc

---

我认为你需要寻找的重点是他想要产生宽高比值（参见问题中使用的“Size”）的最小整数。 - Codesleuth

“0 / 0” 对我来说看起来像是除以零的错误;) - PeterK