学步园

红黑树(tree)
【问题描述】
红黑树是一类特殊的二叉搜索树，其中每个结点被染成红色或黑色。若将二
叉搜索树结点中的空指针看作是指向一个空结点，则称这类空结点为二叉搜索树
的前端结点。并规定所有前端结点的高度为-1。
一棵红黑树是满足下面“红黑性质”的染色二叉搜索树：
(1) 每个结点被染成红色或黑色；
(2) 每个前端结点为黑色结点；
(3) 任一红结点的子结点均为黑结点；
(4) 在从任一结点到其子孙前端结点的所有路径上具有相同的黑结点数。
从红黑树中任一结点x 出发(不包括结点x)，到达一个前端结点的任意一条
路径上的黑结点个数称为结点x 的黑高度，记作bh(x)。红黑树的黑高度定义为
其根结点的黑高度。
给定正整数N，试设计一个算法，计算出在所有含有N 个结点的红黑树中，

红色内结点个数的最小值和最大值。

【输入】

一个正整数N(N<=5000)

【输出】

第一行为最小值

第二行为最大值

不是特别会，看了看解析，看了一下规律，很好奇如何才能推出前四十多个的值……

program tree;
var
  n,i,k,now,l:longint;
  f:array [0..5001] of longint;
begin
  assign(input,'tree.in');
  reset(input);
  assign(output,'tree.out');
  rewrite(output);
  read(n);
  now:=0;
  k:=2;
  f[1]:=0;
  f[2]:=1;
  for i:=3 to n do
    begin
      if now=1 shl k then
        begin
          now:=0;
          inc(k);
        end;
      inc(now);
      if now<=1 shl (k-1) then f[i]:=f[i-1 shl (k-1)]
                          else f[i]:=f[i-1 shl k]+1;
    end;
  writeln(f[n]);
  fillchar(f,sizeof(f),0);
  now:=0;
  k:=2;
  f[1]:=1;
  f[2]:=1;
  l:=1;
  for i:=3 to n do
    begin
      if now=1 shl k then
        begin
          l:=f[i-(1 shl k)];
          now:=0;
          inc(k);
        end;
      inc(now);
      if now<=1 shl (k-1) then
        f[i]:=f[i-(1 shl (k-1))]+l
                          else
      if now=1 shl (k-1) + 1 then
        begin
          f[i]:=f[i-1]+1+(1 and (k-1));
          l:=f[i]-l;
        end
                             else
        f[i]:=f[i-(1 shl k)]+l;
      if (k and 1 = 0)and(now=(1 shl (k-1))+1) then dec(f[i]);
      if (k and 1 = 1)and(now=1) then inc(f[i]);
    end;
  writeln(f[n]);
  close(input);
  close(output);
end.