내가 방법을 쓸 필요 라이더

Question

2 XN 어레이를 채우기 도미노 블록으로 보드를 채울 수있는 방법을 찾을 수 있습니까?

(각 도미노는 접촉하고 대각선이 아닌 2 개의 셀을 채 웁니다.)

내가 어떻게 재귀를 사용하기로되어있어이하지만 난 어쩌면 그냥 할 수있는 방법이 있다는 것을 hink

:

return(some sort of combinatorics formula) 

이것에 대한 공식이있다?

감사합니다.

Answer 1

이것은 간단한 반복 방법으로 수행 할 수 있습니다. T(n)은 2 x n 보드를 채울 수있는 방법의 수라고 가정합니다.

이제 가장 왼쪽 상단의 셀을 고려해보십시오. 이것을 다루는 도미노는 2 가지 방법으로 지향 될 수 있습니다. 그 도미노 수평 때문에

1) 수평 2)

세로

케이스 (1)는, 아래의 셀은 가로 도미노 의해 채워 져야. 그 후에, T(n-2) 방법으로 채울 수있는 2 x (n-2) 보드가 남아 있습니다.

두 번째 경우에는 T(n-1) 개의 방법으로 채울 수있는 2 x (n-1) 보드가 남아 있습니다.

는 따라서 2 × N 보드 충전 방식의 총 수

T(n) = T(n-1) + T(n-2)이고베이스 케이스 (1) = 1을 쉽게 확인할 수있는 T이다.

닫힌 폼 솔루션을 가진 기본적으로 피보나치 재발입니다.