Разработка системы задач (алгоритмы-программы) по дискретной математике — страница 9

графе (алгоритм Дейкстры). (Текст программы см. Приложение 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 вводится с клавиатуры). Схема метрополитена имеет следующий вид: 1 2 3 4 5 6

Решение: Если входные данные представить в виде матрицы смежности путей метрополитена, то при помощи алгоритма нахождения матрицы достижимости можно решить данную задачу. Выходные данные: это индексы столбцов матрицы достижимости 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 Пример выходных