кривой? Попробуем в качестве основного строительного ка выделить лист Si, возможно, без одного ребра. Но эт не приводит нас к нужному решению. Принципиальное ра личие между кривыми Серпинского и Гильберта заключаете в том, что кривые Серпинского являются замкнутыми (gg соединительных линий). Это означает, что основная рекурсив, пая схема должна давать разомкнутую кривую, а четыре ча. сти соединяются линиями, не принадлежашими самому рекур. сивному узору. Действительно, эти связи представляют собой

/ \

Рис. 3.6. Кривые Серпинского порядка 1 и 2.

четыре прямые в четырех внешних углах , изображенных на рис. 3.6 жирными линиями. Можно считать, что они принадлежат к непустой начальной кривой So, представляющей собой квадрат, стоящий на одном угле.

Теперь легко построить рекурсивную схему. Четыре составляющие фигуры вновь обозначаются А, В, С и D, а соединительные линии рисуются явно. Заметим, что четыре ре курсивные кривые действительно одинаковы с точностью до поворота на 90°.

Основной образ кривых Серпинского следующий:

S:A-~*BCD (3-21)

а объединенные рекурсивные фигуры строятся по таким схемам:

А: A-B=D-A В-.В^С Ы^В С: CDB.C D: J)AA CD

(Двойные стрелки обозначают линии двойной длины.)

(3.22)

ptogtm Sierpinski {pf,output);

,изображение кривых Сврпинского порядка oml до п\ const п 4; hO 512; -var /,A,x,j,xO,jO: integer;

pf: file of integer; procedure A(i: integer); begin if j > 0 then

begin .(j-1); x := x+h; у y-h; phi;

B(i-l); x := X + 2*h; plot; Z)(/-l); X := x+h; у := y+h; plot; A(i-l)

end ;

procedure В(1: integer); begin if I > 0 then

begin5(f-l); x := x-h; у := j-/г; plot; C(/-l); J := J - 2*/i; рЫ;

1); -\- := л:-ЬЛ; j> := y-h; plot; B(i-])

end ;

procedure C{i: integer); begin if J > 0 then

begin C(i-l); x := x-h; у :=> y+h; plot; /)(/-!); X := л; - 2*/г; plot; .fi(/-l); л := x-h; у := j-A; /7/0/;

F €0-1)

end ;

procedure D(i: integer): begin if f > 0 then

begin 2)(г-1); x ! = :>q+A; У J+A; pfo/f yl(/-l); у у + 2*A; />Ы; C(/-l); л := x-h; у j-f A; ploti D(i-i)

end end ;

btgin startplot;

i :< 0; A := AO div 4; xO 2*A; >0 : 3*A; repeat f := i+l; aO л-0-А; A :== A div 2; yO := >0+A; л; :== лО; у :== jO; setplot; A{i); X := x-fA; 7-A; pto;

BQ); X := x-h; у := y-h; plot;

C(i); X := x~h; у := y+h; plot;

JXf); X := x+h; у := y+h; plot; until i - n; endplot

end.

Программа 3.2. Кривые Серпинского.

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

procedure A(i: integer);

begin if/> Othen

begin Aii-1); x := x+h; у := yh; plot;

B(i-1); X x+2*h; plot;/ (3.23)

na-l); X := x+h; у y+h; plot; A(i-1)

Эта процедура соответствует первой строке рекурсивной схемы (3.22). Процедуры, соответствующие фигурам В, С и Д строятся аналогично. Основная программа строится по схеме (3.21). Она должна установить начальные значения для координат рисунка и задать длину единичной линии h в зависимости от формата бумаги, как показано в программе 3.2. Результат работы этой программы при п = 4 показан на рис. 3.7. Заметим, что 5о не рисуется.

Как можно убедиться, в этих примерах рекурсия используется весьма элегантно. Правильность программ легко следует из их структуры и схем построения. Кроме того, исполь; зование явного параметра уровня i в соответствии со схемой (3.5) гарантирует окончание программ, так как глубина Р^ курени не может быть больше п. По сравнению с этой Р^ курсивной формулировкой эквивалентные программы, кот рые избегают явного использования рекурсии, чрезвычайно рложны и трудны для понимания. Мы предлагаем читатея! самому в этом убедиться, попытавшись разобраться в пр граммах, приведенных в [3.3].