Решение задачи: Кратчайший путь между А и Е

Хорошо, давайте разберем задачи по порядку. Часть 2 11. Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего пути между пунктами А и Е. Перепишем таблицу для удобства: | | A | B | C | D | E | |---|---|---|---|---|---| | A | | 2 | 5 | | | | B | 2 | | 1 | | | | C | 5 | 1 | | 3 | 2 | | D | | | 3 | | 1 | | E | | | 2 | 1 | | Найдём кратчайший путь от А до Е, используя метод Дейкстры или просто перебирая пути: * **Путь из А в А:** 0 * **Путь из А в В:** 2 (А-В) * **Путь из А в С:** * А-С: 5 * А-В-С: 2 + 1 = 3 (этот путь короче) * **Путь из А в D:** * А-С-D: 3 + 3 = 6 * А-В-С-D: 2 + 1 + 3 = 6 * **Путь из А в Е:** * А-С-Е: 3 + 2 = 5 * А-С-D-Е: 3 + 3 + 1 = 7 * А-В-С-Е: 2 + 1 + 2 = 5 * А-В-С-D-Е: 2 + 1 + 3 + 1 = 7 Сравнивая все найденные пути до Е, видим, что кратчайший путь равен 5. **Ответ:** 5 12. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город В? Давайте посчитаем количество путей из А в Л, проходящих через В. Сначала найдём все пути из А в В: * А-Б-В (1 путь) * А-Г-В (1 путь) * А-Д-В (1 путь) Итого 3 пути из А в В. Теперь найдём все пути из В в Л: * В-Е-Л (1 путь) * В-Ж-Л (1 путь) * В-И-Л (1 путь) * В-К-Л (1 путь) Итого 4 пути из В в Л. Чтобы найти общее количество путей из А в Л, проходящих через В, нужно перемножить количество путей из А в В на количество путей из В в Л. Количество путей = (Пути из А в В) * (Пути из В в Л) = 3 * 4 = 12. **Ответ:** 12 13. У исполнителя Вычислитель две команды, которым присвоены номера: 1. умножь на 4 2. вычти 2 Первая из них увеличивает число на экране в 4 раза, вторая уменьшает его на 2. Составьте алгоритм получения из числа 3 числа 30, содержащий не более 5 команд. В ответе запишите только номера команд. Нарисуем дерево возможных операций: Начальное число: 3 Целевое число: 30 Максимум 5 команд. Попробуем идти от конца к началу или перебирать варианты: * **Вариант 1:** * 3 * 4 = 12 (1 команда) * 12 * 4 = 48 (2 команды) - слишком много * 12 - 2 = 10 (2 команды) * 10 * 4 = 40 (3 команды) * 40 - 2 = 38 (4 команды) * 38 - 2 = 36 (5 команд) - не 30 * **Вариант 2:** * 3 - 2 = 1 (1 команда) * 1 * 4 = 4 (2 команды) * 4 * 4 = 16 (3 команды) * 16 * 4 = 64 (4 команды) - слишком много * 16 - 2 = 14 (4 команды) * 14 * 4 = 56 (5 команд) - слишком много * 14 - 2 = 12 (5 команд) - не 30 * **Вариант 3 (попробуем больше вычитаний в начале):** * 3 * 4 = 12 (1 команда) * 12 - 2 = 10 (2 команды) * 10 - 2 = 8 (3 команды) * 8 * 4 = 32 (4 команды) * 32 - 2 = 30 (5 команд) - **Найдено!** Последовательность команд: 1. 3 * 4 = 12 (команда 1) 2. 12 - 2 = 10 (команда 2) 3. 10 - 2 = 8 (команда 2) 4. 8 * 4 = 32 (команда 1) 5. 32 - 2 = 30 (команда 2) Номера команд: 12212 **Ответ:** 12212 14. В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. | Запрос | Найдено страниц (в тысячах) | |---|---| | Москва & Самара | 1260 | | Самара & (Москва | Уфа) | 1467 | | Москва & Самара & Уфа | 1190 | Какое количество страниц (в тысячах) будет найдено по запросу Самара & Уфа? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов. Обозначим количество страниц: * М = Москва * С = Самара * У = Уфа Известные данные: 1. \(N(М \text{ & } С) = 1260\) 2. \(N(С \text{ & } (М \text{ | } У)) = 1467\) 3. \(N(М \text{ & } С \text{ & } У) = 1190\) Нужно найти \(N(С \text{ & } У)\). Раскроем второе выражение, используя дистрибутивность логических операций: \(N(С \text{ & } (М \text{ | } У)) = N((С \text{ & } М) \text{ | } (С \text{ & } У))\) По формуле включений-исключений для двух множеств: \(N(А \text{ | } В) = N(А) + N(В) - N(А \text{ & } В)\) Применим эту формулу к \(N((С \text{ & } М) \text{ | } (С \text{ & } У))\): \(N((С \text{ & } М) \text{ | } (С \text{ & } У)) = N(С \text{ & } М) + N(С \text{ & } У) - N((С \text{ & } М) \text{ & } (С \text{ & } У))\) Заметим, что \((С \text{ & } М) \text{ & } (С \text{ & } У)\) эквивалентно \((С \text{ & } М \text{ & } У)\). Тогда: \(N(С \text{ & } (М \text{ | } У)) = N(С \text{ & } М) + N(С \text{ & } У) - N(С \text{ & } М \text{ & } У)\) Подставим известные значения: \(1467 = 1260 + N(С \text{ & } У) - 1190\) Теперь решим уравнение относительно \(N(С \text{ & } У)\): \(1467 = 1260 - 1190 + N(С \text{ & } У)\) \(1467 = 70 + N(С \text{ & } У)\) \(N(С \text{ & } У) = 1467 - 70\) \(N(С \text{ & } У) = 1397\) **Ответ:** 1397