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

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

данных для данного примера: Введите пункт отправки – 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 2 3 4 5 6 7 8 1 В двумерном массиве Aplace[1..n,1..m] для каждого робота значениями, равными единице, будем указывать те населенные пункты, в которых данный робот может находиться в данный момент времени. Поясним логику решения на примере. Четыре робота находятся в пунктах 1,2,7,8. Alink Aplace 1 2 3 4 5 6 7 8 1 2 3 4 1 0 1 1 0 0 0 0 0 1 1 0 0 0 2 1 0 1 0 0 0 0 0 2 0 1 0 0 3 1 1 0 1 1 0 0 0 3 0 0 0 0 4 0 0 1 0 0 1 0 0 4 0 0 0 0 5 0 0 1 0 0 1 0 0 5 0 0 0 0 6 0 0 0 1 1 0 1 1 6 0 0 0 0 7 0 0 0

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

8 0 0 0 1 1 2 3 4 1 1 1 0 0 2 1 1 0 0 3 1 1 1 1 4 1 1 1 1 5 0 0 1 1 6 0 0 1 1 7 0 0 1 1 8 0 0 1 1 Итак, появилась строка или строки матрицы Aplace, состоящие из одних единиц. Эта строка будет соответствовать населенному пункту, в котором возможна встреча роботов. Однако для пунктов SHAPE \* MERGEFORMAT 1 2 3 4 5 6 И при начальном расположении двух роботов в пунктах 1 и 6 встреча роботов никогда не произойдет, и строки Aplace, состоящей из одних единиц, не появится. Это требует введения второй