Информатика -продвинутый курс



         

РЕКУРСИВНЫЕ АЛГОРИТМЫ - часть 2


begin

k:=0; repeat k:=k+l; ql:=false; u:=x+dx[k]; v:=y+dy(k];

if ( (1<=u) and(u<=n) and (1<=v) and (v<=n) ) and(h[u,v]=0)

then begin h[u,v]:=i;

(*для отладки и наблюдения процесса поиска с возвратом*')

for ii:=l to n do begin for jj:= 1 to n do

write(h[ii,jj]:5); writeln;

end;

readin;

if i<nn then begin try(i+l,u,v,ql);

if not(ql) then h[u,v]:=0

else ql:=truer;

end

else ql:=true

end;

until (ql) or (k=8);

q:=ql

end; (* конец процедуры*)

begin

dx[l] =2: dx[2]:=l; dx[3]:=-l; dx[4]:=-2; dx[5]:=-2;

dx[6] =-1: dx[7]:=l; dx[8]:=2; dy[l]:=l; dy[2]:=2;

dy[3] =2: dy[4]:=l; dy[5]:=-l; dy[6]:=-2;

dy[7] =-2: dy[8]:=-1;

write ('введи n: '); readln(n);

for i =1 to n do for j:=1 to n do h[i,j]:=0;

write; ('введи i,j : '); readln(i,j); nn:=n*n;

h[i,j]:=l; try(2,i,j,q);

if q then begin

for i:=l to n do begin

for j:= 1 to n do write(h[i,j]:5);

writeln;

end;

end ' else writeln( 'нет маршрута');

readln

end.

Для n = 5 и n = 6 алгоритм быстро находит искомые туры коня. Для n = 8 время решения может возрасти в несколько десятков раз.

Рассмотрим еще два замечательных рекурсивных алгоритма, позволяющих строить регулярные образы, в конечном счете образующие красивые узоры на экране дисплея. Узор образуется из серии выстраиваемого определенным образом заданного мотива. '

Ниже представлена программа, использующая при построении узора кривые Серпинского, рис. 3.13.

Рис. 3.13. Примеры кривых Серпинского

На рисунке изображены кривые Серпинского S1 и S2 первого и второго порядков. Кривую Серпинского Si можно разбить на 4 части: Ai, Bi, Ci, Di, которые соединяются четырьмя отрезками Эти четыре части кривой представляют одну и ту же ломаную, поворачивающуюся каждый раз на 90 градусов. Нетрудно увидеть рекурсивные схемы, по которым ломаные Ai, Bi. Ci, Di получаются из кривых A(i-l). B(i-l), C(i-l), D(i-l), размеры которых при этом сокращаются вдвое:

Ai: A(i-l)

Bi: B(i-l)

Ci: C(i-l)

Di: D(i-l)

B(i-l)  –

C(i-l)  |

D(i-l) –

A(i-l)  |

D(i-l)

A(i-l)

B(i-l)

C(i-l)

A(i-l)

B(i-l)

C(i-l)

D(i-l)

<


Содержание  Назад  Вперед