找到所有的對，使得x^2 + Y^2 = <N^2

Question

我試圖寫C中的算法，該算法對於給定的自然數n會發現對(x,y)其中x,y是整數的數目，使得

X + Y < = N

我能夠用兩個for循環要做到這一點，但是，這似乎是次優。對這個問題最有效的方法是什麼？

Answer 1

只需要找到邊界處的點，即對於每個給定的x，最大的y_max s.t. x^2 + y_max^2 < = n。那麼給定x的有趣對的數量是2 * y_max + 1。對於x = 0，我們有y_max = n。對於x> 0，我們還必須考慮具有-x的對。這導致下面的代碼：

int pairCnt = 2*n+1; /* pairs (0,-n), (0,-n+1), ..., (0,n) */ 
int n2 = n*n; 
for (int x=1; x<=n; ++x) 
{ 
    int y_max = (int)sqrt(n2-x*x); 
    pairCnt += 2*(2*y_max+1); /* (+/-x,-y_max), ..., (+/-x,y_max) */ 
} 

使用SQRT的可以用下列的算法來避免：

int pairCnt = 2*n+1; /* pairs (0,-n), (0,-n+1), ..., (0,n) */ 
int n2 = n*n; 
for (int x=1, y_max=n; 1; ++x) 
{ 
    if (y_max*y_max > n2-x*x) 
    --y_max; 
    if (x > y_max) break; 
    pairCnt += 2*(2*y_max+1); /* (+/-x,-y_max), ..., (+/-x,y_max) */ 
} 
int s = 2*x-1; /* side length of maximal inscribed square */ 
pairCnt = 2*pairCnt - s*s; 

用於第二算法的第一個想法是，當x增加Y_MAX將最大限度通過減少1，只要y_max> x（即我們沿半徑爲n的圓的內部從（0，n）直到我們穿過第一個中值y = x）。當我們添加一個以90°爲單位的計數點的副本（即迄今爲止發現的點數的兩倍）時，我們將對最大內切方格內的點進行兩次計數。

下面是n = 3的一種可視化。 *將標記對置於有趣集合之外（x*x+y*y > n*n=9）。數字標記了有趣集合（x*x+y*y <= n*n=9）內的對的頻率到目前爲止。

before loop after loop after doubling result 
    ----   ----   ----   ---- 
    4321

4 ********* ********* *********  ********* 
3 ****1**** ****1**** ****1****  ****1**** 
2 **00100** **11111** **22222**  **11111** 
1 **00100** **11111** **22222**  **11111** 
0 *0001000* *0111110* *1222221*  *1111111* 
-1 **00100** **11111** **22222**  **11111** 
-2 **00100** **11111** **22222**  **11111** 
-3 ****1**** ****1**** ****1****  ****1**** 
-4 ********* ********* *********  ********* 

Answer 2

你不需要兩個循環。只需循環x，然後就可以計算出y，因爲x和n都是已知的。

Answer 3

如果你實現一個函數int int_sqrt (int n)，它返回sqrt(double n)的整數部分，那麼你可以通過使用這個函數只用一個循環來處理它。但整數平方根只存在於C++，所以你必須通過強制轉換結果，以實現一個在C int

編輯： 這裏的想法：

int x=0,result=0; 
while ((n-(x*x)) >=0){ 
    result += int_sqrt (n-(x*x)) +1; 
    x++; 
} 

這是在你接受所有的情況下，整數，包括0，使你的夫婦。