时间戳

首页 > 解决方案 > 用于在 2 个有符号整数区间之间进行除法的 C++ 算法

c++ - 用于在 2 个有符号整数区间之间进行除法的 C++ 算法

问题描述

考虑区间 A = [x1, y1] 和 B = [x2, y2]，这两个区间表示有符号整数。

维基百科上的区间算术页面给出了一个公式来解决B不包含0的情况，其C++实现可能如下：

void print(const char* const what, int x, int y)
{
  std::cout << what << " = [" << x << ", " << y << "]\n";
}

void div(const char* const what, int x1, int y1, int x2, int y2)
{
  int v1 = x1/x2;
  int v2 = x1/y2;
  int v3 = y1/x2;
  int v4 = y1/y2;

  int x = std::min(std::min(v1, v2), std::min(v3, v4));
  int y = std::max(std::max(v1, v2), std::max(v3, v4));

  print(what, x, y);
}

int main()
{
  int x1 = -10000, y1 = 150000;
  int x2 = -10, y2 = 10;

  print("A", x1, y1);
  print("B", x2, y2);

  div("A/B", x1, y1, x2, y2);
}

输出：

A = [-10000, 150000]
B = [-10, 10]
A/B = [-15000, 15000]

正如预期的那样，鉴于 B 包含 0，结果是不正确的。例如，由于 1 是 B 的一部分，因此 150000 应该在 A/B 内，但不是。

当从 B 中排除 0 时，什么是可行的算法？解决方案是否应该在 -1 和 1 附近使用多个间隔（即排除 0）并以某种方式加入它们？

编辑：解决方案可以用 long long 类型的间隔的联合（向量）来表示。

标签： c++mathinterval-arithmetic

解决方案

推荐阅读