с алгеброй
1. Изобразить граф, соответствующий матрице:
A B C D E
A X 4 X X 5
B 4 X 8 11 9
C X 8 X 7 2
D X 4 7 X 6
E 5 9 2 6 X
2.Между населенными пунктами A,B,C,D,E,F построены дороги протяженность которых (в километрах) приведена в матрице. Определите длину кратчайшего пути между пунктами A и F.
A B C D E F
A X 9 1 7 4 14
B 9 X 8 2 X 5
C 1 8 X X 2 X
D 7 2 X X 3 8
E 4 X 2 3 X 12
F 14 X X 8 12 X
Задание №3. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Задание №4. У исполнителя Преобразователь две команды, которым присвоены номера:
1. обнули справа
2. увеличь на 12
Первая из них заменяет цифру младшего разряда числа на 0, вторая увеличивает число на 12. Составьте алгоритм получения из числа 15 числа 58, содержащий не более 5 команд. В ответе запишите только номера команд.
Например, 121—это алгоритм: «обнули справа, увеличь на 12, обнули справа» Если таких алгоритмов более одного, то запишите любой из них.
1. Для начала рассмотрим данную матрицу:
```
A B C D E
A X 4 X X 5
B 4 X 8 11 9
C X 8 X 7 2
D X 4 7 X 6
E 5 9 2 6 X
```
Данная матрица представляет собой граф, в котором вершины - это населенные пункты A, B, C, D, E, а ребра - дороги между этими населенными пунктами. Значение в ячейке матрицы представляет собой длину дороги между соответствующими населенными пунктами. Если между двумя населенными пунктами нет дороги, то значение в матрице будет обозначено символом "X".
Изобразим граф по данной матрице:
```
4 5
A -----> E
^ ^ ^
| / \
| 5 9
| / \
| / \
v v v
B ------> D ---> C
^ 4 | ^
|________| |
7
```
2. Для нахождения кратчайшего пути между пунктами A и F в данной матрице, мы можем использовать алгоритм Дейкстры. Начинаем с вершины A и рассчитываем длину пути до всех остальных вершин.
```
A B C D E F
0 X 1 7 4 14
```
Затем выбираем вершину с наименьшей длиной пути из A (в данном случае это C) и обновляем расстояние до всех соседних вершин C:
```
A B C D E F
0 X 1 7 4 3
```
Затем выбираем следующую вершину с наименьшей длиной пути (в данном случае это E) и обновляем расстояние до соседних вершин E:
```
A B C D E F
0 X 1 7 4 10
```
Далее, выбираем вершину D и обновляем расстояние до соседних вершин D:
```
A B C D E F
0 X 1 6 4 10
```
Наконец, выбираем вершину B и обновляем расстояние до соседних вершин B:
```
A B C D E F
0 9 1 6 4 10
```
Теперь мы можем видеть, что кратчайший путь между A и F составляет 10 километров.
3. Задание №3 требует посчитать количество различных путей из города А в город К, используя только указанные направления. Для этого нужно проследовать по стрелкам от города А к К, считая каждый новый путь. Запишем все различные пути:
```
A -> Б -> В -> Д -> К
A -> Б -> В -> И -> К
A -> Б -> Б -> В -> Д -> К
A -> Б -> Б -> В -> И -> К
A -> В -> Д -> К
A -> В -> И -> К
```
Всего существует 6 различных путей из города А в город К.
4. В задании №4 требуется составить алгоритм получения из числа 15 числа 58, используя команды "обнули справа" и "увеличь на 12". Мы должны составить алгоритм, содержащий не более 5 команд.
```
Алгоритм: "обнули справа, увеличь на 12, обнули справа, обнули справа, увеличь на 12"
Номера команд: 12110
```
Применяя данный алгоритм к числу 15, мы получим число 58.