|
Читайте также: |
Поиск достижимых вершин графа.
Пример графа
Графы-способ формализовать всевозможные схемы.
Математики считают, что граф состоит из двух связанных между собой множеств. Первое- множество вершин (чаще всего изображается в виде кружочков с цифрами). Вершина: технологическая установка города на атласе автомобильных дорог, станция метрополитена и т.д.
Второе- множество дуг (чаще всего изображается в виде стрелочек).
Дуга: трубы, дороги, туннели.
Графы бывают направленные и ненаправленные. Если граф направленный, дуги обозначаются стрелочками (транспортная схема с односторонним движением).
Один из способов представления графа в памяти компьютера называется матрицей смежности.
В 4-ю из 1-й
n i A к у д а
5 о 0 0 0 1 0
т 1 0 1 0 0
к 0 0 0 1 0
у 0 1 0 0 1
д 0 0 0 0 0
а
Задача: граф задан матрицей смежности; необходимо назвать все вершины графа, в которые можно попасть по стрелочкам (дугам) из заданной вершины.
Схематичное описание алгоритма поиска достижимых вершин.
Алгоритм поиска достижимых вершин графа является рекурсивным. Схематично его можно описать как:
Шаг 1: найти все вершины непосредственно связанные со стартовой вершиной (идём по стрелочкам);
Шаг 2(рекурсивный): для каждой найденной вершины рекурсивно выполнить алгоритм поиска достижимых вершин, рассматривая уже найденную вершину как стартовую.
В процессе работы все найденные вершины нужно объединять вместе.
Примитивный алгоритм должен быть снабжён проверками, предотвращающий бесконечную рекурсию.
←Бесконечная рекурсия.
Sub click()
Dim n As Integer, i As Integer, j As Integer, count As Integer
n=cells(2,1) ‘ n – это количество вершин (ячеек)
ReDim A(n,h) As Integer ‘ двумерный массив А
For i=1 To n:for j=1 To n двойной цикл перебираются строки, столбцы, ячейки
A(i,j)=cells(1+i,2+j)
Next j,i
i=cells(2,2):count=0 ‘ счётчик считает найденные вершины начиная с 0
call spisok(n,i,count,A()) ‘ i – стартовая величина, Call – вызов подпрограммы, А() –матрица смежности.
End Sub
Подпрограмма (процедура), вызывает сама себя, (рекурсивная):
Sub spisok (n As Integer, i_start As Integer, count As Integer, A() As Integer)
Dim i As Integer, j As Integer, k As Integer ‘ дополнительные переменные
For j=1 to n
If A(i_start,j)=1 then
count=count+1’увеличивает счётчик на единицу
cells(3+count,2)=j ‘ записывает в свободную ячейку
For k=1 To n:A(k,j)=-Abs(A(k,j)):Next k ‘Отвечает за то, чтобы мы не могли попасть в найденную вершину из другой вершины
call spisok (n,j,count,A()) ‘ программа вызывает сама себя, i- стартовая величина,не исходная,а которую мы нашли
End If
Next j
End Sub
for k=1 To n:A(k,j)=-Abs(A(k,j)):Next k
1 соответствует разорванной стрелке => больше в найденную вершину не попадём.
Задача о Ханойских башнях.
(классическая задача на использование рекурсии)
Предыстория:
Исторически данная задача возникла как математическая головоломка-шутка, замаскированная под старинную легенду.
Старинная легенда гласит: «Однажды, при сотворении мира, Бог создал три хрустальных (алмазных) стержня, на один из которых помещал 64 диска разных диаметров так, чтобы они образовали пирамиду. Эти диски и стержни находятся в древнем храме. Жрецы этого храма работают день и ночь и переносят диски с одного стержня на другой, руководствуясь двумя правилами:
1) Диски можно брать и переносить только по одному.
2) Нельзя помещать диск большего диаметра над диском меньшего диаметра.
Как только жрецы перенесут все диски со стержня А на стержень С, наступит конец света.
Дата добавления: 2015-01-07; просмотров: 20 | Поможем написать вашу работу | Нарушение авторских прав |