№1 · Алгоритм дейкстры
1. Допустимые веса рёбер
Выбери условие, при котором можно применять алгоритм Дейкстры для поиска кратчайших путей.
Ф.И.
Класс
Потренируйся находить кратчайшие маршруты, сохранять предков и распознавать выигрышные позиции в игре. Внимательно следи за каждым шагом алгоритма.
№1 · Алгоритм дейкстры
Выбери условие, при котором можно применять алгоритм Дейкстры для поиска кратчайших путей.
№2 · Проверка понятий
Определи истинность каждого утверждения только с точки зрения работы алгоритма Дейкстры и восстановления кратчайшего пути.
№3 · Динамическое программирование
Заполни пропуски в записи перехода динамического программирования для слоистого графа.
Минимальная стоимость попадания в вершину v равна по всем предшественникам u: d(v) = . Для восстановления пути сохраняют вершины.
№4 · Таблица меток
Для ориентированного графа с рёбрами A→B (4), A→C (2), C→B (1), B→D (3), C→D (5), D→E (2) заполни скрытые ячейки таблицы после работы алгоритма Дейкстры из вершины A.
| Вершина | Кратчайшее расстояние от A | Предок |
|---|---|---|
| A | 0 | — |
| B | ||
| C | ||
| D | ||
| E |
№5 · Сравнение маршрутов
Сравни стоимость маршрутов. В каждой строке поставь знак между левым и правым выражением.
№6 · Термины алгоритма
Соедини каждый термин с его точным описанием.
+5 заданий в этом листе
Зарегистрируйтесь — и соберите свой рабочий лист по этой теме за минуту: заданий столько, сколько нужно.
№7 · Порядок шагов
Расставь действия алгоритма Дейкстры в правильном порядке: от инициализации до получения окончательных меток.
№8 · Слоистый граф
В слоистом графе есть рёбра: A→B со стоимостью 2, A→C со стоимостью 5, B→D со стоимостью 4, B→E со стоимостью 7, C→D со стоимостью 1, C→E со стоимостью 3, D→F со стоимостью 2, E→F со стоимостью 1. Найди минимальную стоимость пути из A в F и восстанови сам путь.
№9 · Теория игр
В игре за ход можно прибавить к текущему числу 1, 2 или 3. Побеждает тот, кто получает 15. Найди лишнюю позицию среди четырёх проигрышных и одной выигрышной. Для каждой позиции проверь, можно ли одним ходом попасть в проигрышную позицию соперника.
№10 · Анализ ограничений
Рассмотри граф с рёбрами A→B (2), A→C (5), B→C (-4), C→D (1), B→D (7). Определи, можно ли корректно применить алгоритм Дейкстры из A. Если нельзя, объясни причину и найди кратчайший путь из A в D перебором допустимых маршрутов.
Создайте уникальный лист по своей теме
Зарегистрируйтесь бесплатно — лист сохранится в личном кабинете, откуда его можно скачать в PDF и распечатать.
В листе 10 заданий: множественный выбор, истина / Ложь, заполни пропуски, таблица, сравни числа, соединение, последовательность, реши задачу, найти лишнее.
Да, задания ориентированы на школьную программу по информатике для 10 класса по ФГОС.
Да. После регистрации лист открывается в конструкторе: задания можно заменить, перегенерировать или добавить новые.