首页 > ACM题库 > 九度OJ > 九度-1044-Pre-Post[分治和组合数]
2014
04-02

九度-1044-Pre-Post[分治和组合数]

题目来源:2008年上海交通大学计算机研究生机试真题

题目描述:
        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:

1044_Pre_Post
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

题目大意:对于n叉树,给出先序遍历和后续遍历,求可能的个数。

递归和组合数学。

例如:

10 abc bca
根节点为a是确定的,接下来是 bc bc
可知b,c在同一级别,有C(10,2)=45 (10个位置中取两个)
2 abc cba

同样根节点为a,然后是 bc cb

b,c在两层 C(2,1) * C(2,1)=4

对于这个就有些复杂了,

13 abejkcfghid jkebfghicda

第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)

再继续递归下去,直到字符串长度为1

#include <iostream>
#include <string.h>
#include <string>
#include <stdio.h>
using namespace std;

char str1[30],str2[30];
string pre,post;
int n;
int c[23][23];
//组合数计算
void initc(){
	c[1][0] = c[1][1] = 1;
	for(int i=2; i<23; i++){
		c[i][0] = 1;
		for(int j=1; j<=i; j++){
			c[i][j] = c[i-1][j] + c[i-1][j-1];
		}
	}
}
int getCnt(string left,string right){
	int cnt=0;
	int res = 1;
	if(left.size() <= 1) return n; //只有一个元素,可以放置n个位置
	for(int i=0; i<left.length();){
		int j=i;
		while(j<left.length() && right[j] != left[i]) j++ ;
		//一层的单个叶子节点不考虑
		if(j>i)
			res *= getCnt(left.substr(i+1,j-i), right.substr(i,j-i));
		cnt++;
		i = j+1;
	}
	res *= c[n][cnt];
	return res;
}

int main() {
	freopen("in.txt","r",stdin);
	initc();
	while(cin >> n ){
		if(!n) break;
		cin >>  pre >> post;
		int ans = 1;
		if(pre.length() > 1)
			ans = getCnt(pre.substr(1,pre.length()-1), post.substr(0, pre.length()-1) );
		cout << ans << endl;
	}
	return 0;
}

解法2:

#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;
int c[21][21];
int n;
long long test(string pre, string post) {
	long long sum = 1;
	int num = 0;
	 int k = 0, i;
	pre.erase(pre.begin());
	post=post.substr(0, post.length()-1);
	while (k < pre.length()) {
		for (i = 0; i < post.length(); i++)
			if (pre[k] == post[i]) {
				sum *= test(pre.substr(k, i - k + 1),
						post.substr(k, i - k + 1));
				num++; //num代表串被分成了几段(例如 (bejkcfghid,jkebfghicd) = (bejk, cfghi, d) )
				k = i + 1;
				break;
			}
	}
	//cout << pre << "  " << post <<"  " << t1 << " =" << num << endl << endl;
	sum *= c[num][n]; //从n中取num个的取法个数
	return sum;
}
void getsc() {
	int i, j;
	c[0][1] = c[1][1] = 1;
	for (i = 2; i < 21; i++) {
		c[0][i] = 1;
		for (j = 1; j <= i; j++){
			if (i == j)
				c[j][i] = 1;
			else
				c[j][i] = c[j - 1][i - 1] + c[j][i - 1];

		}
	}
}
int main() {
	string pre, post;
	getsc();
	while ((cin >> n >> pre >> post) && n) {

		cout << test(pre, post) << endl; //printf("%ld\n",test(pre,post));
	}
	return 0;
}
/**************************************************************
	Problem: 1044
	User: coder
	Language: C++
	Result: Accepted
	Time:0 ms
	Memory:1520 kb
****************************************************************/

  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  3. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

    • a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c