Как решать 1 часть егэ по информатике - Помощь в подготовке к экзаменам и поступлению

Урок посвящен тому, как решать 1 задание ЕГЭ по информатике

Содержание:

Объяснение заданий 1 ЕГЭ по информатике
- Структурирование информации и информационные модели
- Поиск кратчайшего пути (перебор)
Решение заданий 1 ЕГЭ по информатике

1-я тема характеризуется, как:
— задания базового уровня сложности,
— требуется использование специализированного программного обеспечения — нет,
— время выполнения – примерно 3 минуты,
— максимальный балл — 1

Проверяемые элементы содержания: Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы)

До ЕГЭ 2021 года — это было задание № 3 и задание № 7 ЕГЭ

Типичные ошибки и рекомендации по их предотвращению:

«Как и в большинстве простых заданий, основные ошибки происходят из-за торопливости и невнимательности»

ФГБНУ «Федеральный институт педагогических измерений»

* Некоторые изображения страницы взяты из материалов презентации К. Полякова

Структурирование информации и информационные модели

Рассмотрим кратко необходимые для решения 1 задания ЕГЭ понятия.

Структурирование информации — это установление главных элементов в информационных сообщениях и установление связей между ними.

Структурирование выполняется с целью облегчения восприятия и поиска информации.

Структурирование возможно при помощи следующих структур (информационных моделей):

множество:

перечисление элементов, собранных по характерному признаку;

Вася, Петя, Коля
1, 17, 22, 55

В множестве упорядочивание элементов не обязательно, т.е. порядок следования не важен.

линейный список

Важна упорядоченность следования элементов.

таблица

В таблицах выделяются объекты (отдельные записи таблиц) и свойства (названия столбцов или названия строк):

дерево или иерархия объектов

Уровни в дереве

Рассмотрим родственные отношения в дереве:

«Сыновья» А: B, C.

«Родитель» B: A.

«Потомки» А: B, C, D, E, F, G.

«Предки» F: A, C.

Корень – узел без предков (A).
Лист – узел без потомков (D, E, F, G).
Высота – наибольшее расстояние от корня до листа (количество уровней).

файловая система (иерархия)

Допустим, на жестком диске компьютера имеются следующие папки (каталоги) с файлами:

Получим дерево:

графы

Иногда очень трудно структурировать информацию описанными структурами из-за сложных «взаимоотношений» между объектами. Тогда можно использовать графы:

Граф – это набор вершин и связей между ними, называющихся рёбрами:

Граф, отображающий дороги между поселками

матрица и список смежности

Связный граф – это граф, между любыми вершинами которого существует путь.

Связный граф

Дерево – это связный граф без циклов (замкнутых участков).

Дерево — связный граф без циклов

взвешенные графы и весовая матрица

У взвешенных графов указан «вес ребра»:

Из взвешенных графов получается весовая матрица, обратное преобразование тоже возможно.

Весовая матрица

Поиск кратчайшего пути (перебор)

Определение кратчайшего пути между пунктами A и D

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

Егифка ©:

Решение заданий 1 ЕГЭ по информатике

Плейлист видеоразборов задания на YouTube:

Задание демонстрационного варианта 2022 года ФИПИ

1_3: Решение 1 задания ЕГЭ по информатике:

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

	A	B	C	D	E	F
A		7	3
B	7		2	4	1
C	3	2		7	5	9
D		4	7		2	3
E		1	5	2		7
F			9	3	7

Определите длину кратчайшего пути между пунктами A и F.

Подобные задания для тренировки

✍ Решение:

Для решения задачи используем построение дерева с подсчетом значений для каждой ветви (протяженности дорог).
При движении от корня дерева (А) вниз будем иметь в виду, что:
рассматривать вершины, которые уже есть в текущей «ветви», — не нужно,
если получаемое число (суммарная протяженность дорог) превышает какое-либо из найденных вариантов от A до F, то дальше эту ветвь можно не рассматривать.
В итоге получим дерево:

Самый короткий путь: A -> C -> B -> E -> D -> F = 11

Результат: 11

Видеоразбор задания:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

1_4: Решение 1 задания ЕГЭ по информатике:

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

	A	B	C	D	E	F
A		3	7		6
B	3			4	4
C	7			5		9
D		4	5			5
E	6	4				8
F			9	5	8

Определите длину кратчайшего пути между пунктами A и F при условии, что передвигаться можно только по указанным в таблице дорогам.

✍ Решение:

Решим задание при помощи построения дерева, вершиной которого является отправной пункт — A. На ребрах дерева будем записывать числа — результат протяженности пути до конкретной вершины.

Кратчайший путь: A -> B -> D -> F = 12

Результат: 12

1_5: Решение 1 задания ЕГЭ по информатике:

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

	A	B	C	D	E	F	Z
A		3		5			14
B			2				8
C		2					7
D					1	4	4
E						1	5
F			12		1		9
Z

Сколько существует таких маршрутов из A в Z, которые проходят через пять и более населенных пунктов? Пункты A и Z при подсчете учитывайте. Два раза проходить через один пункт нельзя.

* в учебниках 2018 года задания 2 и 3 поменяли местами: теперь 2 — Поиск кратчайшего пути, а 3 — Алгебра логики

✍ Решение:

Для решения будем использовать дерево:

Розовым отмечены неподходящие маршруты, а голубым — подходящие.
Заметим, что после 4-го уровня сверху, все варианты будут подходить.

Результат: 6

1_2: 1 задание:

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

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

Подобные задания для тренировки

✍ Решение:

Посчитаем сколько ребер у каждой вершины:

A -> 3 (В Г Д)
Б -> 1 (В)
В -> 4 (А Б Г Е)
Г -> 4 (А В Д К)
Д -> 2 (А Г)
Е -> 1 (В)
К -> 1 (Г)

Три ребра имеет только одна вершина — А, поэтому только А может соответствовать П3.
Уникальное значение количества ребер имеет также вершина Д, — два ребра. В таблице вершине Д будет соответствовать П4.
Вершины Г и В имеют по 4 ребра. Рассмотрим матрицу, в ней 4 числа соответствуют пунктам П2 и П5.
С пунктом Д пересекается только вершина Г (Г -> 4 (А В Д К)). В весовой матрице с вершиной Д пресекается П5. Значит вершина Г соответствует П5.
В П5 на пересечении с П3 находится число 6.

Результат: 6

Подробное решение данного 1 задания из демоверсии ЕГЭ 2018 года смотрите на видео:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

1_1: ЕГЭ по информатике:

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

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

✍ Решение:

Рассмотрим граф и посчитаем количество ребер из каждой вершины:

А - > 2 ребра (Г, В)
В - > 4 ребра (А, Г, К, Д)
Г - > 4 ребра (А, В, К, Д)
Б - > 2 ребра (Г, К)
К - > 5 ребер (Б, Г, В, Д, Е)
Е - > 2 ребра (К, Д)
Д - > 3 ребра (В, К, Е)

Мы выделили вершины, с уникальным числом ребер: 3 ребра соответствует только вершине Д, а 5 ребер соответствует только вершине К.
Рассмотрим таблицу и найдем те строки или столбцы, в которых 5 значений и 3 значения: Это П2 и П4.
Получаем П2 соответствует Д, а П4 соответствует К. На пересечении находится цифра 20.

Результат: 20

Кроме того, Вы можете посмотреть видео решения этого задания ЕГЭ по информатике:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь

1_6: Разбор 1 задания ЕГЭ:

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

	1	2	3	4	5	6	7	8
1			*	*			*
2			*	*				*
3	*	*
4	*	*			*	*	*	*
5				*		*	*
6				*	*			*
7	*			*	*
8		*		*		*

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

Подобные задания для тренировки

✍ Решение:

Для начала найдем уникальные вершины — у которых уникальное число ребер: это A (2 ребра) и H (6 ребер). В таблице им соответствуют номера 3 и 4:

	1	2	A	H	5	6	7	8
1			*	*			*
2			*	*				*
A	*	*
H	*	*			*	*	*	*
5				*		*	*
6				*	*			*
7	*			*	*
8		*		*		*

По схеме находим, что смежными вершинами для A являются B и G. В таблице определяем соответствующие им цифры — 1 и 2. Поскольку по заданию они нас не интересуют, обозначим их вместе:

	B,G	B,G	A	H	5	6	7	8
B,G			*	*			*
B,G			*	*				*
A	*	*
H	*	*			*	*	*	*
5				*		*	*
6				*	*			*
7	*			*	*
8		*		*		*

У обеих вершин B и G смежными являются уже известные A и H и, кроме того, вершины F и C. По первому столбцу или первой строке находим, что F или C будет соответствовать цифра 7, а по второй строке — цифра 8. Обозначим их в таблице:

	B,G	B,G	A	H	5	6	F,C	F,C
B,G			*	*			*
B,G			*	*				*
A	*	*
H	*	*			*	*	*	*
5				*		*	*
6				*	*			*
F,C	*			*	*
F,C		*		*		*

В результате получаем, что искомым вершинам — D и E — соответствуют цифры 5 и 6. Поскольку не имеет значения, какой именно цифре должна соответствовать та или иная вершина, то в ответе просто запишем эти цифры в порядке возрастания.

Результат: 56

Источник

Привет! Сегодня порешаем демонстрационный вариант ЕГЭ по информатике 2022.

В этой статье представлены задания с 1-ого по 5.

Источник задач: https://fipi.ru/ege/demoversii-specifikacii-kodifikatory#!/tab/151883967-5

Приятного прочтения!

Разбор демоверсии ЕГЭ по информатике 2022 (6-10 Задание)
Разбор демоверсии ЕГЭ по информатике 2022 (11-15 Задание)
Разбор демоверсии ЕГЭ по информатике 2022 (16-21 Задание)
Разбор демоверсии ЕГЭ по информатике 2022 (22-27 Задание)

Задание 1

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

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

Решение:

В начале нужно понять, какой город под какой буквой находится в таблице.

Точка К — особая точка, т.е. она отличается от остальных, т.к. только она имеет 6 дорог. Поэтому её легко найти в таблице, она под номером 5.

Рисунок имеет симметричную структуру. Поэтому например точки A и E мы не сможем отличить друг от друга. Но найдём примерное их расположение.

Города A и E имеют по две дороги. Значит, им соответствуют номера 1 и 3.

Городам Б и Д соответствуют номера 2 и 4. Т.к. эти номера по таблице связаны с 1 и 3. Опять, какому номеру соответствует конкретная буква, мы не сможем узнать.

С номерами 2 и 4, должны быть связаны уже В и Г. Значит, городам В и Г соответствуют номера 6 и 7.

Получается, чтобы ответить на вопрос задачи, нужно суммировать расстояния между 2 и 6 И 4 и 7.

13+7=20

Ответ: 20

Смотреть 1 Задание на YouTube

Задание 2

Миша заполнял таблицу истинности логической функции F

¬(y → (x ≡ w)) ∧ (z → x),

но успел заполнить лишь фрагмент из трёх различных её строк, даже
не указав, какому столбцу таблицы соответствует каждая из переменных
w, x, y, z.

Определите, какому столбцу таблицы соответствует каждая из переменных
w, x, y, z.

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

Пример. Функция F задана выражением ¬x / y, зависящим от двух
переменных, а фрагмент таблицы имеет следующий вид.

В этом случае первому столбцу соответствует переменная y, а второму
столбцу – переменная x. В ответе следует написать: yx.

Решение:

Напишем шаблон для решения 2 задания на языке программирования Python.

print('x', 'y', 'z', 'w')
for x in range(0, 2):
    for y in range(0, 2):
        for w in range(0, 2):
            for z in range(0, 2):
                if not(not(y) or (x==w)) and (not(z) or x):
                    print(x, y, z, w)

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

Отрицание меняется на not, следование представляем по формуле A->B = ¬A or B.

Получается

x y z w
0 1 0 1
1 1 0 0
1 1 1 0

Видно, что третий столбец — это y.

Т.к. у нас нет столбца, который состоит только из одних нулей, то в четвёртом столбце в пустой ячейке будет 1.

Получилась строчка из трёх 1. Значит, в первом столбце в пустой ячейке вверху будет 0. Следовательно, первый столбец — w.

Последний столбец достаётся z, т.к. из оставшихся переменных только у неё два 0 и одна 1. Второй столбец, по принципу исключения, — это x.

Ответ: wxyz

Смотреть 2 Задание на YouTube

Задание 3

В файле приведён фрагмент базы данных «Продукты» о поставках товаров
в магазины районов города. База данных состоит из трёх таблиц.

Таблица «Движение товаров» содержит записи о поставках товаров в
магазины в течение первой декады июня 2021 г., а также информацию
о проданных товарах. Поле Тип операции содержит значение Поступление
или Продажа, а в соответствующее поле Количество упаковок, шт.
занесена информация о том, сколько упаковок товара поступило в магазин
или было продано в течение дня. Заголовок таблицы имеет следующий вид.

ID
операции

Дата

ID
магазина

Артикул

Тип
операции

Количество
упаковок,
шт.

Цена,
руб./шт.

Таблица «Товар» содержит информацию об основных характеристиках
каждого товара. Заголовок таблицы имеет следующий вид.

Артикул

Отдел

Наименование

Ед.
изм.

Количество
в упаковке

Поставщик

Таблица «Магазин» содержит информацию о местонахождении магазинов.
Заголовок таблицы имеет следующий вид.

На рисунке приведена схема указанной базы данных.

Используя информацию из приведённой базы данных, определите на
сколько увеличилось количество упаковок яиц диетических, имеющихся в
наличии в магазинах Заречного района, за период с 1 по 10 июня
включительно.

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

Решение (через формулу):

Откроем файл Excel. Внизу у нас три вкладки (три таблицы).

Есть магазины, есть товары, есть операции, какие товары, куда перемещаются.

Прочитаем ещё раз внимательно вопрос задачи. Переходим на вкладку Магазин. Выделим столбец «Район» и отсортируем по данному столбцу таблицу (кнопка сортировки находится обычно в правом верхнем углу). Если появится вопрос об автоматическом расширении выделенного диапазона, отвечаем утвердительно.

Теперь удобно посмотреть ID магазинов Заречного Района. Всего получается 4 ID: M3, M9, M11, M14.

Переходим на вкладку Товар. Нас интересует яйцо диетическое. Ищем по поиску (Ctrl + F) и получаем Артикул данного товара. Это номер 15.

Данные мы собрали, теперь переходим на вкладку Движение товаров.

Сначала подсчитаем сколько поступило указанного товара в указанные торговые точки за период 1-10 июня. Убедимся, что первая строчка не подходит нам по условию и в ячейке H2 ставим значение 0. Это число олицетворяет количество поступивших товаров.

В ячейке H3 пропишем формулу:

=ЕСЛИ(И(ИЛИ(C3=«M3»;C3=«M9»;C3=«M11»; C3=«M14»); D3=15; F3=«Поступление»);H2+E3;H2)

Эту формулу мы распространяем на весь столбец H. Тогда она будет анализировать каждую строчку и подсчитывать количество поступившего товара, учитывая все обстоятельства задачи. В самой последней ячейке столбца H получается число 1420. Это и есть то количество нашего товара, которое поступило в указанные торговые точки. Про дату в этой задаче думать не нужно, т.к. вся таблица по операциям происходит в пределах 1-10 июня.

Аналогично, подсчитаем в столбце I, какое количество убыло. Тогда формула получается:

=ЕСЛИ(И(ИЛИ(C3=«M3»;C3=«M9»;C3=«M11»; C3=«M14»); D3=15; F3=«Продажа»);I2+E3;I2)

Получаем количество проданных товаров 454.

Подсчитаем на сколько же увеличилось товаров:

1420-454=966

Это и будет ответ.

Ответ: 966

Смотреть 3 Задание (решение через формулу) на YouTube

Решение (через фильтры)

В подобных задачах удобно воспользоваться фильтрами!

Выбираем вкладку Магазин и нажимаем кнопку Фильтр.

При этом должна быть выделена не пустая ячейка.

Кнопка Фильтр может находится и на главной панеле.

Теперь можно отфильтровать магазины Заречного района.

Нажмём «ОК», и у нас останутся только магазины Заречного района. Фиксируем их ID.

Переходим на вкладку Товар. Включаем фильтры. С помощью фильтров оставляем только яйцо диетическое и узнаём его Артикл.

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

В начале найдём количество упаковок, которые поступили в магазины, поэтому в столбце Тип операции выбираем «Поступление«.

Выделяем ячейки столбца Количество упаковок для получившихся операций, и внизу смотрим сумму этих ячеек.

Здесь нельзя пользоваться стандартной функцией СУММ, потому что она суммируем ещё и скрытые ячейки. А так мы получаем сумму выделенных ячеек.

Получается количество поступивших упаковок равно 1420. Аналогично количество убывших получается 454.

1420-454=966

Ответ: 966

Смотреть 3 Задание (решение через фильтры) на YouTube

Задание 4

Для кодирования некоторой последовательности, состоящей из букв Л, М,
Н, П, Р, решили использовать неравномерный двоичный код,
удовлетворяющий условию, что никакое кодовое слово не является началом
другого кодового слова. Это условие обеспечивает возможность
однозначной расшифровки закодированных сообщений. Для букв Л, М, Н
использовали соответственно кодовые слова 00, 01, 11. Для двух оставшихся
букв П и Р кодовые слова неизвестны.

Укажите кратчайшее возможное кодовое слово для буквы П, при котором
код будет удовлетворять указанному условию. Если таких кодов несколько,
укажите код с наименьшим числовым значением.

Решение:

Т.к. никакое кодовое слово не является началом другого кодового слова, то, значит, выполняется условие Фано.

Следовательно, можно воспользоваться приёмом дерево Фано.

Разместим буквы для которых известны коды на дереве Фано.

При построении дерева Фано мы проращивает от корня две ветки 0 и 1. От каждой ветки тоже можно прорастить две ветки 0 и 1 и т.д. Если буква «села» на ветку, то она блокирует эту ветку, и больше нельзя проращивать новые ответвления от неё.

У нас остались две буквы П и Р, а прорастить можем только одну ветку (из 1 — прорастить 0). Мы проращиваем эту ветку и от неё проращиваем два ответвления, и теперь мы уже можем разместить оставшиеся буквы на дереве.

Для П выбираем код с меньшим числовым значением — 100, как написано в условии. Букве Р достаётся код — 101.

Ответ: 100

Смотреть 4 Задание на YouTube

Задание 5

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему
новое число R следующим образом.

1. Строится двоичная запись числа N.

2. К этой записи дописываются справа ещё два разряда по следующему
правилу:

а) складываются все цифры двоичной записи числа N, и остаток от деления
суммы на 2 дописывается в конец числа (справа).
Например, запись 11100 преобразуется в запись 111001;

б) над этой записью производятся те же действия – справа дописывается
остаток от деления суммы её цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем
в записи исходного числа N) является двоичной записью результирующего
числа R.

Укажите такое наименьшее число N, для которого результат работы
данного алгоритма больше числа 77. В ответе это число запишите
в десятичной системе счисления.

Решение:

На вход поступает натуральное (обычное, не дробное, положительное) число N.

Это число алгоритм переводит в двоичную систему.

Сказано, что дописываются два разряда справа к тому двоичному числу, которое получили в первом пункте.

Про первый дополнительный разряд написано в пункте a второго правила: «складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001».

Если сказать более просто, то автомат подсчитывает количество единиц у первоначального двоичного числа N, полученного в первом пункте. Если количество чётное, то автомат в первый дополнительный разряд должен поставить 0. Если количество нечётное, то автомат в первый дополнительный разряд должен поставить 1.

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

В вопросе просят указать входящее наименьшее число N, чтобы автомат выдал число R больше 77.

Т.к. число R должно быть больше 77, то переведём число 78 (77 + 1) в двоичный вид, чтобы можно было оценить входящее число N.

Это можно сделать стандартным калькулятором windows, переключив его в режим «Программиста» (Вид->»Программист»).

Получилось число 1001110. Будем рассматривать (начиная с 1001110) числа на выполнение правил, которые заданы для алгоритма. Если все правила будут выполнены, значит, мы получили то число, по которому вычислим изначальное N. Нам нужно получить именно минимальное число, поэтому мы и начали с минимального возможного претендента для числа R (78).

Здесь нам сразу повезло, сразу число 78 удовлетворяет всем условиям. Нас просили написать именно число N, поэтому от числа 1001110 отбрасываем два разряда и переводим в десятичную систему.

Переводим в десятичную систему 10011 -> 19.

Ответ: 19

Смотреть 5 Задание на YouTube

Очень доступное объяснение. Жду разбор следующих заданий

Следующие задания уже разобраны из Демоверсии 2022. Можете посмотреть в разделе ЕГЭ.

Источник

Доброго времени суток каждому жителю Хабрвилля! Давненько я не писал статей! Пора это исправить!

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

Вот я и подумал, чтобы не получилось как в песне, стоит этим заняться. Я расскажу про все задачи первой части и их решения на примере демо варианта ЕГЭ за октябрь.

Всех желающих — приглашаю ниже!

Быстрый перевод из системы в систему

В Python есть интересные функции bin(), oct() и hex(). Работают данные функции очень просто:

bin(156) #Выводит '0b10011100'
oct(156) #Выводит '0o234'
hex(156) #Выводит '0x9c'

Вывод в интерпретационном режиме

Как вы видите, выводится строка, где 0b — означает, что число далее в двоичной системе счисления, 0o — в восьмеричной, а 0x — в шестнадцатеричной. Но это стандартные системы, а есть и необычные…

Давайте посмотрим и на них:

n = int(input()) #Вводим целое число
 
b = '' #Формируем пустую строку
 
while n > 0: #Пока число не ноль
    b = str(n % 2) + b #Остатот от деления нужной системы (в нашем сл записываем слева
    n = n // 2 #Целочисленное деление
 
print(b) #Вывод

Данная программа будет работать при переводе из десятичной системы счисления в любую до 9, так как у нас нет букв. Давайте добавим буквы:

n = int(input()) #Вводим целое число

b = '' #Формируем пустую строку

while n > 0: #Пока число не ноль
	if (n % 21) > 9: #Если остаток от деления больше 9...
		if n % 21 == 10: #... и равен 10...
			b = 'A' + b #... запишем слева A
		elif n % 21 == 11:#... и равен 11...
			b = 'B' + b#... запишем слева B

'''

И так далее, пока не дойдём до системы счисления -1 (я переводил в 21-ную систему и шёл до 20)

'''

		elif n % 21 == 11:
			b = 'B' + b
		elif n % 21 == 12:
			b = 'C' + b
		elif n % 21 == 13:
			b = 'D' + b
		elif n % 21 == 14:
			b = 'E' + b
		elif n % 21 == 15:
			b = 'F' + b
		elif n % 21 == 16:
			b = 'G' + b
		elif n % 21 == 17:
			b = 'H' + b
		elif n % 21 == 18:
			b = 'I' + b
		elif n % 21 == 19:
			b = 'J' + b
		elif n % 21 == 20:
			b = 'K' + b
	else: #Иначе (остаток меньше 10)
		b = str(n % 21) + b #Остатот от деления записываем слева
	n = n // 21 #Целочисленное деление

print(b) #Вывод

Способ объёмен, но понятен. Теперь давайте используем тот же функцию перевода из любой системы счисления в любую:

def convert_base(num, to_base=10, from_base=10):
    # Перевод в десятичную систему
    if isinstance(num, str): # Если число - строка, то ...
        n = int(num, from_base) # ... переводим его в нужную систему счисления
    else: # Если же ввели число, то ...
        n = int(num) # ... просто воспринять его как число
    # Перевод десятичной в 'to_base' систему
    alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" # Берём алфавит
    if n < to_base: # Если число меньше системы счисления в которую переводить...
        return alphabet[n] # ... вернуть значения номера в алфавите (остаток от деления)
    else: # Иначе...
        return convert_base(n // to_base, to_base) + alphabet[n % to_base] # ... рекурсивно обратиться к функии нахождения остатка

Вызвав функцию вывода print(convert_base(156, 16, 10)) мы переведём 156 из 10 в 16 систему счисления, а введя print(convert_base('23', 21, 4)) переведёт 23 из 4-ичной в 21-ичную систему (ответ: B).

Задача 2

Все задания беру из первого октябрьского варианта (он же вариант № 9325894) с сайта Решу.ЕГЭ.

Решение данной задачи совсем простое: банальный перебор.

print('y', 'x', 'z', 'F') #Напечатаем заголовки таблицы
for y in range(2): #Берём все переменные и меняем их в циклах '0' и '1'
	for x in range(2):
		for z in range(2):
			for w in range(2):
				F = ((not x or y) == (not z or w)) or (x and w) #Записываем функцию
				print(x, y, z, F) #Выводим результат

Результат:

Нам вывелась вся таблица истинности (1 = True, 0 = False). Но это не очень удобно. Обратите внимание, что в задании, функция равно 0, так и давайте подправим код:

print('y', 'x', 'z', 'F') #Напечатаем заголовки таблицы
for y in range(2): #Берём все переменные и меняем их в циклах '0' и '1'
	for x in range(2):
		for z in range(2):
			for w in range(2):
				F = ((not x or y) == (not z or w)) or (x and w) #Записываем функцию
				if not F:
					print(x, y, z, F) #Выводим результат

Результат:

Далее — простой анализ.

Задача 5

Данная задача легко решается простой последовательностью действий в интерпретационном режиме:

Задача 6

Перепечатали и получили ответ:

s = 0
k = 1
while s < 66:
    k += 3
    s += k
print(k)

Задача 12

В очередной раз, просто заменим слова на код:

a = '9' * 1000

while '999' in a or '888' in a:
	if '888' in a:
		a = a.replace('888', '9', 1)
	else:
		a = a.replace('999', '8', 1)
print(a)

Задача 14

Компьютер железный, он всё посчитает:

a = 4 ** 2020 + 2 ** 2017 - 15
k = 0

while a > 0:
    if a % 2 == 1:
    	k += 1
    a = a // 2

print(k)

Задача 16

Опять же, просто дублируем программу в python:

def F(n):
    if n > 0:
        F(n // 4)
        print(n)
        F (n - 1)
print(F(5))

Результат:

Задача 17

Задача с файлом. Самое сложное — достать данные из файла. Но где наша не пропадала?!

with open("17.txt", "r") as f: #Открыли файл 17.txt для чтения
    text = f.read() #В переменную text запихнули строку целиком
a = text.split("n") #Разбили строку энтерами (n - знак перехода на новую строку)

k = 0 #Стандартно обнуляем количество
m = -20001 #Так как у нас сумма 2-ух чисел и минимальное равно -10000, то минимум по условию равен -20000, поэтому...

for i in range(len(a)): #Обходим все элементы массива
	if (int(a[i - 1]) % 3 == 0) or (int(a[i]) % 3 == 0): #Условное условие
		k += 1 #Счётчик
		if int(a[i - 1]) + int(a[i]) > m: #Нахождение минимума
			m = int(a[i - 1]) + int(a[i])

print(k, m) #Вывод

Немного пояснений. Функция with() открывает файл считывает данные при помощи функции read() и закрывает файл. В остальном — задача стандартна.

Задача 19, 20 и 21

Все три задачи — задачи на рекурсию. Задачи идентичны, а вопросы разные. Итак, первая задача:

Пишем рекурсивную функцию и цикл перебора S:

def f(x, y, p): #Рекурсивная функция
	if x + y >= 69 or p > 3: #Условия завершения игры
		return p == 3
	return f(x + 1, y, p + 1) or f(x, y + 1, p + 1) or
		   f(x * 2, y, p + 1) or f(x, y * 3, p + 1) #Варианты действий

for s in range (1, 58 + 1): #Перебор S
	if f(10, s, 1): #Начали с 10 камней
		print(s)
		break

Немного пояснений. В рекурсивной функции существует 3 переменные x — число камней в первой куче, y — число камней во второй куче, p — позиция. Позиция рассчитывается по таблице:

	Игра	Петя	Ваня	Петя	Ваня	Петя
p	1	2	3	4	5	6

Далее — всё по условию задачи.

Вторая задача на теорию игр:

Все отличия в рамке. Ну и код, соответственно, не сильно отличается:

def f(x, y, p): #Рекурсивная функция
	if x + y >= 69 or p > 4: #Условия завершения игры
		return p == 4
	if p % 2 != 0:
		return f(x + 1, y, p + 1) or f(x, y + 1, p + 1) or
			   f(x * 2, y, p + 1) or f(x, y * 3, p + 1) #Варианты действий
	else:
		return f(x + 1, y, p + 1) and f(x, y + 1, p + 1) and
			   f(x * 2, y, p + 1) and f(x, y * 3, p + 1) #Варианты действий


for s in range (1, 58 + 1): #Перебор S
	if f(10, s, 1): #Начали с 10 камней
		print(s)

Отличия:

Выиграл Петя, соответственно, позиция 4
Так как Петя не может выиграть за один ход — он выигрывает за 2 хода (and, а не or на нечётных позициях (играх Пети))
Убрали break, так как нам нужны все S, а не единственный

Последняя вариация задачи:

Сразу код:

def f(x, y, p): #Рекурсивная функция
	if x + y >= 69 or p > 5: #Условия завершения игры
		return p == 3 or p == 5
	if p % 2 == 0:
		return f(x + 1, y, p + 1) or f(x, y + 1, p + 1) or
			   f(x * 2, y, p + 1) or f(x, y * 3, p + 1) #Варианты действий
	else:
		return f(x + 1, y, p + 1) and f(x, y + 1, p + 1) and
			   f(x * 2, y, p + 1) and f(x, y * 3, p + 1) #Варианты действий


for s in range (1, 58 + 1): #Перебор S
	if f(10, s, 1): #Начали с 10 камней
		print(s)

Ну и всего лишь 2 отличия:

Позиции 3 или 5, а не 4, так как выиграл Ваня
На второй ход выигрывает Ваня и нам нужно or и and поменять. Я заменил только кратность 2.

Задача 22

Ctrl+C, Ctrl+V — наше всё!

for i in range(1, 100000):
	x = i
	L = 0
	M = 0
	while x > 0 :
		L = L+1
		if (x % 2) != 0:
			M = M + x % 8
		x = x // 8
	if L == 3 and M == 6:
		print(i)

Задача 23

Итак, код:

def f(x, y):
	if x > y: #Перегнали цель
		return 0
	if x == y:  #Догнали цель
		return 1
	if x < y: #Догоняем цель тремя методами
		return f(x + 1, y) + f(x + 2, y) + f(x * 2, y)

print(f(3, 10) * f(10, 12)) #Прошло через 10, значит догнали 10 и от де догоняем 12

Так как в условии задачи мы увеличиваем число, но будем числа «догонять». Три метода описаны, ну а пройти через 10 — значит дойти до него и идти от него.

Собственно, это и есть вся первая часть ЕГЭ по информатике решённая на Python.

Ссылка на репозиторий со всеми программами:

Надеюсь, что смог помочь в своей статье выпускникам и готовящимся

Остался один вопрос — нужен ли разбор второй части ЕГЭ по информатике на Python? Оставлю этот вопрос на ваше голосование.

Всем удачи!

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

Делаю разбор второй части?

Проголосовали 105 пользователей.

Воздержались 15 пользователей.

Источник

Единый государственный экзамен по информатике состоит из 27 заданий. В задании 1 проверяются навыки кодирования и проведения операций над числами в различных системах счисления. Школьник должен уметь переводить число из десятичной системы счисления в произвольную и наоборот, а также выполнять сложение и вычитание чисел в различных системах счисления и сравнивать их. Здесь вы можете узнать, как решать задание 1 ЕГЭ по информатике, а также изучить примеры и способы решения на основе подробно разобранных заданий.

Укажите наименьшее четырёхзначное шестнадцатеричное число, двоичная запись которого содержит ровно N нулей. В ответе запишите только само шестнадцатеричное число, основание системы счисления указывать не нужно.