Лабораторная работа № Проектирование алгоритмов. Оценка корректности и эффективности алгоритма. Алгоритм определения корня квадратного уравнения. Формула Герона для определения площади треугольника

Пример

Порядок обхода дерева в глубину:

Граф и остовное дерево, полученное при обходе его вершин методом поиска в глубину:

Цепочка Задание
Задан набор неповторяющихся пар (A_i,A_j), A_i, A_j принадлежат множеству А={A₁, A₂, ...,
A_n}. Необходимо составить цепочку максимальной длины по правилу (A_i,A_j)+(A_j,Ak)=(A_i,A_j,A_k).
При образовании этой цепочки любая пара может быть использована не более одного раза.

Ввод

Входящими данными является матрица смежности, составленая по такому правилу:
C[i,j]=1, если в наборе есть пара (Ai,Aj) и C[i,j]=0 иначе.

Вывод

Вывести последовательность звеньев самой длинной цепочки в формате Ai Ak ... An. Решение
Будем строить все возможные цепочки (по правилу, данному в условии) и искать среди них ту, которая имеет максимальную длину. Для этого воспользуемся поиском в глубину. После построения цепочки, к которой уже нельзя присоединить ни одного звена, сравниваем длину текущей цепочки с длиной максимальной. Если текущая цепочка длиннее, то запоминаем еѐ и считаем текущую цепочку максимальной. Формальный алгоритм приведѐн ниже.

Формальное описание

Chain()

1. 
   Создать матрицу смежности для цепочки.
   
2. 
   Для каждой вершины графа повторить пп.2.1-2.4:
   
   1. 
      Поиском в глубину найти неувеличивающийся маршрут из текущей вершины.
      
   2. 
      Если найденный маршрут длиннее максимального, то сохранить данный маршрут и считать его максимальным.
      
   3. 
      Найти следующий маршрут для текущий вершины.
      
   4. 
      Если маршрут не найден, то перейти к следующей вершине.
      
3. 
   Вывести самый длинный маршрут
   

Путь Задание

Найти все возможные пути между двумя вершинами в графе не пеpесекающиеся по: а) pебpам
б) веpшинам. Ввод
Входящими данными является матрица смежности, составленная по такому правилу: C[i,j]=1, если в графе есть ребро (Ai,Aj) и C[i,j]=0 иначе.