Реферат: Разработка системы задач (алгоритмы-программы) по дискретной математике
Ситуативные задачи: это задачи, формулировка которых представляет собой ситуацию из жизни. Это необходимо для более наглядного представления задачи, а также для того, чтобы сделать задачу более интересной для решения.
Задачи со строгой формулировкой: это задачи, в формулировке которой строго изложена суть задачи. Данные задачи являются задачами более низкого уровня, так как в них не требуется определения тематики задачи, а следовательно, и выбора способа решения, требуется лишь реализация алгоритма на языке программирования.
Задачи с единственным способом решения: это задачи, решить которые можно лишь одним способом, т.е. задачу нельзя рассмотреть с точки зрения различных тематик, таким образом, отсутствует выбор способа решения задачи (Пример: задача о футболистах и т.д.).
Задачи с несколькими способами решения: это задачи, которые могут быть рассмотрены с точки зрения различных тематик и, таким образом, имеют более широкий спектр решений (Пример: задача о метрополитене и т.д.).
Задачи, имеющие решение применимое только к конкретным задачам: это задачи, которые в своей формулировке имеют достаточно много деталей, чтобы их решение было применимо только к конкретным задачам (Пример: задача о роботах).
Задачи, имеющие решение применимое к целому классу подобных задач: это задачи, в формулировке которых не содержится особых деталей, чтобы их решение было применимо к целому классу подобных задач (Пример: задача о метрополитене и т.д.).
Задачи.
Комнаты музея. Составьте алгоритм-программу определения числа комнат в музее и площади каждой комнаты в клетках. План музея показан ниже на рисунке.
11 6 11 6 3 10 6
7 9 6 13 5 7 5
1 10 12 7 13 13 5
13 11 10 8 10 14 13
Цифровая карта
Площадь музея состоит из клеток: m рядов и p столбцов. В каждой клетке такой матрицы (цифровая карта) проставляется число, в котором кодируется наличие стен у данной клетки. Значение числа в каждой клетке является суммой чисел: 1 (клетка имеет стену на западе), 2 (клетка имеет стену на севере), 4 (клетка имеет стену на востоке), 8 (клетка имеет стену на юге). Например, если в клетке стоит число 11 (11=8 + 2 + 1), то клетка имеет стену с южной стороны, с северной и с западной.
Исходные данные представляются в текстовом файле со следующей структурой. Первая строка: m, p – размерность сетки. Вторая строка, третья и следующие строки содержат описание матрицы цифровой карты по строкам. Расчетные данные вывести на экран в следующем порядке: первая строка – площадь каждой комнаты музея, вторая строка – количество комнат в музее.
Пример файла исходных данных:
4 7
11 6 11 6 3 10 6
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)
Диспетчер и милиция. У диспетчера имеется схема города, на которой изображены районы и дороги, связывающие данные районы. На схеме указаны расстояния от одного пункта к другому и направление движения, которое разрешено. Схема выглядит следующим образом:
|
|
|
|
|
|
|
|
|
