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

Задача о футболистах. Футбольная команда поехала на выездную игру, так как команда большая, то все игроки залезли в два автобуса, в произвольном порядке и в разных количествах. В автобусах игроки по привычке построились по возрастанию номеров и сели. Необходимо составить алгоритм – программу, помогающую игрокам, на выходе из двух автобусов, сразу же вставать по возрастанию номеров.

Исходные и выходные данные:

Входной файл содержит три строки. В первой строке находятся два числа – количество игроков в первом и втором автобусах. Вторая строка содержит номера игроков, находящихся в первом автобусе. Третья строка содержит номера игроков, находящихся во втором автобусе:

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