Примеры рекурсивных алгоритмов

Рисование дерева

Рассмотрим алгоритм рисования деревца, изображенного на рис. 6. Если каждую линию считать узлом, то данное изображение вполне удовлетворяет определению дерева, данному в предыдущем разделе.

Рис. 6. Деревце.

Рекурсивная процедура, очевидно должна рисовать одну линию (ствол до первого разветвления), а затем вызывать сама себя для рисования двух поддеревьев. Поддеревья отличаются от содержащего их дерева координатами начальной точки, углом поворота, длиной ствола и количеством содержащихся в них разветвлений (на одно меньше). Все эти отличия следует сделать параметрами рекурсивной процедуры.

Пример такой процедуры, написанный на Delphi, представлен ниже:

procedure Tree( Canvas: TCanvas; //Canvas, на котором будет рисоваться дерево x,y: extended; //Координаты корня Angle: extended; //Угол, под которым растет дерево TrunkLength: extended; //Длина ствола n: integer //Количество разветвлений (сколько еще предстоит //рекурсивных вызовов) ); var x2, y2: extended; //Конец ствола (точка разветвления) begin x2:= x + TrunkLength * cos(Angle); y2:= y - TrunkLength * sin(Angle); Canvas.MoveTo(round(x), round(y)); Canvas.LineTo(round(x2), round(y2)); if n > 1 then begin Tree(Canvas, x2, y2, Angle+Pi/4, 0.55*TrunkLength, n-1); Tree(Canvas, x2, y2, Angle-Pi/4, 0.55*TrunkLength, n-1); end; end;

Для получения рис. 6 эта процедура была вызвана со следующими параметрами:

Tree(Image1.Canvas, 175, 325, Pi/2, 120, 15);

Заметим, что рисование осуществляется до рекурсивных вызовов, то есть дерево рисуется в прямом порядке.[14]

Дата добавления: 2015-08-09