我出一个题目，大家看能不能做出来

BingbingNorth

在一平面直角坐标系上，有一个以原点为圆心，以n（n是大于1的整数）为半径的圆，求一算法，输入为半径大小，输出为在圆内的横纵坐标均为整数的点的个数。
这是某年的研究生面试题，看看谁能给出效率较高的算法。

蓝色键盘

几何都忘完了，呵呵

hzhrh

应该是排列组合的题，结果应该是：2^(n-1)*4+4*n+1

oh，是圆内，那应该把圆周上的点去掉：
2^(n-1)*4+4*（n-1）+1

syl80kk

偶，数学的不懂，看来不行了！！！

lenovo

原帖由 "hzhrh" 发表：
应该是排列组合的题，结果应该是：2^(n-1)*4+4*n+1

oh，是圆内，那应该把圆周上的点去掉：
2^(n-1)*4+4*（n-1）+1

怎么算出来的？

hzhrh

排列组合的题啊，我已经毕业了快10年了，但是应该不会错的。

BingbingNorth

看了hzhrh的解法我感到有点不理解，我觉得是不能通过公式推出来的，必须要经过计算才行，否则就不用编程序了。您能证明那个公式吗？
我的题原来是包含圆上的点的，不过解法大致相同，能做出一种来，另一种也就迎刃而解了。我以前想出了一个比较简单的算法，不过比起hzhrh的解法来说就要难得多，需要经过大量的计算，现在我也没有现成的解法，清容我想一阵子再给出。

hzhrh

2^(n-1)*4+4*（n-1）+1中：
2^(n-1)*4是圆内并且不包括坐标上的。
4*（n-1）是坐标上并且不包括原点的点。
1：是原点。

hzhrh

这是某年的研究生面试题，看看谁能给出效率较高的算法。
当某人去面试时难道还拿个电脑写程序？
先计算出1/4圆内的不包括坐标上的点数：2^(n-1)
再计算出坐标上不包括原点的点：4*(n-1)

这样，总点数就是：2^(n-1)*4+4*（n-1）+1

bjf

int test( int r )
{
    int i,j;
    int count=0;

    for(i=-1*r+1; i<r; i++)
        for(j=-1*r+1; j<r; j++)
           if(i*i+j*j >; r*r)
               count++;
    return count
}