5

我刚刚在准备考试时遇到了一个考试问题，我被困住了。问题是：

设计一个算法，给定一组正整数 X，确定方程 x 5 + xy - y 2 = y 3是否具有 x 和 y 都属于 X 的解。

不涉及编程，只是算法设计。有人可以分享他们的想法吗？

暴力是不可接受的

4

4 回答 4

2

伪代码：

result = false
foreach (x in X) {
    foreach (y in X) {
        if (x^5 + x*y - y^2 == y^3) result = true
    }
}

是否比预期的更复杂？如果是这样，可以像这样利用高阶项x^5：

Sort X as a list from least to greatest.
result = false
foreach (y in X) {
    v = y*y*(y+1)
    foreach (x in X) {
        x2 = x*x
        u = x2*x2 + x*y - v
        if (u == 0) {
            result = true
            goto [DONE]
        }
        if (u > 0) goto [NEXT]
    }
    [NEXT]
}
[DONE]
于 2012-04-25T02:37:23.613 回答
2

对于（真的！）大量输入，您可以：

  1. 对列表进行排序；
  2. 使用公式求解每个数字的三次方程。这里假设每个数都是x，所以方程变成了 的三次方程y，那么公式是适用的。然而，这个公式可能需要很长时间，为了避免可能的精度问题，您可以插入答案来检查它。然后对排序列表（O（logn））进行二进制搜索。

这将渐近 O(nlogn)，但常数因素是可怕的，并且被大哦很好地隐藏了（好吧，如果你正在回答问题，而不是编写程序）。当然，如果允许散列（这通常是面试的情况，但不一定是考试），这可能是 O(n)。

于 2012-04-25T02:39:44.093 回答
2

求解 y 作为 x 的函数：http ://www.wolframalpha.com/input/?i=x%5E5%2B+xy+-+y%5E2+-+y%5E3

y(x) := INSERT_EQUATION_HERE
any((y in setX) for y in y(x) for x in setX)

这需要 O(|X|)，即线性时间。

或者，如果您没有使用具有any函数或列表操作的语言，那么您的解决方案必须更加冗长：

for x in setX:
    possibleYs = solveForY(x)
    for y in possibleYs:
        if y in setX:
            return SOLUTION:(x,y)
return NO_SOLUTION

您实际上不必像我上面展示的那样求解 2D 多项式。相反，您可以考虑集合中的每个 x；这修复了 x 并为您提供了 y 中的多项式。然后，您在恒定时间内求解该多项式。例如，如果 x=0，我们会找到 y^2==y^3 的 3 个解；如果 x=1，我们会找到 2-y^2==y^3 的 3 个解决方案，如果 x=-0.52，我们会等等。解决方案是http://en.wikipedia.org/wiki/ Cubic_function#General_formula_of_roots

问题的更一般版本：

如果您考虑任意多项式，请注意此方法只能在以下情况下提供 O(1) 效率：min(max_x_degree, max_y_degree)<5。这是因为，正如伽罗瓦理论所证明的那样，唯一具有某些封闭形式解的多项式是 4 次或更小的多项式。而在这个问题中，我们可以把度数最高的变量变成一个常数。

这并不是说在 min(max_x_degree, max_y_degree)<5 的情况下，不能通过其他方法获得 O(1) 效率。

如果增加变量的数量，事情也会变得更有趣。

于 2012-04-25T02:40:56.137 回答
0

如果集合 X 不是很大，那么简单的蛮力算法可以通过构造 2D 矩阵来工作。

于 2012-04-25T02:41:34.930 回答