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

Решение

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

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

Way()

1. 
   Создать матрицу смежности для графа.
   
2. 
   Прочитать номера стартовой и финишной вершины графа.
   
3. 
   Инициализировать метки о использовании.
   
4. 
   Добавить стартовую вершину в путь.
   
5. 
   Найти все маршруты, не пересекающиеся по рѐбрам (пп.5.1-5.5):
   
   1. 
      Если поиск вызван не со стартовой вершины, то считать последнее ребро маршрута пройденным.
      
   2. 
      Найти вершину, инцидентную данной.
      
   3. 
      Если ребро, которое ведѐт к инцидентной вершине не было использовано, то добавить вершину в путь, то считать ей текущей и перейти к 5.1.
      
   4. 
      Если финишная вершина достигнута, то вывести путь.
      
   5. 
      Считать последнее ребро маршрута непройденным.
      
6. 
   Найти все маршруты, не пересекающиеся по вершинам (пп.6.1-6.5):
   
   1. 
      Присвоить текущей вершине номер шага.
      
   2. 
      Найти вершину, инцидентную данной.
      
   3. 
      Если инцидентная вершина не была использована, то считать еѐ текущей, запомнить предыдущую вершину и перейти к п.6.1.
      
   4. 
      Если финишная вершина достигнута, то вывести путь.
      
   5. 
      6.5. Считать последнюю вершину маршрута непройденной.
      

3. Задание на лабораторную работу

1. 
   Создать граф на 9 вершин, реализовать алгоритм обхода графа в глубину, вывести на экран список древесных ребер и число компонент связности.
   

Пример:




4. Содержание отчета
В отчете следует указать:

• 
  Название работы.
  
• 
  Цель работы.
  
• 
  Теоретическая часть.
  
• 
  Выполненное задание.
  
• 
  Заключение (выводы).
  
• 
  Литература.