Диспетчеру поступают запросы из патрульных машин милиции, патрульные сообщают район, где они находятся и район, в который им необходимо попасть на вызов. Требуется составить алгоритм – программу, которая бы помогла диспетчеру найти минимальное расстояние, которое предстоит покрыть патрульной машине. Необходимо учесть направление движения, которое разрешено на данном участке пути.
Решение. Входные и выходные данные:
Первая строка входного файла содержит количество районов города. Затем идет матрица смежности, где занесены все пути из одной вершины в другую с расстоянием:
6
0 3 7 0 0 0
1 0 2 0 0 1
0 1 0 4 4 0
0 0 0 0 1 5
0 0 1 0 0 3
0 0 0 2 0 0
Номер района, из которого выехала милицейская машина и в который ей необходимо попасть вводятся с клавиатуры.
Выходные данные:
Единственное число, которое представляет собой минимальный путь, который предстоит покрыть милицейской машине.
Идея решения: данную задачу можно решить с помощью алгоритма поиска кратчайших путей в графе (алгоритм Дейкстры).
(Текст программы см. Приложение 3)
Задача о футболистах. Футбольная команда поехала на выездную игру, так как команда большая, то все игроки залезли в два автобуса, в произвольном порядке и в разных количествах. В автобусах игроки по привычке построились по возрастанию номеров и сели. Необходимо составить алгоритм – программу, помогающую игрокам, на выходе из двух автобусов, сразу же вставать по возрастанию номеров.
Исходные и выходные данные:
Входной файл содержит три строки. В первой строке находятся два числа – количество игроков в первом и втором автобусах. Вторая строка содержит номера игроков, находящихся в первом автобусе. Третья строка содержит номера игроков, находящихся во втором автобусе:
5 8
4 7 9 15 23
1 2 3 5 6 8 10 17
Выходные данные: номера футболистов, вышедших из автобусов в порядке возрастания. Выходные данные для данного примера:
1 2 3 5 6 7 8 9 10 15 17 23
Идея решения:
Оптимального решения данной задачи можно добиться, используя метод сортировки слияниями.
(Текст программы см. Приложение 4)
Задача о семьях. На сельской улице живут Ивановы и Петровы. Необходимо, используя минимальное число обменов, расселить их так, чтобы Ивановы жили с одного конца улицы, а Петровы – с другого.
Исходные и выходные данные. С клавиатуры вводится n - количество человек, проживающих на данной улице. Затем вводится массив А[1..n], состоящий из 0 и 1, где 0 – Петров, 1 – Иванов. Выходными данными является число обменов.
Идея решения:
Задача по методам сортировки. Один из способов её решения заключается в следующем. Пусть Ивановы должны жить в начале улицы, а Петровы – в конце. По индексу i (i<j) ищем первого Петрова, i увеличивается с шагом 1. Если нашли, то ищем Иванова с конца улицы – индекс j, он уменьшается. Если пара составлена, то совершаем обмен, и так до тех пор, пока i будет меньше j.
(Текст программы см. Приложение 5)
Метро. Дана схема метрополитена, с направлениями движения поездов до других станций. Станции пронумерованы. Необходимо составить алгоритм – программу, которая выводит номера станций, в которые можно попасть из станции с номером k (k вводится с клавиатуры). Схема метрополитена имеет следующий вид:
Решение:
Если входные данные представить в виде матрицы смежности путей метрополитена, то при помощи алгоритма нахождения матрицы достижимости можно решить данную задачу. Выходные данные: это индексы столбцов матрицы достижимости k – той строки, которые в значении имеют 1.
Исходные данные для данной задачи будут иметь вид:
6 {первая строка – это количество станций метро}
0 1 1 1 0 0
0 0 1 0 1 0
0 0 0 0 1 1
0 0 0 0 0 1
0 0 0 0 0 1
0 0 0 1 1 0
Пример выходных данных для данного примера:
Введите пункт отправки – 4
5 6
(Текст программы см. Приложение 6)
Роботы. Пункты с номерами 1,2,…,N (N<=50) связаны сетью дорог, длины которых равны 1. Дороги проходят на разной высоте и пересекаются только в пунктах. В начальный момент времени в некоторых пунктах находятся M роботов. Все роботы начинают двигаться с постоянной скоростью 1. Останавливаться или менять направление они могут только в пунктах.
a) Требуется найти минимальное время Т1, через которое все роботы могут встретиться в одном пункте, указать этот пункт или сообщить, что такая встреча невозможна.
b) Если встреча возможна, то найти время Т2<=T1, через которое встреча может произойти и вне пунктов.
c) Пусть роботам запрещена какая – либо остановка, и скорость равна 1 или 2. При этих условиях найти минимальное время Т, через которое произойдет их встреча, или сообщить, что встреча невозможна.
Примечания:
· Для задачи (в) можно указать, что М равно 2 или 3.
· При решении задач (а) и (б) данные о скоростях игнорируются.
Решение.
Идея решения основана на свойстве достижимости одной вершины из другой на графе.
Данные о связях между пунктами будем хранить в массиве Alink[1..n,1..n], элементы которого равны 0 или 1. Значение Alink[i,j]=1 говорит о том, что между пунктами i и j есть дорога.
