9도 OJ 1044:Pre-Post(선순 후순)(n 포크 트리, 귀속)
메모리 제한: 32메가
특수 판제:아니오
제출: 701
해결: 398
제목 설명:
We are all familiar with pre-order, in-order and post-order traversals of binary trees. A common problem in data structure classes is to find the pre-order traversal of a binary tree when given the in-order and post-order traversals. Alternatively, you can find the post-order traversal when given the in-order and pre-order. However, in general you cannot determine the in-order traversal of a tree when given its pre-order and post-order traversals. Consider the four binary trees below:
All of these trees have the same pre-order and post-order traversals. This phenomenon is not restricted to binary trees, but holds for general m-ary trees as well.
입력:
Input will consist of multiple problem instances. Each instance will consist of a line of the form m s1 s2 indicating that the trees are m-ary trees, s1 is the pre-order traversal and s2 is the post-order traversal.All traversal strings will consist of lowercase alphabetic characters. For all input instances, 1 <= m <= 20 and the length of s1 and s2 will be between 1 and 26 inclusive. If the length of s1 is k (which is the same as the length of s2, of course), the first k letters of the alphabet will be used in the strings. An input line of 0 will terminate the input.
출력:
For each problem instance, you should output one line containing the number of possible trees which would result in the pre-order and post-order traversals for the instance. All output values will be within the range of a 32-bit signed integer. For each problem instance, you are guaranteed that there is at least one tree with the given pre-order and post-order traversals.
샘플 입력:
2 abc cba
2 abc bca
10 abc bca
13 abejkcfghid jkebfghicda
샘플 출력:
4
1
45
207352860
출처:
2008년 상해교통대학 컴퓨터 연구 생기 시험 진제
아이디어:
m포크 나무의 각 층의 잎 노드의 조합 방식이 몇 가지가 있는지 구하세요.
선순과 후순 서열은 사실 각 층의 잎 노드의 개수와 어떤 것이 이 층의 잎 노드인지 확정할 수 있다. 유일하게 확실하지 않은 것은 바로 이 노드의 위치(그러나 선순으로 이 잎 노드의 상대적인 위치가 확정된 것)이다. 예를 들어 i층에 n개의 잎 노드가 있다(선순과 후순이 결합하여 판정된다). 그러면 이 층에는 c(n, m)의 조합 방식이 있다.그리고 어떤 잎 노드의 자수를 확정하여 그에 대해 귀속구해를 한다.
코드:
#include <stdio.h>
#include <string.h>
#define M 20
#define N 26
int m;
long long C(int m, int k)
{
int i;
long long c = 1;
for (i=m; i>k; i--)
c *= i;
for (i=m-k; i>0; i--)
c /= i;
return c;
}
long long prepost(char s1[], char s2[])
{
int len = strlen(s1);
if (len == 0 || len == 1)
return 1;
char root;
int c;
char sch1[M][N+1], sch2[M][N+1];
int i, j, k;
c = 0;
i = 1;
while (i < len)
{
root = s1[i];
j = i-1;
k = 0;
do
{
sch1[c][k] = s1[i];
sch2[c][k] = s2[j];
k++;
i++;
} while (s2[j++] != root);
sch1[c][k] = '\0';
sch2[c][k] = '\0';
c++;
}
long long count = C(m, c);
for (i=0; i<c; i++)
count *= prepost(sch1[i], sch2[i]);
return count;
}
int main(void)
{
char s1[N+1], s2[N+1];
while (scanf("%d", &m) != EOF)
{
scanf("%s%s", s1, s2);
//printf("%lld
", C(6, 2));
printf("%lld
", prepost(s1, s2));
}
return 0;
}
/**************************************************************
Problem: 1044
User: liangrx06
Language: C
Result: Accepted
Time:0 ms
Memory:912 kb
****************************************************************/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
C 언어 체인 시계는 뱀을 탐식하는 작은 게임을 실현한다본고의 실례는 여러분에게 C 언어 체인표가 뱀 탐식 게임을 실현하는 구체적인 코드를 공유하여 참고하도록 하였으며, 구체적인 내용은 다음과 같다. 프로젝트 이름: 뱀놀이 운영 환경: Linux 프로그래밍 언어: C 언...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.