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

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

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

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

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

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