openjudge 4077 스 택 시퀀스 통계

4077: 스 택 시퀀스 통계
보다
제출
통계
힌트
질문
총 시간 제한: 
100ms 
메모리 제한: 
64kB
묘사 하 다.
스 택 은 자주 사용 하 는 데이터 구조 로 n 개의 요소 가 스 택 상단 한쪽 에서 스 택 에 들 어 오 기 를 기다 리 고 스 택 상단 의 다른 한쪽 은 스 택 시퀀스 입 니 다.스 택 의 조작 은 두 가지 가 있다 는 것 을 이미 알 고 있 습 니 다. push 와 pop, 전 자 는 하나의 요 소 를 스 택 에 넣 고 후 자 는 스 택 꼭대기 요 소 를 팝 업 합 니 다.현재 이 두 가지 조작 을 사용 하려 면 하나의 조작 서열 에서 일련의 출력 서열 을 얻 을 수 있다.주어진 n 에 대해 연산 자 서열 1, 2,... n 을 계산 하고 출력 하 며 일련의 작업 을 통 해 얻 을 수 있 는 출력 서열 의 총 수 를 프로 그래 밍 하 십시오.
입력
하나만 n (1 ≤ n ≤ 15).
출력
출력 가능 한 시퀀스 의 총 항목 입 니 다.
샘플 입력
3

샘플 출력
5

제시 하 다.
이 문제 의 답 은 사실 카 탈 란 수 입 니 다. n 이 크 면 대응 하 는 수치 도 상당히 크 고 높 은 정밀도 로 사용 해 야 수용 할 수 있 습 니 다.그러나 n 이 그리 크 지 않 을 때 재 귀적 으로 해결 하려 고 시도 할 수 있다.
F (i, j) 는 스 택 에 i 개의 요소 가 있 고 j 개의 요소 가 스 택 에 들 어가 지 않 았 을 때 해당 하 는 방법 수 를 나타 낸다.
AC 코드:
# include "stdio.h"
int F(int i, int j)
{
	if(i==0&&j==0)
	return 1;
	else if(i>0&&j>0)
	return F(i+1, j-1)+F(i-1, j);
	else if(i==0&&j>0)
	return F(i+1, j-1);
	else if(i>0&&j==0)
	return F(i-1, j);
}
int main()
{
	int num;
	scanf("%d", &num);
	printf("%d
", F(0, num)); }

좋은 웹페이지 즐겨찾기