世界著名对冲基金:noi2004之FBI树。
来源:百度文库 编辑:高校问答 时间:2024/08/30 06:21:43
(fbi.pas/c/cpp)
【问题描述】
我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树 ,它的结点类型也包括F结点,B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T,递归的构造方法如下:
1) T的根结点为R,其类型与串S的类型相同;
2) 若串S的长度大于1,将串S从中间分开,分为等长的左右子串S1和S2;由左子串S1构造R的左子树T1,由右子串S2构造R的右子树T2。
现在给定一个长度为2N的“01”串,请用上述构造方法构造出一棵FBI树,并输出它的后序遍历 序列。
【输入文件】
输入文件fbi.in的第一行是一个整数N(0 <= N <= 10),第二行是一个长度为2N的“01”串。
【输出文件】
输出文件fbi.out包括一行,这一行只包含一个字符串,即FBI树的后序遍历序列。
【样例输入】
3
10001011
【样例输出】
IBFBBBFIBFIIIFF
【数据规模】
对于40%的数据,N <= 2;
对于全部的数据,N <= 10。
1、自下而上逐层生成FBI树
在程序中,要涉及到状态的存储、转换等。选择的数据结构必须先适用于描述状态,并使对状态的各种操作能够明确地定义在数据结构上。FBI树的数据结构不仅满足存储结点类别(‘F’,‘B’,‘Z’)的需要,而且能够方便地计算出左儿子和右儿子。设
tree为FBI树,其中tree[i]为节点i的类型标志,tree[i]∈{‘F’,‘B’,‘Z’};
treel,treer为FBI树的左儿子序列和右儿子序列,即节点i的左儿子序号为treel[i],右儿子序号为treer[i]。
FBI树的编号规则如下:
01串对应的类型作为FBI树的叶子存储于tree[m]¨tree[2*m-1](m=2n)。然后从最底层出发,自下而上地逐层向上计算tree[m-1]¨tree[1],其中节点i的左儿子序号为2*i,右儿子序号为2*i+1,即treel[i]←i*2; treer[i]←i*2+1。显然,根节点的序号为1。
若节点i的左子树的类型(tree[treel[i]])和右子树的类型(tree[treer[i]])至少有一个为‘F’或者一个‘B’和一个‘I’,则节点i的类型为‘F’;
若全‘I’,则节点i的类型为‘I’;若全‘B’,则节点i的类型为‘B’。
readln(n);{输入2的次幂}
if n=0{若01串的长度为1,则根据该字符输出串类型}
then begin
read(ch);
if ch='1'
then writeln('I')
else writeln('B');
halt{退出程序}
end;
m:=1;{计算串长2n}
for i:=1 to n do m:=m*2;
for i:=m to 2*m-1 do{将01串转换成FBI树的叶子}
begin
read(ch);
if ch='1'
then tree[i]:='I'
else tree[i]:='B';
treel[i]:=0;treer[i]:=0
end;
for i:=m-1 downto 1 do{由下而上递推计算FBI树}
begin
treel[i]:=i*2; treer[i]:=i*2+1;{计算节点i的左右儿子}
s:=tree[i*2]+tree[i*2+1];{取左右儿子的字符,根据规则向上递推节点i的字符}
if (s[1]='F')or(s[2]='F'){ 若节点i的左子树的类型和右子树的类型至少有一个为‘F’,则节点i的类型为‘F’}
then tree[i]:='F'
else begin{在节点i的左右子树的类型非‘F’的情况下,若左右子树的类型相同,则节点i的类型取决于子节点的类型;否则节点i的类型为‘F’}
if s[1]=s[2]
then if s[1]='I'
then tree[i]:='I'
else tree[i]:='B';
if s[1]<>s[2]{若}
then tree[i]:='F'
end{else}
end;{for}
后序遍历FBI树
在FBI树中,节点1为根。我们从根出发,按照左子树、右子树、根的顺序输出FBI树的后序遍历序列:
procedure print(s:integer);{后序遍历以节点s为根的FBI树}
begin
if s=0 then exit;{从叶子开始回溯}
print(treel[s]);print(treer[s]);{分别递归左子树和右子树}
write(tree[s]){输出根}
end;{ print }
显然,在递推出FBI树后递归调用print(1),便可得出问题的解。