태그 보관물: geometry

geometry

대각선 그리드에서 사각형을 계산 이제 그리드의 사각형의 모든 대각선을 가로

이 과제에 대한 후속 조치로서 , 이제 그리드의 사각형의 모든 대각선을 가로 지르는 선이있는 r 개의 행과 c 개의 열이있는 그리드의 사각형 수를 계산하려고 합니다. 이제는 이전과 같은 사각형을 계속 계산하지만 이번에는 45도 기울어 진 사각형도 포함해야합니다.

목표는 행 수 r 과 열 c 에 치수 ( r , c ) 가있는 대각선 그리드의 사각형 수를 출력 하는 함수 또는 프로그램을 만드는 것입니다 .

데모로, 이것은 (2 x 3) 대각선 그리드로 형성된 37 개의 직사각형을 반복하는 애니메이션입니다.

예

테스트 사례

Each case is [rows, columns] = # of rectangles
[0, 0] = 0
[0, 1] = 0
[1, 0] = 0
[1, 1] = 1
[3, 2] = 37
[2, 3] = 37
[6, 8] = 2183
[7, 11] = 5257
[18, 12] = 40932
[42, 42] = 2889558
[51, 72] = 11708274

규칙

  • 이것은 코드 골프 이므로 가장 짧은 코드가 승리합니다.
  • 이를 해결하는 내장은 허용되지 않습니다.

답변

루비, 58 바이트

이것은 Releasing Helium Nuclei의 C answer에 알고리즘을 간단하게 구현 한 것 입니다.

g=->m,n{n>m ?g[n,m]:m*~m*n*~n/4+n*((2*m-n)*(4*n*n-1)-3)/6}

나는이 공식이 왜 효과가 있으며 제한된 성공을 조사하고 있습니다. 똑바로 직사각형 (m+1)*m/2 * (n+1)*n/2의 수가 같다는 것을 쉽게 확인할 수 있으며 대각선 직사각형의 수는 조금 더 애매합니다.

닐했다 확인 을 위해 m==n에 기울어 진 사각형의 수 있다는 n*n광장이입니다 (4*n**4-n*n-3*n)/6것을 할 때 m>n 당신이 추가로 추가해야합니다 (m-n)(n*(4*n*n-1)/3)(관련 OEIS A000447 )이 설명하지 않습니다하지만 그 두 공식 어디에서 왔는지. 나는 대답의 일부를 찾았습니다.

를 들어 m==n, 그리드 내부의 모양은이다 아즈텍 다이아몬드 .

Wolfram Alpha의 Aztec 다이아몬드 이미지

아즈텍 다이아몬드 사각형의 수는 큰 사각형의 수의 합 (a 검색된 제 4 다이아몬드 대하도록 중첩 인 5x5격자 2x8, 4x6, 6x4및 8x2마이너스 사각형의 수)를 계수 배 (개수 이전 Aztec 다이아몬드의 사각형 ).

여기 공식은 다음과 같습니다 (TeX는 나중에 추가됩니다).

# superimposed rectangles, 2x(2n-2), 4*(2n-4), ...
f = lambda n: sum( (2*k)*(2*k+1)/2 * (2*n-2*k)*(2*n-2*k+1)/2 for k in range(1, n) )
aztec_rect = f(n) - f(n-1)

볼프람 알파에 대한 닫힌 형태에 따르면 fIS 1/30*(n-1)*n*(4*n**3+14*n**2+19*n+9)와의 폐쇄 된 형태 aztec_rect닐 발견과 같다, 1/6*n*(n-1)*(4*n**2+4*n+3) == 1/6*(4*n**4-n**2-3*n).

그 이유를 발견 아직 (m-n)(n*(4*n*n-1)/3)내가 한 정의 때문입니다 의심하지만, 작품을 A000447가 있다 binomial(2*n+1, 3). 난 당신이 게시 계속됩니다.

업데이트 : 확장 된 Aztec 다이아몬드의 사각형 수 기능 이 다이아몬드 빼기 m>n의 중첩 된 2k*2(n-k)사각형 수와 관련이 있다고 생각하는 이유 가 있습니다 F(m-1,n-1). 내가 가질 때 더 많은 결과.

업데이트 : 다른 경로를 시도하고 확장 가능한 Aztec 다이아몬드에 대한 또 다른 공식으로 끝났습니다. 주로 설명 할 수는 있지만 아직 이해하지 못하는 용어가 있습니다. 후자! :디

def f(m,n):
 if n > m:
     return f(n,m)
 if n == 0:
     return 0
 else:
     return(m-n+1)*(4*n**4-n*n-3*n)/6-f(m-1,n-1)+(m-n)*2+(m-n)*(n-2)-(m-n-1)*f(n-1,n-1)

마지막 공식에 대한 간단한 분석 :

  • (m-n+1)*(4*n**4-n*n-3*n)/6은 n구조에서 크기가 중첩 된 Aztec 다이아몬드의 수입니다 f(n,n) = (4*n**4-n*n-3*n)/6. f(7,3)5 개의 중첩 된 Aztec 다이아몬드 크기 3를 f(3,3)가지고 있지만, 1 개의 다이아몬드 만 있습니다.
  • -f(m-1,n-1) 겹쳐진 다이아몬드의 중간에서 중복 사각형 중 일부를 제거합니다.
  • +(m-n)*22 개 추가를 차지 2-by- (2n-1)각각 별도의 다이아몬드 사각형.
  • +(m-n)*(n-2)추가를 차지 n-by- n각각 별도의 다이아몬드 광장.
  • -(m-n-1)*f(n-1,n-1)이것은 새로운 수수께끼 용어입니다. 분명히 나는 ​​계산에서 여분의 사각형을 설명하지 않았지만 확장 다이아몬드의 어디에 있는지 알아 내지 못했습니다.

참고 : when m==n, m-n-1 = -1이 마지막 항 은 계산에 제곱을 추가 함을 의미합니다 . 정규식에 무언가가 누락되었을 수 있습니다. 전체 공개, 이것은 방금 작동 한이 공식의 초안에 대한 패치 일뿐이었습니다. 분명히, 나는 아직도 무슨 일이 일어나고 있는지 조사해야하며, 내 공식에는 약간의 버그가있을 수 있습니다. 계속 게시하겠습니다.

Russell, Gary 및 Weisstein, Eric W. “Aztec Diamond” MathWorld–Wolfram 웹 리소스에서. http://mathworld.wolfram.com/AztecDiamond.html

답변

기음, 71 64 바이트

f(m,n){return n>m?f(n,m):m*~m*n*~n/4+n*((2*m-n)*(4*n*n-1)-3)/6;}

Ideone에서 사용해보십시오

답변

파이썬, 73 68 바이트

x=lambda m,n:m*~m*n*~n/4+n*((2*m-n)*(4*n*n-1)-3)/6if m>n else x(n,m)

그리고 다음 버전은 더 높은 바이트 수 (75)를 갖지만 사용 장소를 찾는 데 훌륭한 운동이었습니다 ~.

def f(r,c):
 if r<c:r,c=c,r
 x=(4*c**3-c)/3
 return r*c*~r*~c/4+x*r--~x*c/2

답변

볼록, 37 36 바이트

__:)+×½½\~æ<{\}&:N\¦\-N¦¦N*(*3-N*6/+

온라인으로 사용해보십시오!

스택 기반 언어에 맞게 수정되고 최적화 된 betseg의 알고리즘을 사용합니다. 자유 시간이 더있을 때 올 설명. 나는 이것이 단축 될 수 있다고 확신하지만 현재는 귀찮게하지 않을 것입니다.

답변

배치, 82 바이트

@if %2 gtr %1 %0 %2 %1
@cmd/cset/a%1*~%1*%2*~%2/4+((%1+%1-%2)*(%2*%2*4-1)-3)*%2/6

답변