Всего в сети 36 компьютеров. Заразить можно половину (18 компьютеров), чтобы антивирус не смог обнаружить. Размер вируса 243 Кб. Учитывая, что при каждом копировании размер вируса сжимается в 3 раза, возможно следующее количество переходов (заражений) компьютеров:
1 шаг – начальный (243 Кб)
2 шаг – 81 Кб
3 шаг – 27 Кб
4 шаг – 9 Кб
5 шаг – 3 Кб
6 шаг – 1 Кб
После 6-го шага вирус перестанет распространяться. Для получения ответа необходимо найти точку заражения такую, что после 6 шагов распространения зараженных компьютеров было максимальное количество, но не более 18.
Для поиска точки заражения возможно 2 варианта решения:
– ручной поиск места и подсчет числа зараженных компьютеров (с учетом симметричности фигуры);
– автоматизированный поиск точки заражения с использованием программы.
Способ 1.
Необходимо рассмотреть 3 пограничных варианта:
1) заражение центрального компьютера (В1);
2) заражение углового компьютера (В2);
3) заражение крайнего компьютера, расположенного в середине последнего ряда треугольника (В3).
Рисунок 4.1-1 – Варианты начальной точки распространения вируса
Результаты распространения вирусов с точек В1, В2, В3 приведены на рисунке 4.1-2.
В1 В2 В3
Рисунок 4.1-2 – Результаты распространения вируса из точек В1, В2, В3
При начале распространения вируса из точки В1 заражаются 32 компьютера – антивирус обнаружит.
При начале распространения вируса из точки В2 заражаются 12 компьютеров – антивирус не обнаружит, но это меньше 18.
При начале распространения вируса из точки В3 заражаются 30 компьютеров – антивирус обнаружит.
Необходимо искать другие точки заражения, расположенные рядом с В2. Рассмотрим 2 варианта: В4 и В5 (см. рисунок 4.1-3).
В4 В5
Рисунок 4.1-3 – Результаты распространения вируса из точек В4 и В5
При начале распространения вируса из точки В4 заражаются 16 компьютеров – антивирус не обнаружит.
При начале распространения вируса из точки В5 заражаются 18 компьютеров – антивирус не обнаружит, это ровно половина компьютеров.
Ответ, удовлетворяющий условиям – В5, при котором заражаются ровно половина компьютеров (18). С учетом симметричности фигуры вирус необходимо скопировать на любой из компьютеров, указанных на рисунке 4.1-4 цветом и буквой «С».
Рисунок 4.1-4 – Место заражения вирусом первого компьютера («С»)
Способ 2.
Для автоматизации поиска числа зараженных компьютеров и места заражения необходимо задать структуру сети в виде графа. Предлагается реализовать матрицу переходов, где каждой вершине соответствует список смежных вершин, то есть тех компьютеров, которые он может заразить. Однако прежде необходимо пронумеровать вершины (компьютеры) (см. рисунок 4.1‑5).
Рисунок 4.1-5 – Нумерация компьютеров (вершин графа)
Теперь матрица переходов будет выглядеть следующим образом (см. листинг 4.1-1).
Листинг 4.1-1 – Реализация матрицы переходов на языке программирования C++
map<int, vector<int>> matrix = {
{1, {3}},
{2, {3,6}},
{3, {1,2,4}},
{4, {3,8}},
{5, {6,11}},
{6, {2,5,7}},
{7, {6,8,13}},
{8, {4,7,9}},
{9, {8,15}},
{10, {11,18}},
{11, {5,10,12}},
{12, {11,13,20}},
{13, {7,12,14}},
{14, {13,15,22}},
{15, {9,14,16}},
{16, {15,24}},
{17, {18,27}},
{18, {10,17,19}},
{19, {18,20,29}},
{20, {12,19,21}},
{21, {20,22,31}},
{22, {14,21,23}},
{23, {22,24,33}},
{24, {16,23,25}},
{25, {24,35}},
{26, {27}},
{27, {17,26,28}},
{28, {27,29}},
{29, {19,28,30}},
{30, {29,31}},
{31, {21,30,32}},
{32, {31,33}},
{33, {23,32,34}},
{34, {33,35}},
{35, {25,34,36}},
{36, {35}}
};
Алгоритм работы самой программы следующий:
1) В цикле перебираем все вершины от 1 до 36.
2) Обнуляем массив инфицированных узлов и добавляем очередную вершину (шаг 1 заражения).
3) В цикле 5 раз (шаги 2-6 заражения) просматриваем массив инфицированных узлов, и для каждого инфицированного узла добавляем туда всех его соседей из матрицы переходов.
4) Подсчитываем количество зараженных узлов в массиве инфицированных.
Для того, чтобы один и тот же узел не добавлялся несколько раз в массив инфицированных узлов, можно воспользоваться контейнером «множество», в котором каждое значение может храниться только в одном экземпляре.
Пример реализации такого алгоритма приведен в листинге 4.1-2.
Листинг 4.1-2 – Реализация алгоритма перебора всех узлов и поиска числа зараженных компьютеров на языке программирования C++
int main()
{
// множество инфицированных узлов (массив без повторений)
set<int> infected;
// множество инфицированных узлов (массив без повторений)
// на очередном шаге
set<int> step_infected;
// множество соседей узла
set<int> neighbors;
// цикл по всем вершинам
for (int i = 1; i <= 36; i++)
{
// очистка множества инфицированных узлов
infected.clear();
step_infected.clear();
// инфицирование первого узла
infected.insert(i);
// цикл для 2,3,4,5,6 волны инфицирования
for (int s = 1; s < 6; s++)
{
// цикл по уже инфицированным узлам
// заражаем всех их соседей
// и добавляем в массив инфицированных
for (auto it = infected.begin(); it != infected.end(); it++)
{
// соседи текущего зараженного узла
neighbors = matrix[*it];
// добавляем всех соседей в массив инфицированных узлов
// на текущем шаге
step_infected.insert(neighbors.begin(), neighbors.end());
}
// добавляем все инфицированные узлы на текущем шаге
// в общий массив инфицированных узлов
infected.insert(step_infected.begin(), step_infected.end());
}
// вывод на экран финформации
cout << "Start: " << i << " total: " << infected.size() << endl;
}
}
Результаты выполнения программы:
Start: 1 total: 12
Start: 2 total: 18
Start: 3 total: 16
Start: 4 total: 18
Start: 5 total: 24
Start: 6 total: 23
Start: 7 total: 26
Start: 8 total: 23
Start: 9 total: 24
Start: 10 total: 24
Start: 11 total: 30
Start: 12 total: 30
Start: 13 total: 32
Start: 14 total: 30
Start: 15 total: 30
Start: 16 total: 24
Start: 17 total: 18
Start: 18 total: 23
Start: 19 total: 26
Start: 20 total: 32
Start: 21 total: 30
Start: 22 total: 32
Start: 23 total: 26
Start: 24 total: 23
Start: 25 total: 18
Start: 26 total: 12
Start: 27 total: 16
Start: 28 total: 18
Start: 29 total: 23
Start: 30 total: 24
Start: 31 total: 30
Start: 32 total: 24
Start: 33 total: 23
Start: 34 total: 18
Start: 35 total: 16
Start: 36 total: 12
Проанализировав информацию, можно сделать вывод, что наилучшие условия для заражения узлов без обнаружения антивирусом – это 18 узлов (ровно половина), при этом разместить вирус необходимо в одном из узлов с номерами 2,4,17,25,28,34 (рисунок 4.1-6).
Рисунок 4.1-4 – Место заражения вирусом первого компьютера («С»)