Билет 4

1. Все подпрограммы на языке Паскаль (подмножестве Object Pascal для системы программирования DELPHI версии 3.0 и выше), передаются пользователям в виде модулей (Unit) языка Паскаль. При этом все подпрограммы, вызываемые из целевой подпрограммы Библиотеки, запаковываются в один ZIP-файл с именем целевой подпрограммы.

Для того чтобы можно было воспользоваться подпрограммами на языке Паскаль, необходимо обеспечить наличие всех заказываемых в uses модулей:

• системных библиотечных модулей ( Math, SysUnils в системе DELPHI ), вызываемых подпрограмм Библиотеки численного анализа, необходимых для конкретной целевой программы, общих библиотечных модулей Библиотеки численного анализа, содержащих стандартные функции, аналогичные имеющимся в языке Фортран, но отсутствующие в языке Паскаль, а также список описаний целого ряда используемых в Библиотеке типов объектов.

Тестовые примеры к подпрограммам Библиотеки реализованы в виде функций типа String языка Паскаль. Вся информация, выводимая из тестового примера (пояснительные тексты, числовые входные данные, а также результаты работы подпрограммы), помещаются в стандартную переменную Result. При этом числовые данные преобразуются в текстовую форму с помощью стандартной процедуры DELPHI Format.

В итоге выводимая информация с помощью стандартной процедуры WRITE помещается в файл с именем тестового примера и с расширением RES. Последнее действие оформлено в виде обращения из тестового примера к стандартной процедуре Библиотеки численного анализа UtRes.

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

Модуль SYSTEM является основной библиотекой Турбо Паскаля. Он реализует подпрограммы для всех встроенных возможностей, таких как ввод/вывод, обработка строк, эмуляция арифметического сопроцессора, управление оверлеями и динамическое распределение памяти. Модуль SYSTEM используется автоматически любым модулем или программой и никогда не указывается в предложении USES.

Модуль Dos реализует ряд очень полезных программ операционной системы и обработки файлов. Ни одна из программ модуля Dos не определена в стандартом Паскале и поэтому они размещены в собственном модуле.

Модуль Сrt содержит подпрограммы управления текстовым выводом на экран дисплея, звуковым генератором и чтения клавиатуры.

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

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

Пусть задан граф G=(V,E), где V— множество вершин графа, E— множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

Из множества всех белых вершин выберем любую вершину, обозначим её u1.

Выполняем для неё процедуру DFS(u1).

Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

Процедура DFS (параметр — вершина uԑV )

Перекрашиваем вершину u в черный цвет.

Для всякой вершины w, смежной с вершиной u и окрашенной в белый цвет, выполняем процедуру DFS(w). пример реализации:

const

MAX_N = 10;

var

graph: array [1..MAX_N, 1..MAX_N] of boolean;

visited: array [1..MAX_N] of boolean;

procedure dfs(v: integer);

var

i: integer;

begin

visited[v] := true;

for i := 1 to MAX_N do

if graph[v, i] and not visited[i] then

dfs(i);