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

7    9    6   13  5    7    5

1   10  12  7    13  13  5

13 11  10  8    10  14  13

Пример выходных данных:

9  3  8  2  6

5

Идея решения:

Данную задачу можно решить используя метод перебора с возвратом. Используя массив координат перемещения, смотрим, где отсутствуют стены, для каждой клетки, и последовательно двигаемся в ту клетку, в которую возможно, предварительно помечая клетку, в которой уже были. Если мы зашли в тупик, то возвращаемся в клетку, из которой вышли. Одновременно считаем количество клеток в каждой комнате. Когда происходит возврат в начальную точку движения, делаем всю комнату просмотренной (при помощи массива логического типа). Затем ищем клетку, в которой ещё не были и делаем её начальной точкой движения.

(Текст программы см. Приложение 1)

Пират в подземелье. В поисках драгоценных камней пират проваливается в подземелье. План подземелья – матрица N*M комнат с драгоценными камнями. Камни из одной комнаты имеют одинаковую стоимость. Пирату в каждой комнате разрешается взять всего лишь один камень с собой и следовать в любую другую  соседнюю с ней комнату. Каждую из комнат пират может посещать всего лишь один раз. Требуется составить алгоритм-программу определения маршрута посещения пиратом К комнат лабиринта таким образом, чтобы он набрал камней на максимально возможную сумму. Входные и выходные данные: В первой строке входного файла содержатся числа N,M,K. В следующих N строках располагается матрица N*M лабиринта. Каждый элемент матрицы представляется стоимостью камня соответствующей комнаты. Маршрут начинается с левой верхней угловой комнаты лабиринта. Выходные данные: содержат единственное число, равное общей стоимости взятых с собой камней.

Пример файла исходных данных:

3  4  7

1  1  1  1

1  1  2  1

1  1  2  3

Выходные данные для данного примера:

12 

Идея решения: Данную задачу можно решить используя метод перебора с возвратом.  Двигаясь последовательно по комнатам считаем общую стоимость камней и выбирая наибольшую перебираем все возможные варианты передвижения пирата по комнатам.

(Текст программы см. Приложение 2)

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

1

6

2

   

2

3

 

4

4

1

3

5

1

1

1

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

Решение. Входные и выходные данные:

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

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 есть дорога.

1

В двумерном массиве Aplace[1..n,1..m] для каждого робота значениями, равными единице, будем указывать те населенные пункты, в которых данный робот может находиться в данный момент времени. Поясним логику решения на примере. Четыре робота находятся в пунктах 1,2,7,8.

Alink                                                                            Aplace

Первый робот может остаться в первом пункте или пойти во второй или третий пункты, в соответствии со связями в матрице Alink. Таким образом, в первом столбце матрицы Aplace во второй и третьей строках вместо 0 должны появиться 1. Изменения матрицы Aplace для роботов с номерами 2, 3 и 4 выполняются аналогичным образом.

Aplace через 1 момент времени              Aplace в следующий момент времени

Итак, появилась строка или строки матрицы Aplace, состоящие из одних единиц. Эта строка будет соответствовать населенному пункту, в котором возможна встреча роботов.

Однако для пунктов

И при начальном расположении двух роботов в пунктах 1 и 6 встреча роботов никогда не произойдет, и строки Aplace, состоящей из одних единиц, не появится. Это требует введения второй матрицы (Aold), в которой должны фиксироваться достижимые пункты для каждого робота в предыдущий момент времени. Итак, если Aplace и Aold совпадают и нет ни одной строки, состоящей из одних единиц, то встреча роботов невозможна. Это схема решения первого задания. Решение второго задания отличается от первого тем, что требуется найти время Т2=Т1 – 1 (Т1 – время встречи роботов в одном населенном пункте), в которое все роботы находятся в одном из двух (произвольных) населенных пунктов, соединенных дорогой. В этом случае возможна их встреча и вне населенного пункта. Другими словами, в каждый момент времени необходимо проверять (находить) две строки матрицы Aplace, поэлементная логическая сумма которых дает строку, состоящую из одних единиц. При решении задания три матрицу Aplace следует не дополнять элементами, равными единице, а обновлять в соответствии со связями из матрицы Alink. Причем обновление выполнять не для всех роботов одновременно: в нечетные моменты времени 1,3,… для роботов, имеющих скорость 2, а в четные – 2, 4, …для всех роботов.    

    (Текст программы см. Приложение 7)

Вожатый в лагере. У вожатого в отряде дети разных возрастов от 10 до 17. каждое утро дети выходят на линейку, где они должны построится по старшинству (сначала старшие, затем младшие), но на первой линейке дети этого не знали и построились в произвольном порядке. Вожатый составил список возрастов построившихся. Необходимо составить алгоритм – программу, которая бы помогла вожатому как можно быстрее выстроить детей по старшинству.

Страницы: 1, 2, 3