2. Создание и обработка типизированных файлов.?????

Билет № 15.

1.Алгоритм генерирования перестановок с минимальным числом транспозиций.

Генерирование всех перестановок за минимальное число транспозиций.

Function B(m As Integer, j As Integer) As Integer

Dim tmp As Integer

If (m Mod 2 = 0) And (m > 2) Then

If j < m - 1 Then B = j Else B = m - 2

Else

B = m - 1

End If

End Function

------------------------------------------------------------

Private Sub PERM(m As Integer)

Dim tmp, k, i As Integer

Dim A As String

If m = 1 Then

A = ""

For k = 1 To n

A = A + Str(P(k))

Next k

lstAntylex.AddItem A

Else

For i = 1 To m

PERM (m - 1)

If i < m Then

tmp = P(B(m, i))

P(B(m, i)) = P(m)

P(m) = tmp

End If

Next i

End If

End Sub

------------------------------------------------------------

Private Sub cmdBegin_Click()

lstAntylex.Clear

n = txtN.Text

ReDim P(n)

For i = 1 To n

tmp = P(i)

P(i) = i

i = tmp

Next

PERM (n)

End Sub

3. Генерирование всех перестановок с минимальным числом транспозиций соседних элементов.

Private Sub cmdBegin_Click()

Dim i, k, tmp, j As Integer

lstAntylex.Clear

n = txtN.Text

ReDim P(n), C(n), PR(n)

For i = 1 To n

P(i) = i

C(i) = 1

PR(i) = True

Next i

C(n) = 0

A = ""

For j = 1 To n

A = A + Str(P(j))

Next j

lstAntylex.AddItem A

i = 1

While i < n

m = m + 1

i = 1

x = 0

While C(i) = n - i + 1

If PR(i) = True Then PR(i) = False Else PR(i) = True

C(i) = 1

If PR(i) Then x = x + 1

i = i + 1

Wend

If i < n Then

If PR(i) Then k = C(i) + x Else k = n - i + 1 - C(i) + x

tmp = P(k)

P(k) = P(k + 1)

P(k + 1) = tmp

A = ""

For j = 1 To n

A = A + Str(P(j))

Next j

lstAntylex.AddItem A

C(i) = C(i) + 1

End If

Wend

End Sub

2. Объявление массивов????

Билет № 16.

1.Введение в теорию графов. Способы представления графов: матрицы смежности и инцидентности, списки инцидентностей.

Граф или неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:

V это множество вершин или узлов,

E это множество пар (в случае неориентированного графа — неупорядоченных) различных вершин, называемых рёбрами.

V (а значит и E) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становятся ложными в случае бесконечных множеств.

Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | — порядком, число рёбер | E | — размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину. Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}.

Степенью degV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Ориентированный граф (сокращённо орграф) G — это упорядоченная пара G: = (V,A), для которой выполнены следующие условия:

V это множество вершин или узлов,

A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v w ведёт от вершины v к вершине w.

Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой G: = (V,E,A), где V, E и A определены так же, как выше.

Понятно, что ориентированный и неориентированный графы являются частными случаями смешанного.

Граф называется:

• связным, если для любых вершин u,v есть путь из u в v.

• сильно связным или ориентированно связным, если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь.

• деревом, если он связный и не содержит простых циклов.

• полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром.

Способы представления графа в информатике

Матрица смежности — таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).

Недостатком являются требования к памяти — очевидно, квадрат количества вершин.

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

Каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа.

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