N개의 결점은 얼마나 다른 두 갈래 나무를 구성할 수 있는가

1848 단어
제목: 나무의 형태
시간 제한 1000ms, 메모리 제한 256000kB, 코드 길이 제한 8000B
줄마다 자연수 n을 입력하여 두 줄, 줄마다 숫자를 출력합니다. 각각: 노드가 n인 두 갈래 트리에는 ___심다각 노드에 빨간색, 검은색 두 가지 색상이 있을 수 있는 경우 ___심다
입력 예:
일
이
출력 예:
일
이
이
팔
사고방식: 이 문제는 바로 Catalan수의 응용 중 하나이다. N개의 결점은 얼마나 다른 두 갈래 나무를 구성할 수 있는지.
문제1에 대해 N개의 결점을 설정하면 f(N)개의 서로 다른 두 갈래 나무를 구성할 수 있다. 만약에 왼쪽 나무에 M개의 결점이 있다면 오른쪽 나무에 N-M-1개의 결점이 있다. 이때 하위 나무 개수는 각각 (M, N-M-1)인 두 갈래 나무는 f(M)*f(N-M-1)종이고 M은 0에서 N-1로 가져올 수 있기 때문에 f(N)=f(0)*f(N-1)+f(N-2)+·+f(M)*f(N-1)*f(0),f(0),f() = 1, f (1) = 1.상식은 바로 Catalan 수의 계산 공식이다.
Catalan 수의 계산 공식은 다음과 같습니다.
f(n)=f(n-1)*(4*n-2)/(n+1);
f(n)=C(2n,n)/(n+1) (n=0,1,2,...);
f(n)=C(2n,n)-C(2n,n+1)(n=0,1,2,...);
C (2n, n) 는 조합수이며, 여기서 빨간색으로 표시된 공식을 선택하여 계산합니다.
문제2, 각 결점은 빨간색과 검은색일 수 있기 때문에 N개의 결점은 2^N에서 가능한 색깔로 배열되고 위에 있는 두 갈래 나무의 종류수, 즉 착색된 두 갈래 나무의 종류수: 2^N*f(N)
#include <iostream>
#include <math.h>
#include <queue>
typedef unsigned long long ULONG;

ULONG Factorial(ULONG N) {
		if (N < 0) return 0;
		ULONG result = 1;
		for (ULONG i = 2; i <= N; ++ i)
			result *= i;
		return result;
}

ULONG Catalan(ULONG N) {
	if (N < 0)  return 0;
	if (N == 0) return 1;
	if (N == 1) return 1;
	ULONG fn = Factorial(N);
	ULONG comb = Factorial(2*N) / (fn * fn);
	return comb / (N + 1);
}

void CatalanReadData() {
	std::queue<int> input;
	int N;
	while (std::cin >> N) {
		input.push(N);
	}
	while (!input.empty()) {
			ULONG cata = Catalan(input.front());
			std::cout << cata << std::endl;
			std::cout << (ULONG)pow((double)2, input.front()) * cata <<std::endl;
			input.pop();
	}
}

PS: 유도, 기계시험, 2013, 학교 모집
참조:
[1] http://blog.csdn.net/ffjjqqjj/article/details/6081711
[2] http://baike.baidu.com/view/2499752.htm
계단식 두 갈래 나무 관련 문제
트리

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage