n개의 서로 다른 노드가 있다고 가정합니다. 모두 다릅니다. 우리는 이진 탐색 트리를 형성하기 위해 그것들을 배열할 수 있는 방법의 수를 찾아야 합니다. 이진 검색 트리에 대해 알고 있듯이 왼쪽 하위 트리에는 항상 더 작은 값이 있고 오른쪽 하위 트리에는 더 큰 값이 있습니다.
이를 해결하기 위해 우리는 카탈로니아 수를 찾을 것입니다. 카탈로니아 숫자 C(n)은 n개의 다른 키를 가진 이진 탐색 트리를 나타냅니다. 공식은 다음과 같습니다.
$$C(n)=\frac{(2n)!}{(n+1)!\times n!}$$
따라서 입력이 n =3과 같으면 출력은 5가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- ncr() 함수를 정의합니다. n, r 이 걸립니다.
- res :=1
- r> n - r이면
- r :=n - r
- 0 ~ r - 1 범위의 i에 대해
- res :=res *(n - i)
- res :=(res/(i + 1))의 바닥
- 반환 결과
- 메인 방법에서 다음을 수행합니다.
- c :=ncr(2 * n, n)
- c /(n + 1)의 바닥 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from math import factorial def ncr(n, r): res = 1 if r > n - r: r = n - r for i in range(r): res *= (n - i) res //= (i + 1) return res def solve(n): c = ncr(2 * n, n) return c // (n + 1) n = 3 print(solve(n))
입력
3
출력
5