Решение
Так как в ответе на задачу необходимо указать через какой маршрутизатор и для какой сети надо отправить пакет, а также указать наибольшее число пересылок пакета, то решить задачу теоретически, получив точный ответ, не представляется возможным. Возможно два варианта поиска ответа: ручной и программный.
Решение задачи вручную и получение полного обоснованного ответа, охватывающего все возможные случаи, когда для каждого из трех вариантов входа может быть одиннадцать вариантов выхода, слишком трудозатратно, так как необходимо проследить пути пакета до всех целевых маршрутизаторов (11 случаев) для всех возможных входов в маршрутизаторы, подключенные к сети Интернет. Но если доказать, что существует путь, для которого пакет «зациклится» и значение счётчика S достигнет 100, то можно будет вручную найти один или более вариант правильного ответа. Зацикливание пакета может произойти в случае, если значение счетчика S станет достаточно большим, чтобы для некоторых двух соседних маршрутизаторов в качестве следующего маршрутизатора для перехода был выбран маршрутизатор с максимальным номером, то есть значение выражения S / R > 2, при этом они являются «соседями» с наибольшим номером друг для друга и, очевидно, что они не должны быть целевыми маршрутизаторами. Такое место в сети есть – это маршрутизаторы с номерами 11 и 12. Далее надо найти такой путь (начальный и конечный маршрутизаторы), для которого пакет на некотором шаге попадёт в маршрутизатор №12 и, в итоге с ростом счётчика S, зациклится.
В качестве сети назначения подойдут сети с номерами 3, 7 и 8, так как можно заметить, что они не достижимы при отправке пакета через заданные условием задачи маршрутизаторы. В сеть 3 можно попасть из сети 1 при условии, что S < 2, но это не возможно потому, что сеть 1 не является входной. А в сети 7 и 8 можно попасть только после того, как пакет пройдёт из сети 9 в сеть 12 со значением счетчика S ≥ 27. При таком значении счетчика из сетей 10 и 11 не перейти в сети 8 и 7 соответственно, так как значение выражения S / R должно быть меньше 2, а оно будет заведомо больше или равно двум.
Рассмотрим пример, когда пакет, переданный через маршрутизатор №2 для сети №3 на шаге №39 зациклится между маршрутизаторами с номерами 11 и 12.
|
S
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
21
|
22
|
23
|
24
|
25
|
26
|
|
R
|
2
|
4
|
2
|
4
|
2
|
5
|
1
|
6
|
1
|
6
|
1
|
6
|
2
|
6
|
2
|
6
|
2
|
6
|
4
|
9
|
5
|
9
|
5
|
9
|
5
|
9
|
|
S
|
27
|
28
|
29
|
30
|
31
|
32
|
33
|
34
|
35
|
36
|
37
|
38
|
39
|
40
|
…
|
100
|
|
R
|
5
|
9
|
12
|
10
|
12
|
10
|
12
|
10
|
12
|
10
|
12
|
11
|
12
|
11
|
…
|
11
|
Таким образом, получаем, что пакет надо отправить через маршрутизаторы №2 или №4 для сети №3, или через любой из входных маршрутизаторов для сетей №7 или №8. При этом значение счетчика S достигнет 100, то есть между маршрутизаторами будет сделано 99 шагов.
Таким будет ответ, если результат операции деления S на R будем считать целочисленным.
Если решать задачу, считая, что результат операции деления вещественный, то ответ будет следующим: пакет надо отправить через маршрутизатор №3 для сети №2, через маршрутизаторы №2 и №4 для сети №3, через маршрутизатор №2 для сети №10 или через любой из входных маршрутизаторов для сетей №7 или №8. Между маршрутизаторами будет сделано 99 пересылок.
Эту задачу удобно решать программным способом, так как ее условие можно формализовать и разработать алгоритм решения. Маршрутизаторы и связи между ними можно программно представить либо в виде матрицы смежности, либо в виде массива «соседей». В матрице смежности размером 12 на 12 ноль в i-ой строке и j-ом столбце будет означать отсутствие связи между маршрутизатором № i и маршрутизатором № j, а единица – наличие связи. В каждой строке будет по три единицы, означающих наличие переходов в маршрутизаторы с наименьшим, средним и наибольшим номерами, как представлено на рисунке. Вместо матрицы смежности можно создать двумерный массив размером 12 на 3, в каждой строке которого будут последовательно указаны номера маршрутизаторов с наименьшим, средним и наибольшим номерами, соединенных с маршрутизатором соответствующим номеру этой строки. Далее необходимо реализовать алгоритм обхода графа, представленного одним из описанных выше способов, начиная с каждой из входных вершин и заканчивая в любой вершине. Получается 36 возможных вариантов с учетом того, что входная и выходная вершины могут совпадать.
