は、このようなダイヤモンドのシリーズを考えるとダイヤモンド

Question

の周囲上のすべての点を生成しますか？赤い四角形が{0、0}にあり、黒い四角形の座標がそれに関連して与えられているとします。

0 = {0, 0} 
1 = {-1, 0}, {0, -1}, {0, 1}, {1, 0} 
2 = {-2, 0}, {-1, -1}, {-1, 1}, {0, -2}, {0, 2}, {1, -1}, {1, 1}, {2, 0} 
3 = {-3, 0}, {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {0, -3}, {0, 3}, {1, -2}, {1, 2}, {2, -1}, {2, 1}, {3, 0} 

観測（所与nは原点から隅までの距離である）：指定されたダイヤモンドの例

• 各座標対の合計は常にNまたは-Nです。
• 0を除いて、リストのサイズは常に4nです。
• | x | + | y | = nは、ダイヤモンドのデカルト方程式です。

最後に、私はC言語で以下の解決策を発見しました。しかし、比較と2回のabs（）呼び出しではO（n^2）時間です。はるかに大きなダイヤモンドに適したより高速なソリューションはありませんか？

void diamond_points(int n) { 
    for (int x = -n; x <= n; ++x) { 
     for (int y = -n; y <= n; ++y) { 
      if (abs(x) + abs(y) == n) { 
       printf("{%d, %d}, ", x, y); 
      } 
     } 
    } 
} 

Answer 1

ありマイクロ最適化のビットは、O（N）

for(int x = -n; x <= n; x++) { 
    int y = n - abs(x); 
    printf("{%d, %d}, ", x, y); 
    if(y > 0) { 
     printf("{%d, %d}, ", x, -y); 
    } 
}