0

我有一个代表一个大范围的线性范围列表：

                                          X'
 100    200 300    400 500    600 700     |       900    (X)
|----------|----------|----------|--------+----------|
 0                                        |       100    (Y)
                                          Y'

X 由以下范围组成（偶数和整数只是为了便于理解的示例，它们可以是任何东西，这里根本没有比例）：

  • 从 100 到 200
  • 从 300 到 400
  • 从 500 到 600
  • 从 700 到 900

另一方面，Y 只有一个范围：

  • 从 0 到 100

X 和 Y 的长度相同，只是单位不同。假设一个是美元，另一个是百分比（或任何其他类似不相关的单位）。所以 Y'0 == X'100 和 Y'100 == X'900。

给定 Y 中的任何点，X 中的等价点是什么，反之亦然，给定 X 中的一个点 - Y 中的什么？

这是一道典型的数学题吗？它有名字吗？

4

5 回答 5

2

你有多少个范围？算法为 O（范围数）是否可以接受？

如果是这样，下面是算法的描述。让我在您的（原始）示例中解释一下。

 100    200 300    400 500    600 700    800
|----------|----------|----------|----------|
 0%                                     100%

1）您要做的是将范围A（100-800）中的值X映射到连续范围B（0-399）中的值Y（因为您范围内的元素总数为400）。然后很容易将B中的位置更改为百分比，我将省略这部分。

2）创建记录列表，其中每条记录代表一个范围映射。

struct RangeRecord {
  int start_in_a;
  int start_in_b;
};

在您的情况下，您将获得以下列表：

{100, 0}, {300, 100}, {500, 200}, {700, 300}

3）当您需要将数字 X 从 A 映射到 B 时，您迭代列表以找到 start_in_a <= X 的第一条记录。那么您的值 Y 是

Y = X + start_in_b - start_in_a;

4）算法是对称的，你只需迭代列表以找到 start_in_b <= Y 的第一条记录，然后

X = Y + start_in_a - start_in_b.

注意 1. 出于错误检查的目的，您也可以将范围大小保留在 RangeRecord 中。

注意 2. 如果 O（范围数）不够好，请将记录保留为树而不是列表。然后，您将需要 O(log(number of range)) 操作，

于 2009-06-01T23:37:35.633 回答
0

在从某些 X' 转换为 Y' 时，您需要调整三件事，反之亦然：

  1. 范围从不同的地方开始。
  2. 其中之一是不连续的。
  3. 每个步骤的大小在两个范围之间是不同的。

考虑一个类似的范围 Z 可能会有所帮助（至少在开发您的解决方案时），该范围是 0 到 503 的范围，并且与 X 中的 504 个可能值具有一对一的映射。也就是说，对于每个不连续性，如果 X 值大于不连续的上端，则减​​去 99（不连续的大小）。那么X'100 = Z'0, X'200 = Z'100, X'300 = Z'101, X'400 = Z'201, X'500 = Z'202等。引入Z范围解决了上面列表中的问题 1 和 2。

要将 Z 转换为 Y，您只需乘以 101/504，它将 Z 缩放到 Y。

于 2009-06-01T23:55:24.180 回答
0

假设您有一个范围（a，b）和另一个范围（c，d）。现在你有一个数字 i，它的 a < i < b。您可以通过减去 a 并除以 b - a 来“标准化”它 - 这会给您一个介于 0 和 1 之间的值。然后您可以使用此值通过将此计算与其他边界相反来将其转移到其他范围，因此说把它乘以 (d - c) 并加上 c。

假设另一个范围内的对应点是 i'。然后，

i' = (i - a) / (b - a) * (d - c) + c

您正在搜索的术语是缩放和平移。

于 2009-06-01T23:01:14.757 回答
0

这并不是真正可以解决的，因为问题未得到充分说明。即使对于相同的范围，也可以有不同的滑块，如下所示：

1  100 101       1000
|-----|-----------|

1        100 101 1000
|-----------|-----|

对于每个范围，[1..100]您需要知道滑块上的哪些百分比点与其对应。在上面的示例中，这可能类似于[0%..33%]or [0%..66%]。一旦您获得了这些信息，就很容易确定给定数据点位于哪个范围内以及该范围的哪个位置以及它对应的值。

于 2009-06-01T23:16:33.117 回答
0

假设您暗示的分段线性排列，您可以通过以下方式找到 X：

X = 4*Y + 100*int(1 + Y/25.)

而 Y 则相反：

X2 = int(X/100.)
X3 = X2-int(X2/2.)
Y = (X-100*X3)/4.

编辑：此解决方案适用于您提供的原始范围：

 100    200 300    400 500    600 700    800
|----------|----------|----------|----------|
 0%                                     100%

当然，反向公式仅适用于 X 的有效值。

这是两条曲线的图。绿色是您的原始规格，蓝色是反向曲线（同样，仅对有效的 x 值有效）。 替代文字 http://img523.imageshack.us/img523/8858/66945008.png

于 2009-06-01T23:34:58.650 回答