Выходной файл для данного примера:

abcba 1 ababa 2 acaba 3 abaca 4 асаса 5 acbca 6

В алгоритме 2.4 представлена программа расчета всех искомых маршрутов длины я. Алгоритм делится на две части. В первой части (процедура CreateTreeAbc) выполняется формирование двоичного регулярного дерева на смежной памяти рис. 2.7.

Алгоритм 2.4. Программа на Pascal t поиска замкнутых маршрутов по треугольнику Program{Движение по треугольнику АЬс)

uses CRT,DOS;

const n max=$fcOO; {Максимальная память для дерева}

type Vector-array[l..n max] of Char;

var f :Text; {Текстовый файл)

z :Vector; {Двоичное дерево движения по треугольнику} Procedure CreateTreeAbc( n:Integer ) ;

{Формирование дерева}

var

k, level,m,ml,m2 :LongInt;

begin

z[l]:=a; {Вершина a)

level: =1; {Номер уровня}

ml:=l; {Индекс первой вешины уровня)

m2:=l; {Индекс последней вешины уровня)

while level<=n do begin

for k:=ml to m2 do begin {Заполнить следующий

уровень дерева}

m:=2*k;

case z[k] of

a : begin z[m] :=b; z[m+l]:=c; end;

b: begin г [m] :=c ; z [m+1] :=a; end;

c: begin z [m] :=a; z [m+1 ] : =b; end; end; end;

level:=level+l;

ml:=2*ml; m2:=2*m2+l; end; end;

Procedure RouteTreeAbo( n:Integer ); (Формирование

маршрутов}

var

i,k,ml,m2,r :LongInt;

begin

r: =0; {Количество маршрутов } k:=l;

for i:=l to n do k:=2*k;

ml:-k;{Индекс первой вершины на последнем уровне! m2:=2*k-l; {Индекс последней вершины

на последнем for i:=ml to m2 do Ьед1п{Проход от листьев

к вершинам дерева}

k:=i;

if z[k]=a then begin r:=r+l; WriteLn(f); repeat

Write(f,z[k]); k:=k div 2; until k=0; Write(f, r) ; end; end; end;

Var {Main> n :Integer; {Длина маршрута»

begin {Main}

Assign(f,treeabc.in ) ;

Reset (f); (Фай/ открыт для чтения)

Read(f,n); {Ввод данных}

Close(f);

Assign(f,treeabc.out ) ;

открыт для

CreateTreeAbc(n); (Формировать дерево Abe

сверху вниз) RouteTreeAbc(з) ; (Формировать маршруты

от листьев к вершине)

Close (f); end. {Main}

При проходе вниз вершины дерева заполняются метками а, Ь. с, соответствующими вершинам треугольника при перемещении

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

данных (смежной памяти).

л л л /\ /\ л /С д

6] с[17] с[18]а[19] с[20] а[21] аг22] b[23]с[24] а[25] а[26] b[27] а[28] b[29] bf30]ф

b[16] с[17] с[18]а[19] с[20] а[21] af22] b23] с[24] а[25] а[26] b[27] а[28] Ь[29] ЬГЗО] cl]

Рис. 2.7. Двоичное дерево маршрутов по треугольнику на смежной памяти

Во второй части алгоритма выполняется формирование искомых маршрутов (процедура RouteTreeAbc), основой для построения которых служит дерево прохода на рис. 2.7. Для формирования всех маршрутов теперь достаточно подняться по нему от листьев с метками а вершины треугольника к корню, запоминая пройденные метки. Ясно, что число маршрутов будет равно числу

вершин на последнем уровне (количество листьев) с меткой а. 2.3. Представление множеств

Существуют два основных подхода к представлению множеств в памяти.

1.При первом подходе хранят описание каждого элемента, действительно присутствующего в множестве, как это делается, когда выписываются все элементы множества и заключаются в фигурные скобки.

2.При втором подходе изначально определяются все потенциально возможные элементы множества, а затем для любого подмножества этого универсального множества для каждого возможного члена указывается, принадлежит ли он на самом деле данному подмножеству или нет.

с[4]