ЗАДАНИЕ 1 - 146

На рисунке слева изображена схема дорог N-ского района. Приведены длины дорог между пунктами. Так как таблицу и граф заполняли независимо, наименование вершин графа никак не зависят от номеров пунктов в таблице. Найдите кратчайший маршрут из А в Н. В качестве ответа укажите найденный маршрут как последовательность названий пунктов на графе. Например, ABCDEFGH.

Посмотреть ответ

Ответ: ABCDGH

Подсказки

Шаг 1. Внимательное прочтение задачи

Внимательно ознакомьтесь с условием задачи.
Выпишите все кодовые слова (последовательности нулей и единиц) и их соответствующие значения (например, символы, буквы или данные, которые нужно кодировать).

Шаг 2. Построение бинарного дерева

Начинайте строить дерево с двух веток: 0 и 1.
Эти ветки — корень вашего дерева.
От каждой ветки можно добавить ещё две: для ветки с 0 — добавляйте ветки с 0 и 1; для ветки с 1 — аналогично.
Продолжайте расширять дерево, создавая новые уровни.
Ветки, направленные вправо — с 1, влево — с 0.
Отметьте на дереве все известные кодовые слова, то есть те пути, которые уже соответствуют кодам из условия.

Шаг 3. Удаление лишних веток (принцип Фано)

Если в конце ветки находится уже буква или символ, значит эта ветка завершена и блокируется.
От таких веток нельзя делать новые ответвления — они «завершённые».
Вычеркните все ветки, которые продолжают расширяться после достижения конечного символа, чтобы не нарушить правила кода Фано (коды не должны быть префиксными друг для друга).

Шаг 4. Назначение кодов символам

Посмотрите, какие ветки ещё свободны для размещения новых кодов.
На ветке с наименьшей длиной текущего кодового слова (то есть короткой ветке) добавьте нужную букву или символ.
Если нужно разместить несколько символов, следите за тем, чтобы длина веток оставалась минимальной — это обеспечивает оптимальность кода (минимальную среднюю длину).

Шаг 5. Решение задачи

После построения дерева и назначения кодов, внимательно прочтите формулировку вопроса.
Выполните необходимые вычисления: например, найдите среднюю длину кода, подсчитайте его эффективность и т.п.
Введите полученный ответ в поле для результатов.

Важное замечание

Длина кодового слова — это количество символов в нём.
- Например, длина кода 1011 равна 4.
- А длина 100 равна 3.

Если потребуется помощь с конкретной задачей или примером, присылайте условие — помогу разобрать подробнее!

Нужна помощь в решении?

89085585294

Меня зовут Евгений Владимирович. Проводу подготовку учеников по ОГЭ, ЕГЭ по информатике. Обучаю программировать на Python с нуля.

Что я предлагаю:

Видеозапись каждого занятия - отправка ученику для повторения
Индивидуальный подход к каждому ученику, с учетом его текущего уровня знаний и целей.
Подготовку по всем разделам ЕГЭ: теория, практика, решение типовых заданий и тренировочных вариантов.
Домашние задания и их разбор
Помощь с задачами и проектами Яндекс Лицея
Разбор подводных камней в задачах экзаменов
Подготовка по программированию для ЕГЭ на языке Python
Решение задач разного уровня сложности
Решение задач, максимально приближенных к реальному ЕГЭ
Обучение эффективным стратегиям выполнения заданий, управлению временем на экзамене.
Регулярные тестирования для оценки прогресса.
Использование современных методик и материалов, адаптированных к формату экзамена.

Мои преимущества:

Глубокое знание программы ЕГЭ по информатике.
Индивидуальный план занятий, гибкий график.
Поддержка и мотивация на пути к успеху.
Помощь в подготовке как к базовой, так и к профильной части экзамена.

Для кого подойдут мои занятия:

Студенты и школьники, готовящиеся к ЕГЭ по информатике.
Те, кто хочет повысить свой уровень знаний и уверенность в своих силах.
Ученики, испытывающие сложности с определенными темами или задачами.

К каким результатам могу привести

По ОГЭ есть опыт подготовки на 100 баллов
по ЕГЭ на 90+ баллов

Возраст ученика не важен, опыт в программировании не важен.

Как проводятся занятия

Занятия онлайн.