0

(私の頭のてっぺんから) 7 x^2 + xy - 3 y^2 = 5 などの方程式を満たす整数 x と ya のペアを検索したいとします。

（そのような二次方程式の整数解を見つけるための非常に効率的な方法があることは知っていますが、これは現在の質問の目的には関係ありません。）

明らかなアプローチは、単純な二重ループを使用することです「for x = -max to max; for y = -max to max { blah}」しかし、検索を停止して再開できるようにするために、可能な整数を描く、より便利なアプローチ平面内の点の正方格子としてのxとyのは、原点から外側に向かって「正方螺旋」を一周し、（たとえば）右上隅で開始および停止します。

したがって、基本的には、ループがそれぞれポイント (m, m) と (n, n) でこのプロセスを開始および停止するためのシンプルで健全な「疑似コード」を求めています。

追加の称賛として、読者が傾いている場合は、x の 1 つが非負であると想定できる場合、または両方が非負であると想定できる場合は、ループも提供することをお勧めします。これはおそらく多少簡単です。特に 2 番目の方法です。

私はこれを難なく自分で作ることができましたが、他の人の素晴らしいアイデアを見ることに興味があります.

これは、候補者をホワイト ボードで拷問するのが好きな恐ろしい面接担当者にとって、非常に優れた「建設的な」面接課題となります ;-)

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 に答える