Вывести его длину L и города, через которые он проходит.
Вариант 4.
Имеется N городов. Для каждой пары городов (I,J) можно построить дорогу, соединяющую эти два города и не заходящие в другие города. Стоимость такой дороги A(I,J). Вне городов дороги не пересекаются. Написать программу для нахождения самой дешевой системы дорог, позволяющей попасть из любого города в любой другой.
Вариант 5.
Имеется лабиринт, состоящий из комнат, некоторые из которых связаны между собой коридорами. Найти путь между заданными двумя комнатами. Найти кратчайший путь. Найти все пути.
Вариант 6.
Заданный орграф проверить на наличие циклов и при их наличии вывести каждый цикл в виде последовательности вершин циклического пути.
Вариант 7.
В орграфе без циклов, заданном матрицей смежности с весами (длинами) дуг, найти критический путь,то есть путь наибольшей длины, идущий из первой вершины до последней.
Вариант 8.
В орграфе найти все стоки, то есть вершины, в которые только входят дуги, и истоки, из которых только выходят дуги.
Вариант 9.
В заданном неориентированном графе найти кратчайший путь,связывающий две заданные вершины.
Вариант 10.
Найти все вершины графа, к которым существует путь заданной длины (не обязательно кратчайший) от заданной вершины.
Рекомендованная литература
1. Кнут, Д. Искусство программирования. Т. 1. Основные алгоритмы. - М.: Вильямс, 2000.
|
|
|
2. Кнут, Д. Искусство программирования. Т. 3. Сортировка и поиск. - М. : Вильямс, 2000.
3. Вирт Н. Алгоритмы и структуры данных. – СПб.: Невский Диалект, 2008.
4. Новиков, Ф.А. Дискретная математика для программистов. - СПб.: Питер, 2004.
5. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. – М: Лаборатория Базовых Знаний, 2002.
Пример оформления курсовой работы
Министерство образования и науки РФ
СПГЭТУ "ЛЭТИ"
Кафедра АСОИУ
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
К курсовой работе
по дисциплине " ПРОГРАММИРОВАНИЕ"
Тема: " Линейные одно и двунаправленные списки, стеки и очереди"
Выполнил
студент группы 8376
Иванов И.И.
Проверил
Ассистент кафедры АСОИУ
Петров С.С.
Санкт-Петербург
2009
Содержание
| 1. СОДЕРЖАТЕЛЬНАЯ (ИСХОДНАЯ) ПОСТАНОВКА ЗАДАЧИ……………. | 3 |
| 2. АНАЛИЗ И ПРИМЕР РЕШЕНИЯ ЗАДАЧИ…………………………………… | 3 |
| 2.1. Анализ задачи…………………………………………………………………... | 3 |
| 2.2.Пример решения………………………………………………………………… | 4 |
| 3.ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ…………………………………….. | 5 |
| 3.1.Исходные данные……………………………………………….………………. | 5 |
| 3.2.Ограничения на исходные данные……………………………………...….….. | 5 |
| 3.3.Результирующие (выходные) данные…………………………………………. | 5 |
| 3.4.Связь выходных данных с исходными данными…………………………...… | 5 |
| 4. СПЕЦИФИКАЦИЯ ПРОГРАММЫ…………………………………………….. | 6 |
| 4.1. Исходные данные………………………………………………………………. | 6 |
| 4.1.1. Перечень и основные характеристики исходных данных…………………. | 6 |
| 4.1.2. Ограничения на исходные данные………………………………………….. | 6 |
| 4.1.3. Место и форма представления исходных данных…………………………. | 6 |
| 4.2. Функции программы по обработке исключительных ситуаций……………. | 7 |
| 4.3. Выходные данные……………………………………………………………… | 8 |
| 4.3.1. Состав выходных данных………………………………………….………… | 8 |
| 4.3.2. Место и форма представления выходных данных…………………………. | 8 |
| 4.4. Сценарий диалога………………………………………………………………. | 8 |
| 4.4.1. Общая схема диалога………………………………………………………… | 8 |
| 4.4.2. Описание сцен диалога………………………………………………………. | 9 |
| 5. РАЗРАБОТКА СТРУКТУР ДАННЫХ И АЛГОРИТМОВ……………………. | 10 |
| 5.1. Алгоритмы ……………………………………………………………………... | 10 |
| 5.2. Модель структуры данных…………………………………………………….. | 14 |
| 5.3. Структура программы и интерфейс модулей………………………………… | 16 |
| 6. ПРОГРАММА НА ЯЗЫКЕ ТУРБО ПАСКАЛЬ……………………………… | 19 |
| 7. ИСПЫТАНИЯ ПРОГРАММЫ………………………………………………….. | 49 |
| 8. ВЫВОДЫ………………………………………... | 53 |
| 9. СПИСОК ЛИТЕРАТУРЫ | 54 |
|
|
|
|
|
|
СОДЕРЖАТЕЛЬНАЯ (ИСХОДНАЯ) ПОСТАНОВКА ЗАДАЧИ
Смоделировать работу фотоателье, обслуживающего фоторепортеров из разных издательств в порядке поступления от них материалов, причем фотографии папарацци поступают в обработку в последнюю очередь. При подготовке фотографий расходуются соответствующие материалы (реактивы различного вида, бумага разного размера и др.) в необходимом количестве. При отсутствии любого компонента обслуживание прекращается до поступления новых его запасов, но для некоторых издательств есть резерв, который с таких случаях идет для их фоторепортеров. В любой момент должна быть доступна информация о запасах материалов в ателье и необслуженных фоторепортерах.
АНАЛИЗ И ПРИМЕР РЕШЕНИЯ ЗАДАЧИ
Анализ задачи
Имеется очередь фоторепортеров, каждый из которых может быть или обыкновенным репортером или быть сотрудником какой-либо фирмы или быть папарацци. Для каждого фоторепортера известно необходимое число заказов Ki на выполнение работы в ателье. Фотоателье имеет определенное количество бумаги No и Mo фотореактивов (в общем случае эти значения различаются) для общего использования и имеет запасы для конкретных фирм (Nj и Mj) для случая когда общие запасы израсходованы.
|
|
|
Анализируется очередной фоторепортер из очереди, анализируется его фирма. Если репортер обыкновенный, то его заказы выполняются из общих запасов (No-Ki и Mo-Ki) , если репортер из какой-либо фирмы, то сначала его стараются обслужить из общих запасов, а если не хватает, то проверяют наличие его фирмы в списке фирм. Если фирма имеет запасы, то репортер дообслуживается, если нет, то репортер ждет до новых поступлений запасов, т.е. если в очереди стоит репортер фирмы J и ему требуется Хj заказов, а общих запасов не хватает ( Хj> min (No, Mo), тогда Mo- min (No, Mo), No- min (No, Mo), Mj-Xj+ min (No, Mo), Nj-Xj+ min (No, Mo).
Если очередной репортер папарацци, то сначала проверяются все остальные репортеры в очереди, если имеются обыкновенные или репортеры из фирм, то они обслуживаются в первую очередь, если таких нет, то идет обслуживание папарацци. Обслуживание осуществляется, как и обыкновенных репортеров, из общих запасов фотоматериалов, если запасов не хватает, то обслуживание прекращается до поступления новых запасов фотоматериалов.
В любой момент работы программы может быть осуществлено пополнение очереди фоторепортеров.
В любой момент могут быть пополнены запасы фотоматериалов как общие, так и для различных фирм, могут быть добавлены новые фирмы. Фирма может быть удалена из общего списка фирм.
В любой момент времени программа должна выдавать основные данные о ходе проведения работы фотоателье: общее количество репортеров в очереди и количество обслуженных репортеров, количество заказов фотографий от всех репортеров в очереди и количество уже выполненных заказов, должны быть отображены общие запасы по бумаге и реактивам.
В любой момент времени должна быть доступной информация о запасах бумаги и реактивов в фотоателье по каждой фирме.
Необходим просмотр очереди необслуженных фоторепортеров в прямом и обратном направлениях.
Нужно организовать ввод данных с клавиатуры и из файла, вывод данных о составе очереди и наличия материалов в фотоателье записывать в файл.
Пример решения
Пусть фотоателье имеет следующие запасы фотобумаги:
Для общих работ фотобумаги - 30, реактивов -30
Фирма "АААА" фотобумаги - 10, реактивов -10
Фирма "ВВВВ" фотобумаги -20 реактивов -20
Состав очереди фоторепортеров ( в скобках указано необходимое число заказов):
< 1-папарацци (5)>, <2-обычный(10)>, < 3-фирма АААА(10)>,< 4-папарацци(3)>, <5- фирма ВВВВ(15)> ,<6-обычный(5)>.
Обслуживание репортеров будет проходить в следующем порядке:
1. <2-обычный(10)>,
2. < 3-фирма АААА(10)>,
3. <5- фирма ВВВВ(15)> (общие запасы фотоматериалов израсходованы, часть использована из фирмы ВВВВ),
После пополнения запасов для общих работ (например фотобумаги - 50, реактивов -30) обслуживание репортеров будет проходить в следующем порядке:
4. <6-обычный(5)>,
5. < 1-папарацци (5)>,
6. < 4-папарацци (3)>.
После выполнения работ фотоателье будет имееть следующие запасы фотобумаги:
Для общих работ фотобумаги - 37, реактивов -17,
Фирма "АААА" фотобумаги - 10, реактивов -10,
Фирма "ВВВВ" фотобумаги -15 реактивов -15.
ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ
Исходные данные
Каждый репортер характеризуется парой атрибутов (N,K), где N - имя, K - количество фотографий. Пусть задана последовательность очередь репортеров
T1=((N1, K1), (N2, K2), (N3, K3), , (Ni, Ki), , (Nj-1, Kj-1), (Nj, Kj)),
где i -индекс, определяющий номер репортера в очереди, .
Каждая фирма характеризуется набором из трех параметров(Pn, Wn) , где n-имя фирмы, Pn - запасы бумаги фирмы N, Wn - запасы реактивов фирмы N, (P0,W0) - запасы бумаги и реактивов, предназначенные для общего пользования. Задано множество
V1=((P0, W0), (P1, W1), (P2, W2), , (Pi, Wi), , (Pj, Wj), (Pj, Wj)).
Дата добавления: 2018-06-27; просмотров: 436; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!