Задание 4 ОГЭ по информатике · 1FEEAD
ПовышеннаяКЭС 2.11
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами A и D при условии, что передвигаться можно только по указанным в таблице дорогам. Каждый пункт можно посетить только один раз.
Таблица 1 · протяжённость дорог
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | — | 5 | — | — | 3 |
| B | 5 | — | 1 | 5 | — |
| C | — | 1 | — | 1 | 5 |
| D | — | 5 | 1 | — | 6 |
| E | 3 | — | 5 | 6 | — |
Таблица 1 · протяжённость дорог
Показать ответ
7
Подсказки (3)
- Перечислите возможные пути из A в D и сложите длины входящих в них дорог.
- Сравните, например, пути A–B–D, A–B–C–D, A–E–D и A–E–C–D.
- Для пути A–B–C–D длина равна 5+1+1=7.
Решение
1. Рассмотрим пути из A в D, не посещая один и тот же пункт дважды. 2. Путь A–B–C–D имеет длину: 5+1+1=7 3. Другие основные варианты длиннее: A–B–D — 10, A–E–D — 9, A–E–C–D — 9. Следовательно, кратчайшим является путь A–B–C–D.
Частые ошибки
- Не учитывают промежуточный пункт C и выбирают путь A–B–D длиной 10.
- Складывают длины дорог, не проверяя, какой путь является кратчайшим.
- Повторно посещают один и тот же пункт.
Источник: Открытый банк ФИПИ
Похожие задания
4Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость…Задания открытого банка ФИПИ · 1BD7B74Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.…Задания открытого банка ФИПИ · 1C05C94Определите длину кратчайшего пути между пунктами B и D. Передвигаться можно только по дорогам, протяжённость…Задания открытого банка ФИПИ · 1CD9994Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость…Задания открытого банка ФИПИ · 1FE6D04Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена…Задания открытого банка ФИПИ · 21C1144Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена…Задания открытого банка ФИПИ · 2442E14Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость…Задания открытого банка ФИПИ · 26B4134Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость…Задания открытого банка ФИПИ · 274256
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ОГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.