1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#!/usr/bin/perl -w
run( @ARGV );
sub bottomup_tree {
my $depth = shift;
return 0 unless $depth;
--$depth;
[ bottomup_tree($depth), bottomup_tree($depth) ];
}
sub check_tree {
return 1 unless ref $_[0];
1 + check_tree($_[0][0]) + check_tree($_[0][1]);
}
sub stretch_tree {
my $stretch_depth = shift;
my $stretch_tree = bottomup_tree($stretch_depth);
print "stretch tree of depth $stretch_depth\t check: ",
check_tree($stretch_tree), "\n";
}
sub run {
my $max_depth = 16;
my $min_depth = 4;
$max_depth = $min_depth + 2 if $min_depth + 2 > $max_depth;
stretch_tree( $max_depth + 1 );
my $longlived_tree = bottomup_tree($max_depth);
for ( my $depth = $min_depth; $depth <= $max_depth; $depth += 2 ) {
my $iterations = 2**($max_depth - $depth + $min_depth);
my $check = 0;
foreach (1..$iterations) {
$check += check_tree( bottomup_tree($depth) );
}
print $iterations, "\t trees of depth $depth\t check: ", $check, "\n"
}
print "long lived tree of depth $max_depth\t check: ",
check_tree($longlived_tree), "\n"
}
|
