Применение теории графов в информатике (стр. 4 из 5)

Рис. 18. Кнопка «Выравнивать по сетке»

Если выбрать две различные вершины (щелчком левой кнопки мыши) нажать на кнопку, то программа найдет кратчайший путь между вершинами.

Рис. 19. Кнопка «Нахождение кратчайшего пути между вершинами»

2. Практическая часть

2.1 Общая характеристика задачи

Агентство по грузоперевозкам "Летучий голландец" предоставляет услуги по перевозке грузов по различным маршрутам. Данные о маршрутах, выполненных в течение недели, по каждому водителю приведены на рис. 1.

Сведения о выполненных маршрутах
№ п/п	ФИО водителя	Марка автомобиля	№ рейса	Выполнено рейсов, шт.	Протяженность рейса, км.	Расход топлива на 100 км, л	Израсходовано топлива, л	Грузоподъемность, т	Вес перевезенного груза, т
1	Соловьев В.В.	КАМАЗ	А112	4
2	Михайлов С.С.	ЗИЛ	С431	3
3	Кузнецов Я.Я.	МАЗ	А112	5
4	Иванов К.К.	МАЗ	М023	7
5	Сидоров А.А.	ЗИЛ	В447	2
6	Волков Д.Д.	КАМАЗ	С431	8
7	Быков Л.Л.	КАМАЗ	В447	4
ИТОГО	Х	Х
В СРЕДНЕМ	Х	Х

Рис. 1. Данные о маршрутах

Справочные данные о технических характеристиках автомобилей и протяженности маршрутов представлены на рис. 2.

Протяженность рейсов
№ п/п	№ рейса	Протяженность рейса, км
1	А112	420
2	В447	310
3	М023	225
4	С431	250

Технические характеристики автомобилей
№ п/п	Марка автомобиля	Расход топлива на 100 км, л	Грузоподъемность, т
1	ЗИЛ	42	7
2	КАМАЗ	45	16
3	МАЗ	53	12

Рис. 2 Данные о технических характеристиках автомобилей и протяженности маршрутов

1. Построить таблицы по приведенным ниже данным.

2.Выполнить расчет количества израсходованного топлива каждым водителем и веса перевезенного груза, данные расчета занести в таблицу.

3. Организовать межтабличные связи для автоматического формирования ведомости расхода топлива за неделю.

4. Сформировать и заполнить ведомость расхода топлива каждым водителем за неделю.

5. Результаты расчета количества израсходованного топлива за неделю представить в графическом виде.

2.2 Описание алгоритма решения задачи

1. Запустить табличный процессор МS Excel.

2. Создать книгу с именем “Летучий голландец”.

3. Лист 1 переименовать в лист с названием Сведения.

4. На рабочем листе Сведения создать таблицу Сведения о выполненных маршрутах (табл. №1).

5. Заполнить таблицу Сведения о выполненных маршрутах.

6. Лист 2 переименовать в лист Характеристики.

7. На рабочем листе Характеристики создать таблицу, в которой будут содержаться технические характеристики автомобилей (табл. №2).

8. Заполнить таблицу со списком Технических характеристик автомобилей.

9. Лист 3 переименовать в лист Протяженность.

10. На рабочем листе Протяженность, создать таблицу протяженности рейсов (табл. №3).

11. Заполнить таблицу Протяженность рейсов исходными данными.

12. Лист 4 переименовать в Ведомость (табл. №4).

13. На рабочем листе Ведомость создать таблицу Ведомость расхода топлива.

14. Лист 5 переименовать в лист График (табл. №5).

15. На рабочем листе График создать график учета расхода топлива на каждого водителя.

16. Заполнить графу Израсходовано топливо таблицы “Сведения о выполненных маршрутах” находящейся на листе Сведения следующим образом:

Занести в ячейку H3 формулу: =СУММ(F3*G3/100).

Размножить введенную в ячейку Н3 формулу для остальных ячеек (с Н4 по Н7) данной графы, соответственно меняя строки F3, G3 на соответствующие строкам в столбце Н.

Таким образом, будет выполнен автоматический подсчет израсходованного топлива.

17. Заполнить графу Вес перевезенного груза таблицы “Сведения о выполненных маршрутах” находящейся на листе Сведения следующим образом:

Занести в ячейку J3 формулу: =СУММ(I3*E3).

Размножить введенную в ячейку J3 формулу для остальных ячеек (с J4 по J7) данной графы, соответственно меняя строки I3, E3 на соответствующие строкам в столбце J.

Таким образом, будет выполнен автоматический подсчет суммы перевезенного груза.

18. На листе Ведомость заполнить графу Израсходовано топлива следующим образом:

Занести в ячейку Е12 формулу: =СУММ(Сведения!H3).

Размножить введенную в ячейку Е12 формулу для остальных ячеек (с Е12 по Е18) данной графы, соответственно меняя строки формулы с Н3 по Н9.

Таким образом, будет выполнен автоматический подсчет израсходованного топлива.

19. На листе Ведомость заполнить графу Выполнено рейсов следующим образом:

Занести в ячейку D12 формулу =СУММ(Сведения!E3).

Размножить введенную в ячейку D12 формулу для остальных ячеек (с D13 по D18) данной графы, соответственно меняя строки формулы с Е3 по Е9.

Таким образом, будет выполнен автоматический подсчет количества выполненных рейсов.

20.По результатам заполненных параметров в таблице «Ведомость расхода топлива» создать график расхода топлива на листе «график».

Таблица №1

Сведения о выполненных маршрутах
№ п/п	ФИО водителя	Марка автомобиля	№ рейса	Выполнено рейсов,шт.	Протяженность рейсов,км	Расход топлива на 100км,л	Израсходовано топлива,л	Грузоподъемность,т	Вес перевезенного груза,т
1	Соловьев В.В.	КАМАЗ	А112	4	420	45	189	16	64
2	Михайлов С.С.	ЗИЛ	С431	3	250	42	105	7	21
3	Кузнецов Я.Я.	МАЗ	А112	5	42	53	222,6	12	60
4	Иванов К.К.	МАЗ	М023	7	225	53	119,25	12	84
5	Сидоров А.А.	ЗИЛ	В447	2	310	42	130,2	7	14
6	Волков Д.Д.	КАМАЗ	С431	8	250	45	112,5	16	128
7	Быков Л.Л.	КАМАЗ	В447	4	310	45	139,5	16	64
ИТОГО	33	2185	325	1018,05	86	435
В СРЕДНЕМ	4,71	312,14	46,43	145,44	12,29	62,14

Таблица №2

Технические характеристики автомобилей
№ п/п	Марка автомобиля	Расход топлива на 100 км, л	Грузоподъемность, т
1	ЗИЛ	42	7
2	КАМАЗ	45	16
3	МАЗ	53	12

Таблица№3

Протяженность рейсов
№ п/п	№ рейса	Протяженность рейса, км
1	А112	420
2	В447	310
3	М023	225
4	С431	250

Таблица №4

ФИО водителя	№ рейса	Выполнено рейсов, шт	Израсходовано топлива, л
Соловьев В.В.	А112	4	189
Михайлов С.С.	С431	3	105
Кузнецов Я.Я.	А112	5	222,6
Иванов К.К.	М023	7	119,25
Сидоров А.А.	В447	2	130,2
Волков Д.Д.	С431	8	112,5
Быков Л.Л.	В447	4	139,5
ИТОГО	33	1018,05

Бухгалтер _________________________

Таблица №5

Заключение

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

Графы и информация

Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.

Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось.