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

  • Просмотров 5971
  • Скачиваний 213
  • Размер файла 88
    Кб

начальной точкой движения. (Текст программы см. Приложение 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 1 3 4 5 7 2 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 Номер района, из которого выехала милицейская машина и в который ей необходимо попасть вводятся с клавиатуры. Выходные данные: Единственное число, которое представляет собой минимальный путь, который предстоит покрыть милицейской машине. Идея решения: данную задачу можно решить с помощью алгоритма поиска кратчайших путей в