2．N叉树
题目描述:
我们都了解二叉树的先根遍历，中根遍历和后根遍历。当知道先根遍历的结果和中根遍
历结果的时候，我们可以唯一的确定二叉树；同样的，如果知道了后根遍历的结果和中根遍
历结果，二叉树也是唯一确定的。但是如果只知道先根遍历和后根遍历的结果，二叉树就不
是唯一的了。但是我们可以计算满足条件的不同二叉树一共有多少个。这不是一个很困难的
问题，稍微复杂一点，我们把这个问题推广到N叉树。
我们用小写英文字母来表示N 叉树的结点，不同的结点用不同的字母表示。比如，对
于4叉树，如果先根遍历的结果是abdefgc，后根遍历的结果是defgbca，那么我们可以
得到6个不同的4叉树（如下图）。

输入:
输入数据包括3行。
第一行是一个正整数N(2 ≤ N ≤ 20)，表示我们要考虑N叉树。
第二行和第三行分别是两个字符串序列，分别表示先根遍历和后根遍历的结果。
输出:
输出不同的N叉树的数目。题目中给的数据保证得到的结果小于2
31
。
输入样例:
4
abdefgc
defgbca
输出样例:
6
程序：
var
str1, str2 : string;
N, len : integer;
com : array[0..100, 0..100] of longint;
function getcom(x, y : integer) : longint;
begin
if (y = 0) or (x = y) then ①
else if com[x][y] <> 0 then getcom := com[x][y]
else begin
com[x][y] := getcom(x - 1, y)+ ② ;
getcom := com[x][y];
end;
end;
function count(a, b, c : integer) : longint;
var
sum : longint;
k, s, t, p : integer;
begin
sum := 1; k := 0; s := a + 1; t := c;
if a = b then count := 1
else begin
while s <= b do begin
p := t;
while str1[s] <> str2[t] do inc(t);
sum := sum * count(s, s + t - p, p);
s := ③ ;
④ ; inc(k);
end;
count := ⑤ * getcom(N, k);
end;
end;
begin
readln(N); readln(str1); readln(str2);
len := length(str1);
writeln(count( ⑥ ));
end.
　

上一页  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]  下一页