考虑区间 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 类型的间隔的联合(向量)来表示。