- •Задание 1. Системы счисления
- •Задание 2. Логические функции и таблицы истинности
- •Задание 3. Графы, поиск пути.
- •Тема 4. Запросы в реляционных бд. Файловая система.
- •Тема 5. Неравномерные коды.
- •Тема 6. Алгоритм для исполнителя
- •Тема 7. Электронные таблицы Excel
- •Тема 8. Простейшие алгоритмы
- •Тема 9. Обработка, хранение, передача информации.
- •Тема 10. Комбинаторика.
- •Тема 11. Рекурсия.
- •Тема 12. Адресация в сети Интернет
- •Тема 13. Информационный объем, формула Шенона.
- •Тема 14. Алгоритмы для исполнителей
- •Тема 15. Поиск путей.
- •Тема 16. Системы счисления
- •Тема 17. Теория множества
- •Корвет & бриг & фрегат Тема 18. Математическая логика
- •Тема 19. Массивы и циклы
- •Тема 20. Циклы и условные операторы
- •Тема 21. Циклы и подпрограммы
- •Тема 22. Динамическое программирование
- •1. Прибавь 1
- •2. Умножь на 2
- •Тема 23. Системы логических уравнений
- •Алгоритмический минимум
Задание 3. Графы, поиск пути.
Тип 1. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути между пунктами Б и Д. Передвигаться можно только по указанным дорогам.
Тип 2. Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из A в B есть дорога длиной 4 км, а из B в A дороги нет.
|
A |
B |
C |
D |
E |
F |
Z |
A |
|
4 |
6 |
|
|
|
30 |
B |
|
|
3 |
8 |
|
|
|
C |
|
|
|
11 |
10 |
|
27 |
D |
|
|
|
|
4 |
3 |
10 |
E |
|
|
|
|
|
4 |
1 |
F |
|
|
|
|
|
|
2 |
Z |
29 |
|
|
|
|
|
|
Курьеру требуется проехать из A в Z, посетив не менее 6 населённых пунктов. Пункты A и Z при подсчёте учитываются, два раза проходить через один пункт нельзя. Какова наименьшая возможная длина маршрута курьера? В ответе запишите натуральное число – длину минимального маршрута.
Тип 3. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
|
A |
B |
C |
D |
E |
F |
A |
|
3 |
4 |
4 |
|
16 |
B |
3 |
|
|
5 |
|
|
C |
4 |
|
|
3 |
|
|
D |
4 |
5 |
3 |
|
6 |
10 |
E |
|
|
|
6 |
|
3 |
F |
16 |
|
|
10 |
3 |
|
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C и не проходящего через пункт B (при условии, что передвигаться можно только по построенным дорогам).
Тип 4. Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из A в B есть дорога длиной 4 км, а из B в A дороги нет.
|
A |
B |
C |
D |
E |
F |
Z |
A |
|
4 |
6 |
|
|
|
30 |
B |
|
|
3 |
4 |
|
|
|
C |
|
3 |
|
11 |
|
|
27 |
D |
|
|
|
|
4 |
7 |
10 |
E |
|
|
|
3 |
|
4 |
8 |
F |
|
|
|
|
5 |
|
2 |
Z |
29 |
|
|
|
|
|
|
Сколько существует таких маршрутов из A в Z, которые проходят через 6 и более населенных пунктов? Пункты A и Z при подсчете учитывать. Два раза проходить через один пункт нельзя.
Тип 5. Между населёнными пунктами A, B, C, D, E, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
|
A |
B |
C |
D |
E |
F |
Z |
A |
|
4 |
6 |
|
|
|
33 |
B |
4 |
|
1 |
|
|
|
|
C |
6 |
1 |
|
2 |
10 |
|
|
D |
|
|
2 |
|
4 |
|
|
E |
|
|
10 |
4 |
|
3 |
8 |
F |
|
|
|
|
3 |
|
2 |
Z |
33 |
|
|
|
8 |
2 |
|
Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).
