How Many Trees?

제목: n개 노드의 두 갈래 나무를 정하고 이 나무에 몇 개의 두 갈래 나무가 있는지 구하세요.
데이터 범위: n<=100
생각:
n개 노드의 두 갈래 나무는 여러 종류가 있고, 여러 종류의 두 갈래 나무 안에 또 자목이 있다.n이 100에 도달했을 때 결과는 방대한 숫자이기 때문에 대수를 써야 한다.
카드란 수의 응용에서 두 갈래 나무의 개수를 구하는 것은 전형적인 응용이고 합법적인 입고출고 서열수, 다각형을 삼각형으로 나누는 개수, 원괄호를 공식에 삽입하는 방법수는 모두 카드란 수의 응용이다
카틀란드 수 상세설명: Math173(이 면은 보기 좋다)
코드:

#include      // 100， 
#include 
#include 
#define base 10000
#define maxn 100 

using namespace std;

int num[105][100];
void multiply(int a[],int b)
{
	int i,temp = 0;
	for(i = maxn - 1; i >= 0; i--)
	{
		temp += a[i]*b;
		a[i] = temp%base;
		temp /= base;
	}
}
void dive(int a[],int b)
{
	int i,temp = 0;
	for(i = 0; i < maxn; i++)
	{
		temp = temp*base + a[i];
		a[i] = temp / b;
		temp %= b;
	}
}
int main()
{
	int i,n;
	memset(num,0,sizeof(num));
	num[1][maxn-1] = 1;
	for(i = 2; i <= 100;i++)
	{
		memcpy(num[i],num[i-1],maxn*sizeof(int));
		multiply(num[i],4*i-2);
		dive(num[i],i+1);
	}
	while(scanf("%d",&n)!=EOF)
	{
		i = 0;
		while(num[n][i] == 0)i++;
		printf("%d",num[n][i++]);
		for(; i < maxn; i++)
		{
			printf("%04d",num[n][i]);
		}
		printf("
");
	}
	return 0;
}

이상은 n개의 입적 조작, n개의 출적 조작을 구하는 것과 같다. 전형적인 입적 조작수는 출적 조작수와 같지만 그렇지 않은 경우도 있다. 다음과 같다.

Buy the Ticket

제목: 영화관에서 표를 판다.표 한 장에 50원입니다.처음에는 잔돈이 없었다.m+n이 있으면 표를 사고, m사람이 50원짜리 지폐를 들고, n사람이 100원짜리 지폐를 받는다.대오에게 몇 가지 배열 방식이 매표를 순조롭게 진행할 수 있는지 물어보다.
데이터 범위: m, n <=100, m==n== 0 입력 종료
문제: 전형적인 카트란 수, 자세한 내용은 i_ 참조fuqiang의 칼럼
코드:

#include 
#include 
using namespace std;
#define MAX 100
#define BASE 10000
void multiply(int a[],int Max,int b)  // 
{
    int i,array=0;
    for (i=Max-1; i>=0; i--)   
    {
        array+=b*a[i];
        a[i] = array%BASE;
        array /= BASE;   
    }
}

void divide(int a[], int Max, int b)  // 
{
    int i,div=0;
    for (i=0;i> M >> N , M + N )
     {
             printf ( "Test #%d:
",ca++ );
             if ( N > M )
             {
                  puts ( "0" );
                  continue; 
             }
             memcpy ( res , fact[M+N] , MAX * sizeof ( int ) ); //  ( m + n )!
             multiply ( res, MAX, M - N + 1 );    // ( m + n )! * ( m-n+1 )
             divide ( res, MAX, M + 1 );   // ( m + n )! * ( m-n+1 )  / ( m+ 1 )         
             outPut ( res );
     }
     return 0;
}