6.5. Произвольное количество вложенных циклов

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

Для примера напишем процедуру, печатающую все возможные сочетания из k чисел от 1 до n ( ). Числа, входящие в каждое сочетание, будем печатать в порядке возрастания. Сочетания из двух чисел (k=2) печатаются так:

1 2 3

for i1 := 1 to n do   for i2 := i1 + 1 to n do     writeln(i1, ' ', i2);

Сочетания из трех чисел (k=3) так:

1 2 3 4

for i1 := 1 to n do   for i2 := i1 + 1 to n do     for i3 := i2 + 1 to n do       writeln(i1, ' ', i2, ' ', i3);

Однако, если количество чисел в сочетании задается переменной, то придется прибегнуть к рекурсии.[19]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

procedure Combinations(   n, k: integer;   //Массив, в котором будем формировать сочетания   var Indexes: array of integer;   //Счетчик глубины рекурсии   d: integer); var   i, i_min: integer;   s: string; begin   if d < k then   begin     if d = 0 then       i_min := 1     else       i_min := Indexes[d-1] + 1;     for i := i_min to n do     begin       Indexes[d] := i;       Combinations(n, k, Indexes, d+1);     end;   end   else   begin     for i := 0 to k-1 do       write(Indexes[i], ' ');     writeln;   end; end;

6.6. Задачи на графах

Графом называют графическое изображение, состоящее из вершин (узлов) и соединяющих некоторые пары вершин ребер (рис. 11а).

Более строго: граф – совокупность множества вершин и множества ребер. Множество ребер – подмножество евклидова квадрата множества вершин (то есть ребро соединяет ровно две вершины).

Ребрам можно также присвоить направление. Граф в этом случае называется ориетированным (рис. 11б).

Рис. 11. (а) Граф. (б) Ориентированный граф.

Теория графов находит применения в самых разных областях. Несколько примеров:

1. Логистика и транспортные системы. Вершинами будут склады с товарами или пункты назначения, а ребра – дороги, их соединяющие.

2. Маршрутизация сетей. Вершины – компьютеры, соединенные в сеть, ребра – связи между ними. Решается задача о путях передачи данных с одного компьютера на другой.

3. Компьютерная химия. Модели в виде графов используются для описания путей протекания сложных реакций. Вершины – участвующие в реакциях вещества, ребра – пути превращений веществ. Также графом является изображение структур молекул: вершины – атомы, ребра – химические связи.

4. Электрические сети.

5. Сайты в Интернете можно считать узлами ориентированного графа, ребрами которого будут гиперссылки.

6. И т. д.

Современная теория графов представляет собой мощную формальную систему, имеющую необозримое множество применений.

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

В программировании используются три способа хранения в памяти информации о стуктуре графов.

1) Матрицы смежности

Квадратная матрица M, где как строки, так и столбцы соответствуют вершинам графа. Если вершины с номерами i и j соединены ребром, то M_ij = 1, иначе M_ij = 0. Для неориентированного графа матрица, очевидно, симметрична. Ориентированный граф задается антисимметричной матрицей. Если ребро выходит из узла i и приходит в узел j, то M_ij = 1, а симметричный элемент M_ji = -1.

2) Матрица инцидентности

Столбцы матрицы соответствуют вершинам, а строки ребрам. Если ребро с номером i соединяет вершины с номерами j и k, то элементы матрицы I_ij = I_ik = 1. Остальные элементы i-й строки равны 0.

3) Список ребер

Просто набор пар номеров вершин, соединенных ребрами.

Рассмотренные выше деревья являются частным случаем графов. Деревом будет любой связный граф, не содержащий циклов.[20]