2. Примеры выполнения курсовой работы

2.I. Разработка эффективных алгоритмов

Пример 2.1.

Постановка задачи. Необходимо ввести таблицу покрытий, а также номера строк таблицы. Алгоритм должен определить, являются ли эти строки покрытием.

Математическое описание задачи и методов ее решения

Здесь необходимо описать математическую постановку задачи о покрытии и привести названия методов для ее решения с их краткой характеристикой.

Словесное описание алгоритма

1. Ввод числа строк (m) и числа столбцов (n) таблицы покрытия.

2. Ввод таблицы покрытия.

3. Ввод номеров строк таблицы покрытия.

4. Рассчитываем суммы элементов (S) по столбцам таблицы (в суммы включаются только проверяемые строки), начиная с первого до последнего (n-го), либо пока не встретится сумма, равная 0.

5. Если все рассчитанные суммы ненулевые, значит, проверяемые строки являются покрытием. В противном случае - не являются.

Разумеется, это не единственный метод для решения задачи. Поэтому имеет смысл сравнить несколько предлагаемых Вами способов.

Выбор структур данных и его обоснование

Из анализа задачи и её данных видно, что алгоритм должен работать с таблицей покрытия и с некоторыми переменными, которые представлены ниже (все переменные - целого типа):

m - количество строк таблицы покрытия;

n - количество столбцов таблицы покрытия;

kol - количество строк, проверяемых на покрытие;

n_str - промежуточная переменная для хранения номера строки;

i - переменная цикла.

Таблица покрытия - это двумерная матрица. Ее целесообразно представить в виде двумерного массива - A(m, n). D - одномерный массив для хранения номеров проверяемых строк матрицы покрытия. Для хранения номеров выбран массив, поскольку количество строк, хотя и неизвестно заранее, ограничено количеством строк матрицы покрытия (m).

Схема алгоритма

Схема алгоритма строится в соответствии с технологией проектирования «сверху вниз» [5], по которой вначале изображается схема алгоритма в общем виде, а затем она всё более детализи-руется вплоть до простых операторных вершин. В окончательном варианте, который будет представлен на графическом листе, следует привести основную схему, которая может включать в себя несколько процедур (функций), а также привести сами процедуры (функции). Для данного примера схема алгоритма представлена на рис. 2.1.

Описание схемы алгоритма. Этот раздел нужен, если в схеме алгоритма нет комментариев либо они слишком кратки.

Алгоритм работает следующим образом. Сначала вводятся исходные данные (блоки 1, 2; в комментариях определено назначение данных), затем организуется цикл записи номеров строк, проверяемых на покрытие, в массив D (блоки 3-6). В блоке 7 вызывается функция POKR(D, kol, A , n), вычисляется её значение, которое затем присваивается условию usl; в соответствии со значением условия (проверка осуществляется в блоке 8) выдаются сооб-щения ‘да’ либо ’нет’ (блоки 9 и 10).

Описание схемы алгоритма. Этот раздел нужен, если в схеме алгоритма нет комментариев либо они слишком кратки.

Алгоритм работает следующим образом. Сначала вводятся исходные данные (блоки 1, 2; в комментариях определено назначение данных), за-тем организуется цикл записи номеров строк, проверяемых на покрытие, в массив D (блоки 3-6). В блоке 7 вызывается функция POKR(D, kol, A, n), вычисляется её значение, которое затем присваивается условию usl; в соответствии со значением условия (проверка осуществляется в блоке 8) выдаются сообщения ‘да’ либо ’нет’ (блоки 9 и 10).

Подпрограммы и функции.

В данном случае используется процедура INS(NEL, LIST, POS) и функция POKR(D, kol, A, n). Процедура INS(NEL LIST, POS) предназначена для вставки нового элемента NEL в список LIST в позицию POS; для реализации этой процедуры может быть использован односвязный список. Функция POKR - более сложная, и потому она описана подробнее.

Словесное описание алгоритма, используемого в функции

Функция POKR(D,kol, A, n) определяет, являются ли строки матрицы А, номера которых заданы в списке D, покрытием. Здесь kol – количество элементов в массиве D, n – количество столбцов матрицы A. Функция возвращает 1, если заданные строки матрицы A образуют покрытие, 0 - в противном случае. Для функции POKR(D, kol, A, n) используется алгоритм, описанный в пункте 4 словесного описания алгоритма для решения всей задачи.

Описание локальных перемен-ных (все - целые):

S - переменная для накопления суммы (целая);

i, j - переменные для органи-зации циклов;

k - переменная для выбора номера строки из списка D.

Схема алгоритма для функции POKR представлена на рис. 2.2.

Описание схемы алгоритма функции. Функция POKR(D, kol, A, n) определяет, являются ли строки матрицы А, номера которых заданы в списке D, покрытием. Здесь kol - количество элементов в массиве D, n - количество столбцов матрицы A. Функция возвращает 1, если заданные строки матрицы A образуют покрытие, 0 - в противном случае.

Алгоритм работает следующим образом. При вызове в основном алгоритме функции POKR(D, kol, A, n) в неё передаются параметры D, kol, A, n; затем организуется внешний цикл (блоки 2-8) прохода по всем стол-бцам матрицы A и внутренний цикл (блоки 3-6) расчёта суммы S по i-му столбцу для заданных строк, проверяемых на покрытие. В качестве признака отсутствия покрытия используется значение суммы S=0, по-скольку если в некотором столбце на всех позициях, соответствующих рассматриваемым строкам, будут нули, то этого достаточно, чтобы констатировать отсутствие покрытия (в этом случае можно не проверять остальные столбцы). Вычисление S производится в блоке 5 для выбран-ной из массива D (блок 4) строки с номером k. В блоке 7 проверяется условие S=0 и в зависимости от его значения принимается решение о том, какое значение функции возвращается в основной алгоритм (блоки 9 и 10), где они присваиваются переменной usl. Отметим, что если цикл прохода по столбцам полностью завершился, значит, ни одна сумма по столбцам не равна 0, что означает, что заданные строки являются решением задачи о покрытии.

Контрольные примеры решения задачи с помощью алгоритма.

Пусть задача о покрытии задана матрицей (табл.2.1). Требуется определить

а) являются ли строки А1, А3 решением задачи о покрытии;

б) являются ли строки А1, А3, А4 решением задачи о покрытии.

П

Таблица 2.1

A	1	2	3	4	5
A1	1		1		1
A2	1	1		1
A3				1	1
A4	1	1

ошаговое решение:

а) i=1, S=2;

i=2, S=0; выход из функции POKR, возвращается 0, выдаётся сообщение «нет».

б) i=1, S=2;

i=2, S=1;

i=3, S=2;

i=4, S=1;

i=5, S=2;

выход из функции POKR, возвращается 1, выдаётся сообщение «да».

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