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