Материал: 12562633_1109924Ispol_zo
ББК 681.142.2
В 19
Рецензент: С.М. Семенов, канд. техн. наук, зав. кафедрой ИСКТ
Васильев Б.К.
В 19 ИСПОЛЬЗОВАНИЕ ТЕХНОЛОГИИ ГОТОВЫХ РЕШЕНИЙ В ПРОГРАММИРОВАНИИ: Лабораторный практикум. – Владивосток: Изд-во ВГУЭС,
2004. – 44 с.
В практикуме рассмотрены типовые лабораторные работы курса «Технология программирования».
Предназначен для студентов, обучающихся по специальности 220100 «Вычислительные машины, системы, комплексы и сети» для очной и заочной форм обучения.
Печатается по решению РИСО ВГУЭС
ББК 681.142.2
© Издательство Владивостокского государственного университета экономики и сервиса, 2004
1
ВВЕДЕНИЕ
Разработка программ давно превратилась из кустарного ремесла в промышленное производство, оставаясь к тому же составной частью науки программирования, которую относят то к искусству [Кнут], то к разновидности фольклора [Турский].
Современные программные продукты разрабатываются, как правило, по установившимся стандартам, а заняты в этом производстве многие разработчики. В лабораторных работах курса «Технология программирования» мы имеем дело с такими аспектами технологии этого производства, как разработка в коллективе, тестирование программ, создание графического пользовательского интерфейса.
Наряду с рассмотрением практических аспектов разработки программных продуктов рассмотрим темы лабораторных работ и предпочтительную последовательность действий при их выполнении.
Отметим, что в целом при выполнении лабораторных работ применяется технология использования готовых программных решений (алгоритмических, технологических, в области разработки графического интерфейса конечного пользователя) и реинженеринга, т.е. повторного использования написанного ранее кода.
2
1. ПРОГРАММНЫЙ ПРОЕКТ
Собственно говоря, как и любой другой проект, программный проект (ПП) имеет определенные рамки, прежде всего это рамки – временные. Срок выполнения проекта можно определить, если произвести анализ необходимых работ и произвести разбиение проекта на законченные отдельные виды деятельности. К ним относятся не только алгоритмизация и кодирование, но и освоение новых программных продуктов, приобретение необходимых программных и аппаратных средств, тестирование и верификация.
Каждый вид деятельности в ПП характеризуется временной оценкой (сроком выполнения), одни виды деятельности не могут быть начаты прежде чем будут выполнены другие (существует зависимость видов деятельности). Некоторые виды деятельности могут выполняться параллельно различными людьми, а некоторые – нет.
При выполнении декомпозиции ПП по видам деятельности удобно все работы представить в виде ориентированного графа, вершинами которого являются этапы выполнения работ (от вершины СТАРТ до вершины КОНЕЦ), а ребрами – выполняемые работы.
Такой граф называют сетевым графиком проекта.
Анализ сетевого графика
Поскольку каждому ребру приписана числовая характеристика – время выполнения, то можно ставить вопрос о нахождении критического пути на данном графе, то есть пути от вершины СТАРТ до вершины
КОНЕЦ, доставляющего максимум сумме величин tij , приписанных
ребрам, входящим в этот путь.
Находить критический путь можно многими способами. Достаточно хорошо работающим даже на графах с большим количеством ребер является алгоритм динамического программирования, основанный на представлении процесса нахождения решения в виде этапов (шагов) и запоминании результатов предыдущих шагов [Кузин, гл.14].
Составим функциональное уравнение Беллмана:
V |
max( ti |
v |
),i |
1,2,...n 1; j 1,2,...n; |
i |
j |
j |
|
|
|
|
|
Vn |
0, |
где величины Vi (i=1, 2, … n-1) являются критическими временами частичных путей от i-й до конечной вершины. Вычисления начнем с конца, полагая
Vi1 tin ,i 1,2,...n 1;
Vn1 tnn 0.
3
На втором шаге
V 2 |
max( t |
V1),i 1,2,...n 1; j 1,2,...n. |
i |
ij |
j |
Дальнейшие вычисления выполняются по рекуррентной формуле
V k |
max( t |
ij |
V k 1 ),i 1,2,...n 1; j |
1,2,...n; k 1. |
||
i |
|
j |
|
|
|
|
V k |
0; t |
ij |
0. |
|
|
|
n |
|
|
|
|
|
|
Вычисления закончатся, когда V k |
V k 1 |
,i |
1,2,...n. |
|||
|
|
|
i |
i |
|
|
Рассмотрим пример решения для следующего графа (рис. 1):
Рис. 1. Пример сетевого графика (Е1=СТАРТ, Е12=КОНЕЦ)
При решении значения Vki будем заносить в табл. 1, а в те элементы таблицы, для которых отсутствует переход, будем заносить большое отрицательное число (- ).
Таблица 1
Значения Vki
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
7 |
8 |
9 |
10 |
11 |
12 |
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
- |
- |
- |
- |
- |
- |
|
- |
- |
5 |
3 |
2 |
0 |
2 |
- |
- |
- |
8 |
- |
13 |
|
11 |
13 |
7 |
6 |
2 |
0 |
3 |
20 |
18 |
17 |
16 |
18 |
16 |
|
17 |
13 |
10 |
6 |
2 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
27 |
27 |
25 |
20 |
18 |
22 |
|
17 |
13 |
10 |
6 |
2 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
31 |
27 |
29 |
20 |
18 |
22 |
|
17 |
13 |
10 |
6 |
2 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
33 |
27 |
29 |
20 |
18 |
22 |
|
17 |
13 |
10 |
6 |
2 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
33 |
27 |
29 |
20 |
18 |
22 |
|
17 |
13 |
10 |
6 |
2 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4
Лабораторная работа 1
Сетевой график
Требования
Четыре часа на выполнение, язык реализации – С или С++.
Алгоритмическая реализация
Смотри ранее рассмотренный анализ сетевого графика.
Реализация
Диалог в консольном приложении.
Написать программу для нахождения критического пути на графе, имея в виду предметную область – анализ времени выполнения программного продукта. Ввод данных в диалоговом режиме и из файла, предусмотреть сохранение файла данных для последующего использования. Использовать для внутреннего представления графа матрицу смежности [Ахо и др.].
Написание программы
При написании программы тщательно продумайте используемую структуру данных (граф). Проверьте, как сохраняется введенный граф, как читаются ранее записанные в файл данные. Для удобства отладки реализуйте вывод таблицы после каждого шага алгоритма.
5