알고리즘 주어진 원 여기

Question

에 사각형의 수를 찾는 내 도면 사각형은 완전히 그려지고 레고 블록처럼 배치 될 수 있습니다. 어떤 경우에는 정사각형의 꼭지점이 원 위에 놓이게됩니다.

예 : 1-의 경우 0, 2-의 경우 3-16, 4-32의 경우 4-52, 5-52의 경우 4를 제공합니다.

필자는 글을 썼지 만, 5+ (반경이 5보다 큰 경우)에서는 제대로 작동하지 않습니다. 여기에 그것은 간다 : CLICK. 내 코드에서 r은 원의 반지름이고, sum은 모든 제곱의 합이며 height는 피타고라스 정리를 사용하여 원으로 "그려"하려는 삼각형의 높이입니다.

지금 도움이 되셨습니까? 내 알고리즘이 정확합니까? 뭔가 바꿔야 하나?

Answer 1

Gauss's Circle Problem은 주어진 반경의 원 안에 정수 포인트를 계산하는 수식을 제공합니다. 이 논리를 사용하여 서클에있는 사각형을 계산할 수 있습니다.

N = 4 * Sum[i=1..R] (Floor(Sqrt((R^2-i^2))) 

예 :

R = 3 
i=1 n1 = Floor(Sqrt(9-1))~Floor(2.8)=2 
i=2 n2 = Floor(Sqrt(9-4))~Floor(2.2)=2 
i=3 n2 = Floor(Sqrt(9-9))=0 
N=4*(n1+n2+n3)=16 

Answer 2

먼저 오프 - 5의 반경이 60 × 1 사각형이 아닌 52 일 누군가가 포인트 {[(3)을 계산하지 않은 것이 나의 내기에 맞는와 원, 4], [3, -4], [4,3], [4,3], [-4,3], [ 4]} 종이에 그려서 손으로 세는 경우, 그들이 원 위에 있든 아니면 바깥에 있는지 확실하지 않습니다. 그들은 정확하게 원에 있습니다.

두 번째 - MBo의 대답이 나를 데려왔다. 가끔 Gauss Circle Problem 용 StackOverflow를 검색하여 누군가 새로운 재미있는 알고리즘을 제안했는지 확인한다. -

셋째 여기에 코드입니다 :

int  allSquares=0, 
     squaredRadius=radius*radius, 
     sideOfQuarterOfInscribedSquare=(int)(long)(radius/sqrt(2)); 
for(int x=sideOfQuarterOfInscribedSquare+1; 
     x<radius; 
     x++){ 
    allSquares+=(long)sqrt(squaredRadius-x*x); 
} 
allSquares= allSquares*8+4*sideOfQuarterOfInscribedSquare*sideOfQuarterOfInscribedSquare; 
return allSquares; 

무엇 그냥 새겨진 사각형 외부 원의 1/8 내부의 사각형을 계산한다 않습니다. 내 hipster 서식 및 지나치게 자세한 변수 이름을 유감스럽게 생각합니다.