0

假设一个人想要搜索满足某个等式的整数对 x 和 ya，例如（在我的脑海中）7 x^2 + xy - 3 y^2 = 5

（我知道有非常有效的方法可以找到这样的二次方程的整数解；但这与本问题的目的无关。）

显而易见的方法是使用一个简单的双循环“for x = -max to max; for y = -max to max { blah}” 但是为了允许停止和恢复搜索，更方便的方法是描绘可能的整数x 和 y 作为平面中点的方格，是从原点向外围绕“方形螺旋”工作，在（例如）右上角开始和停止。

所以基本上，我要求一个简单而合理的“伪代码”用于循环分别在点 (m, m) 和 (n, n) 开始和停止这个过程。

对于额外的荣誉，如果读者倾向于，我建议如果 x 之一可以假设为非负数，或者两者都可以假设为非负数，我建议也提供循环。这可能更容易一些，尤其是第二个。

我可以毫不费力地自己解决这个问题，但我有兴趣看到其他人的巧妙想法。

对于那些喜欢用白板折磨候选人的可怕面试官来说，这将是一个很好的“建设性”面试挑战；-)

4

2 回答 2

0 
def enumerateIntegerPairs(fromRadius, toRadius):
    for radius in range(fromRadius, toRadius + 1):
        if radius == 0: yield (0, 0)
        for x in range(-radius, radius): yield (x, radius)
        for y in range(-radius, radius): yield (radius, -y)
        for x in range(-radius, radius): yield (-x, -radius)
        for y in range(-radius, radius): yield (-radius, y)
于 2012-06-23T20:51:50.033 回答
0

这是一个简单的实现（也在ideone上）：

void turn(int *dr, int *dc) {
    int tmp = *dc;
    *dc = -*dr;
    *dr = tmp;
}
int main(void) {
    int N = 3;
    int r = 0, c = 0;
    int sz = 0;
    int dr = 1, dc = 0, cnt = 0;
    while (r != N+1 && c != N+1) {
        printf("%d %d\n", r, c);
        if (cnt == sz) {
            turn(&dr, &dc);
            cnt = 0;
            if (dr == 0 && dc == -1) {
                r++;
                c++;
                sz += 2;
            }
        }
        cnt++;
        r += dr;
        c += dc;
    }
    return 0;
}

实现中的关键是turn函数，它在给定一对{delta-Row, delta-Col}. 剩下的就是简单的算术。

于 2012-06-23T21:22:16.090 回答