|
Матрица статей Список статей Всячина Контакты | ||||||||||||
|
Двоичные деревья 
Ярким примером
конструктивного фрактала является двоичное дерево. Оно строится по
следующему принципу: на каждом уровне вертикальная линия разделяется на две
с показателем уменьшения Разбиение какого-либо множества на группы из двух элементов или комбинирование в группы из двух элементов, характерно для двоичной системы счисления. Это разбиение часто применяется на практике, например, при спортивных командных соревнований. Команды разбиваются попарно, в паре определяется победитель, оставшиеся команды снова разбиваются, итак далее, пока не останется команда-победитель. Таким образом мы получили перевернутое двоичное дерево. Двоичное дерево является, одним из самых простых примеров семейства фракталов, в котором структура системы счисления представлена геометрически. Можно также построить троичное, четвертичное и т. д. деревья. Приведём программу построения двоичного дерева, представленного на рисунке.
program DD;
uses Graph, CRT;
const
min = 1;
var
gd, gm : Integer;
procedure Draw(x, y, l : Integer);
begin
if KeyPressed then
exit;
If l > min then
begin
l := l div 2;
line(x, y, x, y - l);
line(x, y - l, x - l, y - l);
line(x, y - l, x + l, y - l);
Draw(x - l, y - l, l);
Draw(x + l, y - l, l);
end;
end;
begin
gd := Detect;
InitGraph(gd, gm, '');
Draw(320, 460, 300);
ReadKey;
CloseGraph;
end.
Существуют и другие представления двоичного дерева, это H-дерево и V-дерево. H-дерево строится следующим образом: берем единичный отрезок, и на первом шаге два более коротких отрезка помещаем перпендикулярно концам первоначального так, чтобы образовалась буква H. И так до бесконечности.
На рисунке показано 9 шагов
построения, с показателем уменьшения 
program Hfract;
uses Graph,CRT;
procedure Fractal(x, y, l: Integer);
begin
if KeyPressed then
Exit;
if l > 4 then
begin
l := l div 2;
Line(x, y, x+l, y);
Line(x, y, x-l, y);
Line(x + l, y, x + l, y - l div 2);
Line(x + l, y, x + l, y + l div 2);
Line(x - l, y, x - l, y - l div 2);
Line(x - l, y, x - l, y + l div 2);
Fractal(x + l, y - l div 2, l);
Fractal(x + l, y + l div 2, l);
Fractal(x - l, y - l div 2, l);
Fractal(x - l, y + l div 2, l);
end;
end;
var
gd, gm: Integer;
begin
gd := detect;
InitGraph(gd, gm, 'c:\bp\bgi');
SetColor(15);
Fractal(320,240,256);
ReadKey;
CloseGraph;
end.
Для построения V-дерева используется фрагмент вида буквы V. Принцип построения виден из рисунка. 
program Vderevo;
uses Graph, CRT;
const
min = 3;
var
gd, gm : Integer;
procedure LineTo1(x, y : Integer; l, u : Real);
begin
Line(x, y, Round(x + l * cos(u)), Round(y - l * sin(u)));
end;
procedure Draw(x, y : Integer; l : Real);
begin
if KeyPressed then
exit;
if l > min then
begin
l := l * 0.5;
LineTo1(x, y, l, pi / 4);
LineTo1(x, y, l, 3 * pi / 4);
Draw(Round(x - l * cos(pi/4)),
Round(y- l * sin(pi/4)), l);
Draw(Round(x + l * cos(pi/4)),
Round(y- l * sin(pi/4)), l);
end;
end;
begin
gd := Detect;
InitGraph(gd, gm, 'c:\bp\bgi');
Draw(320, 380, 400);
ReadKey;
CloseGraph;
end.
Дерево Пифагора также является двоичным деревом. По аналогии можно построить троичное дерево и так далее. 
program DTr;
uses Graph, CRT;
const
max = 5;
var
gd, gm : Integer;
procedure LineTo1(x, y, l, u : Real);
begin
Line(Round(x), Round(y), Round(x + l * cos(u)), Round(y - l * sin(u)));
end;
procedure Draw(x, y : Integer; l, u : Real);
begin
if KeyPressed then
exit;
if l > max then
begin
l := l * 0.37;
Lineto1(x, y, l, u);
x := round(x + l * cos(u));
y := round(y - l * sin(u));
Draw(x, y, l + l / 3, u + 4 * pi/3);
Draw(x, y, l + l / 3, u - 4 * pi/3);
Draw(x, y, l + l / 3, u);
end;
end;
begin
gd := Detect;
InitGraph(gd, gm, '');
Draw(320, 240, 300, pi/2);
Draw(320, 240, 300, pi/2 + 4 * pi/3);
Draw(320, 240, 300, pi/2 - 4 * pi/3);
ReadKey;
CloseGraph;
end.
program Pr;
uses Graph, CRT;
const
min = 2;
var
gd, gm : Integer;
procedure Draw(x, y, l : Integer);
begin
if KeyPressed then
exit;
if l > min then
begin
l := l div 2;
SetFillStyle(1, 1);
Bar(x, y, x + l, y - l * 2);
SetFillStyle(1, 15);
Bar(x, y, x - l, y - l * 2);
Draw(x - l div 2, y - l, l);
Draw(x + l div 2, y - l, l);
end;
end;
begin
gd := Detect;
InitGraph(gd, gm, 'c:\bp\bgi');
Draw(320, 350, 256);
ReadKey;
CloseGraph;
end.
program Tree;
uses Graph;
procedure LinePolar(r1 : Real; a1 : Real; r2 : Real; a2 : Real);
begin
Line(
Round(320 + r1 * cos(a1)),
Round(240 - r1 * sin(a1)),
Round(320 + r2 * cos(a2)),
Round(240 - r2 * sin(a2)));
end;
function pow(d : Real; n : Integer) : Real;
var
i : Integer;
result : Real;
begin
result := 1.0;
for i := 1 to n do begin
result := result * d;
end;
pow := result;
end;
function radius(s : Real; r : Real; i : Integer): Real;
begin
radius := s * (1 - pow(r, i)) / (1 - r);
end;
function angle(d : Integer; i : Integer; j : Integer) : Real;
begin
angle := 2 * pi / pow(d, i) * (j - (pow(d, i) - 1) / 2);
end;
procedure Draw(n : Integer; d : Integer; r : Real; s : Integer);
var
i, j : Integer;
r1, r2, a1, a2 : Real;
begin
for i := 1 to n do begin
r1 := radius(s, r, i);
r2 := radius(s, r, i - 1);
for j := 0 to Round(pow(d, i)) - 1 do begin
a1 := angle(d, i, j);
a2 := angle(d, i - 1, j div d);
LinePolar(r1, a1, r2, a2);
end;
end;
end;
var
gd, dm : Integer;
begin
gd := Detect;
InitGraph(gd, dm, 'd:\tp7\bgi');
Draw(3, 8, 0.8, 90);
ReadLn;
CloseGraph;
end.
Смотрите также: Ссылки:
|
