Страниц: [1]
  Печать  
Автор Тема: Задача про распространение компьютерного вируса  (Прочитано 7121 раз)
0 Пользователей и 1 Гость смотрят эту тему.
recs
Новенький
*
Offline Offline

Сообщений: 1

СПАСИБО
-вы поблагодарили: 1
-вас поблагодарили: 1


Просмотр профиля
: Март 06, 2009, 23:57:53 �

Есть сеть из 20 компьютеров, один из них заражен вирусом. По условиям лицензии на антивирус за один день можно проверить только один компьютер. Каждую ночь вирус перемещается на компьютер адрес которого отличается на единицу (с 192.168.1.5 может переместится на 192.168.1.4 или 192.168.1.6). Всего адреса в сети : с 192.168.1.1 по 192.168.1.20. Найти алгоритм позволяющий обнаружить вирус со вероятностью 1. Проверять несколько компьютеров за один день нельзя, работать ночью тоже.

Эти пользователи сказали вам СПАСИБО :

Smith

За это сообщение 1 пользователь сказал спасибо!
Записан
drobin
Давненько
**
Offline Offline

Сообщений: 40

СПАСИБО
-вы поблагодарили: 3
-вас поблагодарили: 7


Просмотр профиля
Ответ #1 : Март 07, 2009, 01:05:07 �

Предположим, что вирус был в на нечетном компе.
Проверяем комп 1. Вирус либо умирает, либо перемещается на комп с четным номером: 2, 4, ... 20.
Проверяем комп 2. В живых мог остаться только вирус, бывший на 4, 6, .. 20. Он перемещается на номер 3, 5, .. 19.
Проверяем комп 3. В живых мог остаться только вирус, бывший на 5, 7, .. 19. Он перемещается на номер 4, 6, .. 20.
...
Возможный ареал вируса сужается, так его можно прижать к стенке, а затем повторить то же самое, но в предположении, что вирус был на четном компьютере (например, провести операцию с конца).

Эти пользователи сказали вам СПАСИБО :

recs, Smith

За это сообщение 2 пользователи сказали спасибо!
Записан
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #2 : Март 12, 2009, 18:11:54 �

..если долго сидеть на одном месте, можно увидеть, как мимо пронесут тело твоего врага (с)Народная мудрость Wink

По сути задачи: вирус, теоретически,  может зациклиться и перемещаться между двумя (тремя и т.д.) компьютерами постоянно, не попадая в один из двадцати? если нет, тогда см. "народную мудрость".. Wink т.е. проверяй один и тот же компьютер... если тебе не везет (а тебе не везет), то максимум 20 проверок соответственно
Записан
drobin
Давненько
**
Offline Offline

Сообщений: 40

СПАСИБО
-вы поблагодарили: 3
-вас поблагодарили: 7


Просмотр профиля
Ответ #3 : Март 13, 2009, 15:19:45 �

вирус, теоретически,  может зациклиться и перемещаться между двумя (тремя и т.д.) компьютерами постоянно, не попадая в один из двадцати?
Конечно же, да. В условии движения вируса ограничены только тем, что он каждый день передвигается на соседний.
Записан
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #4 : Март 13, 2009, 16:47:54 �

правильное решение было выложено в посте drobin с маленькой поправкой, что если вирус в нечетных не пойман, тогда в последнем (20-ом) компе нужно проверить дважды, чтобы уровнять ходы и повторить последовательную проверку с конца.
спасибо, было интересно!

Эти пользователи сказали вам СПАСИБО :

drobin

За это сообщение 1 пользователь сказал спасибо!
Записан
Страниц: [1]
  Печать  
 
Перейти в: