Всего в сети 54 компьютера. Заразить можно половину (27 компьютеров), чтобы антивирус не смог обнаружить. Размер вируса 81 Кб. Учитывая, что при каждом копировании размер вируса сжимается в 3 раза, возможно следующее количество переходов (заражений) компьютеров:
1 шаг – начальный (81 Кб)
2 шаг – 27 Кб
3 шаг – 9 Кб
4 шаг – 3 Кб
5 шаг – 1 Кб
После 5-го шага вирус перестанет распространяться. Для получения ответа необходимо найти точку заражения такую, что после 5 шагов распространения зараженных компьютеров было максимальное количество, но не более 27.
Для поиска точки заражения возможно 2 варианта решения:
– ручной поиск места и подсчет числа зараженных компьютеров (с учетом симметричности фигуры);
– автоматизированный поиск точки заражения с использованием программы.
Способ 1.
Можно рассмотреть 3 варианта, учитывая симметричность фигуры:
1) заражение центрального компьютера (В1);
2) заражение компьютера на расстоянии 1 от центрального (В2);
3) заражение компьютера на расстоянии 2 от центрального (В3).
В1 В2 В3
Рисунок 4.2-1 – Результаты распространения вируса из точек В1, В2, В3
При начале распространения вируса из точки В1 заражаются 33 компьютера – антивирус обнаружит.
При начале распространения вируса из точки В2 заражаются 28 компьютеров – антивирус обнаружит.
При начале распространения вируса из точки В3 заражаются 24 компьютеров – антивирус не обнаружит, но это меньше половины (27).
Очевидно, что при рассмотрении точек заражения ближе к границам фигуры, количество зараженных компьютеров будет меньше. Поэтому необходимо рассмотреть еще один вариант (В4) и убедиться, что больше 24 и меньше 27 компьютеров заразить нет возможности (рисунок 4.2-2).
Рисунок 4.2-2 – Результаты распространения вируса из точки В4
При начале распространения вируса из точки В4 заражается 31 компьютер – антивирус обнаружит.
С учетом симметричности фигуры ответом будет заражение 24 компьютеров без обнаружения антивирусом. Узел, на который необходимо скопировать вирус, указан на рисунке 4.2-3.
Рисунок 4.2-3 – Место заражения вирусом первого компьютера («С»)
Способ 2.
Для автоматизации поиска числа зараженных компьютеров и места заражения необходимо задать структуру сети в виде графа. Однако прежде необходимо пронумеровать вершины (компьютеры) (см. рисунок 4.2‑4). Предлагается нумеровать строки и столбцы для каждого узла.
Рисунок 4.2-4 – Нумерация узлов
Легко заметить зависимости в номерах соседних узлов:
1) Соседи справа есть у всех, кроме крайних правых узлов (номера которых последние в строке). Его номер равен номеру столбца узла плюс 1.
2) Соседи слева есть у всех, кроме крайних левых узлов (номера которых равны 0). Его номер равен номеру столбца узла минус 1.
3) Соседи сверху (кроме первой строки 0) есть:
- у узлов с нечетными номерами в верхней половине – номер строки минус 1 и номер столбца минус 1;
- у узлов с четными номерами в нижней половине – номер строки минус 1 и номер столбца минус 1 (или номер столбца такой же, если длина верхней строки такая же).
4) Соседи снизу (кроме последней строки 5) есть:
- у узлов с четными номерами в верхней половине – номер строки плюс 1 и номер столбца плюс 1 (или номер столбца такой же, если длина нижней строки такая же);
- у узлов с нечетными номерами в нижней половине – номер строки плюс 1 и номер столбца минус 1.
Вместо того, чтобы вручную задавать матрицу переходов или матрицу смежности (где число строк и число столбцов равно числу вершин – а это 54), можно написать функцию, которая возвращает массив соседних узлов. Пример такой функции приведен в листинге 4.2-1.
Листинг 4.2-1 – Функция получения массива соседних связанных узлов на языке программирования Python
# Длины строк
StrLen = [7,9,11,11,9,7]
## Функция получения массива соседних связанныъх узлов
# PARAMS
# nStr - номер строки искомого узла (нумерация с 0)
# nStb - номер столбца искомого узла (нумерация с 0)
# RETURN
# массив соседей в формате [ [nStr1, nStb1], [nStr2, nStb2],...]
##
def neighbors(nStr ,nStb):
res = []
# если не первый узел в строке - сосед слева есть
if nStb != 0:
res.append([nStr, nStb - 1])
# если не последний узел в строке - сосед справа есть
if nStb != StrLen[nStr] - 1:
res.append([nStr, nStb + 1])
# если строка из верхней половины и не первая и номер узла нечетный,
# ИЛИ
# строка из нижней половины и номер узла четный,
# то сосед сверху есть
if ( (nStr != 0 and nStr < len(StrLen)//2 and nStb % 2 == 1)
or (nStr >= len(StrLen)//2 and nStb % 2 == 0) ):
# если верхняя строка больше, то столбец + 1
if StrLen[nStr - 1] > StrLen[nStr]:
res.append([nStr - 1, nStb + 1])
# если верхняя строка меньше, то столбец - 1
elif StrLen[nStr - 1] < StrLen[nStr]:
res.append([nStr - 1, nStb - 1])
# если верхняя строка такой же длины, то номер столбца такой же
else:
res.append([nStr - 1, nStb])
# если строка из верхней половины и номер узла четный,
# ИЛИ
# строка из нижней половины и не последняя и номер узла нечетный,
# то сосед сверху есть
if ( (nStr < len(StrLen)//2 and nStb % 2 == 0)
or (nStr >= len(StrLen)//2 and nStr != len(StrLen)-1 and nStb%2==1)
):
# если нижняя строка больше, то столбец + 1
if StrLen[nStr + 1] > StrLen[nStr]:
res.append([nStr + 1, nStb + 1])
# если нижняя строка меньше, то столбец - 1
elif StrLen[nStr + 1] < StrLen[nStr]:
res.append([nStr + 1, nStb - 1])
# если нижняя строка такой же длины, то номер столбца такой же
else:
res.append([nStr + 1, nStb])
# возвращаем массив соседей
return res
Алгоритм работы самой программы следующий:
1) В цикле перебираем все строки от 0 до 5 включительно.
2) Для каждой строки в цикле перебираем узлы.
3) Обнуляем массив инфицированных узлов и добавляем очередную вершину (шаг 1 заражения).
4) В цикле 4 раз (шаги 2-5 заражения) просматриваем массив инфицированных узлов, и для каждого инфицированного узла добавляем туда всех его соседей, получаемых с помощью функции neighbors().
5) После завершения цикла по шагам заражения подсчитываем количество зараженных узлов в массиве инфицированных, выводим на экран информацию и переходим к следующему узлу (п.3).
Пример реализации такого алгоритма приведен в листинге 4.2-2.
Листинг 4.2-2 – Реализация алгоритма перебора всех узлов и поиска числа зараженных компьютеров на языке программирования Python
## Функция инфицирования узлов
# PARAMS
# массив уже инфицированных узлов
# RETURN
# массив инфицированных + новых зараженных узлов
# (всех соседей из массива инфицированных + сами инфицированные узлы)
def infect(infected):
# создаем копию массива, чтобы не испортить оригинал
res = copy.copy(infected)
# цикл по всем узлам из массива инфицированных
for node in infected:
# цикл по всем соседям очередного узла node
for infNode in neighbors(node[0],node[1]):
# если такого узла еще нет в списке инфицированных -
# добавляем его
if infNode not in res:
res.append(infNode)
# возвращаем результат
return res
output=[]
# цикл по строкам
for i in range(0,len(StrLen)):
# цикл по узлам в строке
for j in range(0,StrLen[i]):
# обнудение массива инфицированных
infected = []
# добавление первого зараженного узла (очередной)
infected.append([i,j])
# шаги заражения
for step in range(1,5):
# добавляем всех соседей в массив инфицированных
infected = infect(infected)
# вывод на экран информации и статистики
print(f"[{i},{j}] - total: {len(infected)}")
output.append({'start':[i,j],'count':len(infected)})
# сортировка итоговой информации
output.sort(key=lambda x: x['count'])
# вывод на экран в отсортированном виде
for i in output:
print(i)
Результат работы программы:
{'start': [0, 0], 'count': 15}
{'start': [0, 1], 'count': 15}
{'start': [0, 5], 'count': 15}
{'start': [0, 6], 'count': 15}
{'start': [2, 0], 'count': 15}
{'start': [2, 10], 'count': 15}
{'start': [3, 0], 'count': 15}
{'start': [3, 10], 'count': 15}
{'start': [5, 0], 'count': 15}
{'start': [5, 1], 'count': 15}
{'start': [5, 5], 'count': 15}
{'start': [5, 6], 'count': 15}
{'start': [0, 3], 'count': 17}
{'start': [1, 0], 'count': 17}
{'start': [1, 8], 'count': 17}
{'start': [4, 0], 'count': 17}
{'start': [4, 8], 'count': 17}
{'start': [5, 3], 'count': 17}
{'start': [0, 2], 'count': 19}
{'start': [0, 4], 'count': 19}
{'start': [1, 1], 'count': 19}
{'start': [1, 7], 'count': 19}
{'start': [2, 1], 'count': 19}
{'start': [2, 9], 'count': 19}
{'start': [3, 1], 'count': 19}
{'start': [3, 9], 'count': 19}
{'start': [4, 1], 'count': 19}
{'start': [4, 7], 'count': 19}
{'start': [5, 2], 'count': 19}
{'start': [5, 4], 'count': 19}
{'start': [1, 2], 'count': 24}
{'start': [1, 3], 'count': 24}
{'start': [1, 5], 'count': 24}
{'start': [1, 6], 'count': 24}
{'start': [2, 2], 'count': 24}
{'start': [2, 8], 'count': 24}
{'start': [3, 2], 'count': 24}
{'start': [3, 8], 'count': 24}
{'start': [4, 2], 'count': 24}
{'start': [4, 3], 'count': 24}
{'start': [4, 5], 'count': 24}
{'start': [4, 6], 'count': 24}
{'start': [1, 4], 'count': 28}
{'start': [2, 3], 'count': 28}
{'start': [2, 7], 'count': 28}
{'start': [3, 3], 'count': 28}
{'start': [3, 7], 'count': 28}
{'start': [4, 4], 'count': 28}
{'start': [2, 4], 'count': 31}
{'start': [2, 5], 'count': 31}
{'start': [2, 6], 'count': 31}
{'start': [3, 4], 'count': 31}
{'start': [3, 5], 'count': 31}
{'start': [3, 6], 'count': 31}
Проанализировав информацию, можно сделать вывод, что наилучшие условия для заражения узлов без обнаружения антивирусом – это 24 узла, при этом разместить вирус необходимо в одном из узлов с координатами [1,2], [1,3], [1,5], [1,6], [2,2], [2,8], [3,2], [3,8], [4,2], [4,3], [4,5], [4,6] (всего 12 вариантов). Подробнее см. рис. 4.2-3 и 4.2-4.