Репетитор ОГЭ и ЕГЭ по информатике
обучение программированию на Python

Задание 1 ЕГЭ по информатике

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАДАНИЕ 1 - 1

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).


Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта А в пункт Г.

В ответе запишите целое число – так, как оно указано в таблице.

ЗАДАНИЕ 1 - 10

На рисунке изображена схема дорог N-ского района. В таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

Каждому населённому пункту на схеме соответствует номер в таблице, но неизвестно, какой именно номер. Определите, какие номера в таблице могут соответствовать населённым пунктам E и F на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

ЗАДАНИЕ 1 - 100

Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).

ЗАДАНИЕ 1 - 101

Ha рисунке схема дорог Н-ского района изображена в виде графа, в таблице звездочкой отмечено наличие дороги между пунктами.

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Установите соответствие между номерами пунктов в таблице и буквенными обозначениями на графе. В ответе запишите последовательность номеров пунктов, соответствующую последовательности пунктов АБВГДИК, без пробелов и дополнительных символов.

ЗАДАНИЕ 1 - 102
А. Богданов

На рисунке схема коммуникаций Н-ского астероида изображена в виде графа, в таблице содержатся сведения о протяжённости некоторых «дорог» между восьми порталов. Для остальных «дорог» длина неизвестна и обозначена «звездочкой».

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

ЗАДАНИЕ 1 - 103

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах)

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта Б в пункт В и из пункта Г в пункт Д.

В ответе запишите целое число.

ЗАДАНИЕ 1 - 104

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Д в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.

ЗАДАНИЕ 1 - 105
Крамник Илья

На рисунке схема долгов между шестью господами изображена в виде ориентированного графа, в таблице содержатся сведения о величинах долга каждого из господ. Так как таблицу и схему рисовали независимо друг от друга, то нумерация господ в таблице никак не связана с буквенными обозначениями на графе. Стрелка показывает кому господин должен. Столбцы таблицы обозначают исходящие стрелки, а строки входящие.

Определите, сколько долларов господин В должен господину И.

ЗАДАНИЕ 1 - 106
Крамник Илья

На рисунке схема дорог Н-ского района изображена в виде ориентированного графа, в таблице звёздочками обозначено наличие дорог. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Стрелка показывает единственное возможное направление движения. Столбцы таблицы обозначают исходящие стрелки, а строки входящие.

Выпишите последовательно, без пробелов и знаков препинания, указанные на графе буквенные обозначения пунктов от П1 до П5: сначала букву, соответствующую П1, затем букву, соответствующую П2 и т. д.

ЗАДАНИЕ 1 - 107
Крамник Илья

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице числами обозначены длины дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.

Выпишите последовательно, без пробелов и знаков препинания, указанные на графе буквенные обозначения пунктов от П1 до П8: сначала букву, соответствующую П1, затем букву, соответствующую П2 и т. д.

ЗАДАНИЕ 1 - 108
Крамник Илья

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице числами обозначены длины дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.

Определите, какова длина дороги из A в С, если известно, что сумма длин дорог между E и G и G и H меньше 25.

ЗАДАНИЕ 1 - 109

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите сумму длин дорог из пункта Г в пункт Е и из пункта Д в З.

ЗАДАНИЕ 1 - 11
Л. Шастин

На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости
каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта В в пункт E и из пункта C в пункт F.
В ответе запишите целое число.

ЗАДАНИЕ 1 - 110
А. Богданов

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите протяжённость дороги из пункта Б в пункт Д. В ответе запишите целое.

ЗАДАНИЕ 1 - 111

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице звёздочками обозначено наличие дорог. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Выпишите последовательно, без пробелов и знаков препинания, указанные на графе буквенные обозначения пунктов от П1 до П7: сначала букву, соответствующую П1, затем букву, соответствующую П2, и т. д.

ЗАДАНИЕ 1 - 112

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, в какой пункт ведёт самая короткая дорога из пункта А. В ответе укажите букву, обозначающую населённый пункт.

ЗАДАНИЕ 1 - 113

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что длина кратчайшего пути из пункта A в пункт Д не превышает 30 километров. Определите длину кратчайшего пути между пунктами Ж и Г. Передвигаться можно только по указанным дорогам.

ЗАДАНИЕ 1 - 114

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Г в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.

ЗАДАНИЕ 1 - 115

На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам Б и В на схеме. В ответ запишите без разделителей сначала номер пункта Б , потом номер пункта В .

ЗАДАНИЕ 1 - 116

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой.

Так как таблицу и схему рисовали отдельно друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам А и Д на схеме.

В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

ЗАДАНИЕ 1 - 117

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите длину дороги между пунктами А и Б, если известно, что длина дороги между Г и Д меньше длины дороги между Г и Е. Передвигаться можно только по указанным дорогам.

ЗАДАНИЕ 1 - 118
А. Богданов

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите минимально возможную протяжённость пути из пункта В в пункт Д. В ответе запишите целое.

ЗАДАНИЕ 1 - 119

На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта Б в пункт Д и из пункта В в пункт Е. В ответе запишите целое число.

ЗАДАНИЕ 1 - 12

На рисунке изображена схема дорог N-ского района. В таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера в таблице могут соответствовать населённым пунктам С и Е на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

ЗАДАНИЕ 1 - 120

На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Г в пункт Д. В ответе запишите целое число.

ЗАДАНИЕ 1 - 121

На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, нумерация населенных пунктов в таблице никак не связана с буквенными обозначениями на графе.

Известно, что длина дороги ГЕ больше, чем длина дороги ГЖ. Определите длину дороги БВ. В ответе запишите целое число - длину дороги в километрах.

ЗАДАНИЕ 1 - 122

На рисунке справа изображена схема дорог N-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам Е и В на схеме.

В ответ запишите эти два номера в возрастающем порядке без пробелов и знаков препинания

ЗАДАНИЕ 1 - 123

На рисунке справа изображена схема дорог N-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам А и Б на схеме.

В ответ запишите эти два номера в возрастающем порядке без пробелов и знаков препинания

ЗАДАНИЕ 1 - 124

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице слева содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Б в пункт В. В ответе запишите целое число — так, как оно указано в таблице.

ЗАДАНИЕ 1 - 125

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите длину дороги между пунктами Г и Е. Передвигаться можно только по указанным дорогам.