algorithm
카탈로니아 어 숫자 알고리즘
수색…
카탈로니아 어 수 알고리즘 기본 정보
카탈로니아 어 숫자 알고리즘은 동적 프로그래밍 알고리즘입니다.
조합 수학에서 카탈로니아 어 수 는 다양한 계산 문제에서 발생하는 자연 수열의 시퀀스를 형성하며 종종 재귀 적으로 정의 된 개체가 포함됩니다. 음수가 아닌 정수 n에있는 카탈로니아 어 숫자는 '다른 방향을 개별적으로 계산하면 정규 n-gon을 n-2 삼각형으로 몇 가지 방법으로 분할 할 수 있습니까?'라는 트리 열거 형 문제에서 발생하는 숫자 집합입니다.
카탈로니아 어 수치 알고리즘의 응용 :
- 아래쪽 열에 동전을 쌓을 수있는 방법의 수는 동전을 n 개의 연속 동전으로 구성하여 하단 동전의 양면에 동전을 넣지 않고 모든 추가 동전을 두 개의 다른 동전 위에 올려 놓아야합니다. n 번째 카탈로니아 어 번호.
- n 개의 쌍의 괄호를 그룹화하는 방법의 수는 각 열린 괄호가 일치하는 닫힌 괄호를 갖도록 n 번째 카탈로니아 번호입니다.
- 교차점이 아닌 직선으로 꼭지점을 연결하여 비행기의 n + 2면 볼록 다각형을 삼각형으로 자르는 방법은 n 번째 카탈로니아 어 수입니다. 오일러가 관심을 보인 어플리케이션입니다.
0부터 시작하는 번호 매기기를 사용하여 n 번째 카탈로니아 번호는 다음 방정식에 따라 이항 계수로 직접 표시됩니다.
카탈로니아 어 번호의 예 :
여기서 n = 4의 값입니다. (가장 좋은 예 - Wikipedia에서)
보조 공간 : O(n)
시간 복잡도 : O(n^2)
C # 구현
public class CatalanNumber
{
public static int Main(int number)
{
int result = 0;
if (number <= 1) return 1;
for (int i = 0; i < number; i++)
{
result += Main(i)*Main(number - i - 1);
}
return result;
}
}
Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow