, представленный ранее, включает
в себя и множественную, и косвенную рекурсию. Поскольку алгоритм состоит из
четырех подпрограмм, которые вызывают друг друга, нельзя просто пронумеро-
вать важные строки программы, как в случае с алгоритмом Гильбертовых кривых.
Можно справиться с этой проблемой, переписав алгоритм с самого сначала.
Рекурсивная-версия алгоритма состоит из четырех подпрограмм- SierpA,
SierpB, SierpC и SierpD. Процедура SierpA выглядит следующим образом:
procedure TSierplForm.SierpA(depth, diet : Integer);
begin
with DrawArea.Canvas do
begin
if (depth=1) then
begin
LineTo(PenPos.X-dist,PenPos.Y+dist);
LineTo(PenPos.X-dist,PenPos.Y+0);
LineTo(PenPos.X-dlst,PenPos.Y-dist);
end else
begin
SierpA(depth-1,dist) ;
LineTo(PenPos.X-dist,PenPos.Y+dist);
SierpB(depth-1,dist);
LineTo(PenPos.X-dist,PenPos.Y+0);
SierpD(depth-1,dist);
LineTo(PenPos.X-dist,PenPos.Y-dist);
SierpA(depth-l,dist) ;
end;
end;
end;
Остальные три процедуры аналогичны. Объединить их все в одну не слишком
сложно.
procedure DrawSubcurve(depth, dist, func : Integer);
begin
case func of
1 :
// <код SierpA>.
2 :
// <код SierpB>.
3 :
// <код SierpC>.
4 :
// <код SierpD>.
end;
end;
Параметр Func указывает процедуре, какая часть кода должна выполняться.
Можно заменить вызовы подпрограмм вызовом SierpAll с соответствующим
значением func. Например, вместо подпрограммы SierpA будет вызываться про-
цедура SierpAll, где значение func установлено в 1.
Новая процедура рекурсивно вызывает себя в 16 различных точках. Эта про-
цедура намного сложнее, чем процедура Hi Ibert, но с другой стороны, она имеет
схожую структуру. Поэтому для того чтобы сделать ее нерекурсивной, вы можете
применить те же методы.
Используйте первую цифру меток рс, чтобы указать общий блок кода, кото-
рый должен выполняться. Пронумеруйте строки в пределах кода SierpA числа-
ми И, 12, 13 и т.д., а в коде SierpB - соответственно числами 21, 22, 23 и т.д.
Теперь можно маркировать ключевые строки программы в пределах каждого
блока. Для кода подпрограммы SierpA ключевые строки будут такими:
// Код SierpA.
with DrawArea . Canvas do
begin
11 if (depth=1) then
begin
LineTo ( PenPos . X-dist , PenPos . Y+dist ) ;
LineTo ( PenPos . X-dist , PenPos . Y+0 ) ;
LineTo ( PenPos . X-dist , PenPos . Y-dist ) ;
end else begin
SierpA (depth-1,dist) ;
12 LineTo (PenPos. X-dist, PenPos. Y+dist) ;
SierpB(depth-1,dist) ;
13 LineTo (PenPos. X-dist, PenPos. Y+0) ;
SierpD (depth-1,dist) ;
14 LineTo (PenPos. X-dist, PenPos. Ydist) ;
SierpA (depth-1,dist) ;
end;
end;
Типичная мнимая рекурсия из кода подпрограммы SierpA в код подпрограм-
мы SierpB выглядит так:
PushValues (depth, 13) // По окончанию рекурсии начать с шага 13.
depth := depth- 1;
рс := 21; // Отправиться в начало кода SierpB.
Метка 0 зарезервирована для обозначения окончания мнимой рекурсии. Сле-
дующий код представляет собой часть нерекурсивной версии процедуры Sierp-
А11. Код для SierpB, SierpC, и SierpD подобен коду для SierpA, поэтому он
опущен.
procedure TSierpinskiForm.DrawSubcurve (depth, pc, dist : Integer);
begin
with DrawArea. Canvas do
begin
while (true) do
begin
case pc of
//**************
//* SierpA *
//**************
11 :
begin
if (depth<=1) then
begin
LineTo(PenPos.X-dist,PenPos.Y+dist);
LineTo(PenPos.X-di st,PenPos.Y+0);
LineTo(PenPos.X-dist,PenPos.Y-di st);
pc := 0;
end else begin
PushValues(12,depth); // Запуск SierpA.
depth := depth-1;
pc := 11;
end;
end;
begin
LineTo(PenPos.X-dist,PenPos.Y+dist);
PushValues(13,depth); // Запуск SierpB.
depth := depth-1;
pc := 21;
end;
begin
LineTo(PenPos.X-dist,PenPos.Y+0);
PushValues(14,depth); // Запуск SierpD.
depth := depth-1;
pc := 41;
end;
14 :
begin
LineTo(PenPos.X-di st,PenPos.Y-di st);
PushValues(0,depth);
depth := depth-1;
pc := 11;
end;
// Код SierpB, SierpC и SierpD опущен.
// Запуск SierpA.
//Конец рекурсии
0 :
begin
if (top_of_stack<=0) then break; // Готово.
PopValues(pc,depth);
end;
end; // case pc of
end; // while (true) do.
end; // with DrawArea.Canvas do.
end;
Как и в случае с алгоритмом построения Гильбертовых кривых, преобразова-
ние алгоритма рисования кривых Серпинского в нерекурсивную форму не изменя-
ет его сложности. Новый алгоритм имитирует рекурсивный, который выполняется
течение O(N^4) времени, поэтому новая версия также имеет сложность порядка
О(N^4).
Нерекурсивная версия позволила бы достичь большей глубины рекурсии, но
вывести кривые Серпинского с глубиной больше чем 8 или 9 практически невоз-
можно. Все эти факты определяют преимущество рекурсивного алгоритма. |
Главная
Каталог файлов
