Форум умных людей

Задачи и головоломки => Логические задачи и головоломки => Тема начата: recs от Март 06, 2009, 23:57:53



Название: Задача про распространение компьютерного вируса
Отправлено: recs от Март 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. Проверять несколько компьютеров за один день нельзя, работать ночью тоже.


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


Название: Re: Задача про распространение компьютерного вируса
Отправлено: Smith от Март 12, 2009, 18:11:54
..если долго сидеть на одном месте, можно увидеть, как мимо пронесут тело твоего врага (с)Народная мудрость ;)

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


Название: Re: Задача про распространение компьютерного вируса
Отправлено: drobin от Март 13, 2009, 15:19:45
вирус, теоретически,  может зациклиться и перемещаться между двумя (тремя и т.д.) компьютерами постоянно, не попадая в один из двадцати?
Конечно же, да. В условии движения вируса ограничены только тем, что он каждый день передвигается на соседний.


Название: Re: Задача про распространение компьютерного вируса
Отправлено: Smith от Март 13, 2009, 16:47:54
правильное решение было выложено в посте drobin с маленькой поправкой, что если вирус в нечетных не пойман, тогда в последнем (20-ом) компе нужно проверить дважды, чтобы уровнять ходы и повторить последовательную проверку с конца.
спасибо, было интересно!