В классе 121 компьютеров объединены в компьютерную сеть, которая имеет вид прямоугольной сетки размера 11 x 11. Вирус с зараженного компьютера может распространяться на соседние по стороне, если заражены два или более непосредственно с ним связанных компьютера. Какое минимальное количество компьютеров надо заразить изначально, чтобы вся сеть оказалась зараженной?

задан 16 Окт '17 21:03

@sevilllaaa: правильно ли я понял условие -- если клетка не заражена, а два её соседа заражены, то она заражается вирусом? Или тут нечто другое имелось в виду?

(16 Окт '17 21:18) falcao

Если клетка заражена и два соседа её по стороне заражены, то соседние по стороне с ней заражаются.

(16 Окт '17 21:37) sevilllaaa

@sevilllaaa: понятно. В условии вроде как именно это и сказано, но я уточнил, потому что при другой трактовке получилась бы достаточно известная задача, которая как-то была уже на форуме.

(16 Окт '17 21:41) falcao
10|600 символов нужно символов осталось
1

Чтобы процесс продолжался, должен быть хотя бы один заражённый компьютер с по крайней мере двумя заражёнными соседями. Тогда изначально заражено не менее 3 компьютеров. Проверим, что и трёх тоже не хватит. Если есть клетка с двумя заражёнными соседями, то она заразит всех своих соседей, и на этом всё остановится. Только у этой заражённой клетки могут быть >=2 заражённых соседей, что видно из рисунка.

Приведём пример, показывающий, что 4 заражённых клеток хватит. Введём координатную запись типа шахматной, и заразим a2, a3, b1, b2. Тогда a2 заразить угловую клетку a1; b2 заразит b3. Далее a3 заразит a4, b3 заразит b4, и так до правого края. Теперь две строки a,b заражены целиком, и клетки строки b последовательно заразят все клетки строки c, и так далее до конца по всем строкам.

ссылка

отвечен 17 Окт '17 0:16

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×70

задан
16 Окт '17 21:03

показан
532 раза

обновлен
17 Окт '17 0:16

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru