Решение егэ информатика 4 задание в эксель
4-е задание: «Кодирование и декодирование информации»
Уровень сложности — базовый,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 2 минуты.
Проверяемые элементы содержания: Умение кодировать и декодировать информацию
Плейлист видеоразборов задания на YouTube:
ЕГЭ 4.1: Для кодирования букв О , В , Д , П , А решили использовать двоичное представление чисел 0 , 1 , 2 , 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).
Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.
Ответ: 22162
- Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:
- Теперь закодируем последовательность букв из слова ВОДОПАД :
- Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:
ЕГЭ 4.2: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:
a | b | c | d | e |
---|---|---|---|---|
000 | 110 | 01 | 001 | 10 |
Какой набор букв закодирован двоичной строкой 1100000100110 ?
Ответ: b a c d e
- Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.
Результат: b a c d e.
✎ 2 вариант решения:
-
Этот вариант решения 4 задания ЕГЭ более сложен, но тоже верен.
📹 Видео (теоретическое решение)
📹 Видеорешение на RuTube здесь (теоретическое решение)
ЕГЭ 4.3:
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4 , и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23 , то получим последовательность 0010100110 ).
Определите, какое число передавалось по каналу в виде 01100010100100100110 .
Ответ: 6 5 4 3
📹 Видео (теоретическое решение)
📹 Видеорешение на RuTube здесь (теоретическое решение)
ЕГЭ 4.4:
Для кодирования некоторой последовательности, состоящей из букв К , Л , М , Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0 , для буквы К — кодовое слово 10 .
Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
Ответ: 9
- Найдём самые короткие возможные кодовые слова для всех букв.
- Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н).
- Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
- Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Условие Фано соблюдается.
- Суммарная длина всех четырёх кодовых слов равна:
✎ 2 вариант решения:
-
Будем использовать дерево. Влево откладываем 0, вправо — 1:
ЕГЭ по информатике 4 (раньше №5) задание 2017 ФИПИ вариант 2 (под редакцией Крылова С.С., Чуркиной Т.Е.):
Укажите кратчайшее кодовое слово для буквы Г , при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Ответ: 00
- Наименьшие коды могли бы выглядеть, как 0 и 1 (одноразрядные). Но это не удовлетворяло бы условию Фано (А начинается с единицы — 101010, Б начинается с нуля — 011011).
- Следующим наименьшим кодом было бы двухбуквенное слово 00. Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00.
ЕГЭ по информатике 4 (раньше №5) задание 2017 ФИПИ вариант 16 (под редакцией Крылова С.С., Чуркиной Т.Е.):
Для кодирования некоторой последовательности, состоящей из букв А , Б , В , Г и Д , решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код:
Укажите, каким кодовым словом должна быть закодирована буква Д . Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Ответ: 101
- Так как необходимо найти кодовое слово наименьшей длины, воспользуемся деревом. Влево будем откладывать нули, а вправо — единицы:
Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Ответ: 1100
- Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
📹 Видео (теоретическое решение)
📹 Видеорешение на RuTube здесь (теоретическое решение)
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Ответ: 00
- Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
- Поскольку в задании явно не указано о том, что код должен удовлетворять условию Фано, то дерево нужно построить как с начала (по условию Фано), так и с конца (обратное условие Фано).
Дерево по условию Фано (однозначно декодируется с начала):
Дерево по обратному условию Фано (однозначно декодируется с конца):
Результат: 00
Привет! Сегодня узнаем, как решать 4 задание из ЕГЭ по информатике нового формата 2021.
Четвёртое задание из ЕГЭ по информатике раскрывает тему кодирование информации. Одним из центральных приёмов при решении задач подобного типа является построение дерева Фано. Рассмотрим на примерах этот метод.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование
Т.к. код букв должен удовлетворять условию Фано (т.е. однозначно декодироваться), то расположим буквы, которые уже имеют код (A, B, C), на Дереве Фано.
Дерево Фано для двоичного кодирования начинается с двух направлений, которые означают 0(ноль) и 1(единицу) (цифры двоичного кодирования).
От каждого направления можно также рисовать только два направления: 0(ноль) и 1(единицу) и т.д. Для удобства будем рисовать 1(единицу) только вправо, а 0(ноль) только влево.
Получается структура похожая на дерево!
В конце каждой ветки можно располагать букву, которую мы хотим закодировать, но если мы расположили букву, от этой ветки больше нельзя делать новых ответвлений.
Буква C заблокировала левую ветку, поэтому будем работать с правой частью нашего дерева.
Если мы расположим какую-нибудь букву на оставшуюся ветку (100), то эта ветка заблокируется, и нам некуда будет писать остальные 2 буквы. Поэтому продолжаем ветку (100) дальше.
Теперь свободно уже две ветки, а нам нужно закодировать ещё три буквы. Поэтому должны ещё раз продолжить дерево от какой-нибудь ветки.
Но уже видно, что букве F будет правильно присвоить код 1000, т.к. нам в условии сказано, что код буквы F должен соответствовать наименьшему возможному двоичному числу. Как расположить буквы D и E в данной задаче не принципиально.
Ответ: 1000.
Ещё один важный тип задания 4 из ЕГЭ по информатике нового формата 2021.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Коды букв должны удовлетворять условию Фано. Некоторые буквы уже имеют заданные коды (Б, К, Л). Нам нужно, чтобы слово АБСЦИССА имело как можно меньше двоичных знаков. Заметим, что буква C встречается три раза, а буква A два раза, значит, этим буквам стараемся присвоить как можно меньшую длину!
Отметим на дереве Фано уже известные буквы (Б, К, Л).
У нас осталось 4 (четыре) буквы, а свободных веток 3(три), поэтому мы должны продолжить дерево. но какую ветку продолжить ?
Если продолжить линию 1-0, то получится такая картина :
Теперь получились 4(четыре) свободные ветки равной длины (3(трём) двоичным символам). Т.к. ветки равной длины, то не важно на какую ветку какую букву расположим.
Посчитаем общую длину слова АБСЦИССА.
3 + 2 + 3 + 3 + 3 + 3 + 3 + 3 = 23.
Продлим линию 1-1-0 (можно и 0-1-1, не принципиально, т.к. эти ветки имеют одинаковую длину.), то получится:
Из этих же соображений букве А присваиваем код из трёх двоичных символов 0-1-1.
3 + 2 + 2 + 4 + 4 + 2 + 2 + 3 = 22
Длина получилась меньше, чем в первом варианте. Других вариантов нет, поэтому ответ будет 22.
В этой задаче ничего не сказано про условие Фано. Здесь уже все буквы закодированы, осталось написать сам код.
Задача сводится к переводу из двоичной системы в восьмеричную систему. На эту тему был урок на моём сайте.
Ответ: 151646.
На этом всё! Увидимся на следующих занятиях по подготовке к ЕГЭ по информатике.
ЕГЭ по информатике 2022 - Задание 10 (Поиск в тексте)
Стас костюшкин 15-10-2020 в 18:48:52
Этого не знаю. Это просто примерные задачи, которые наиболее часто попадаются в книжках и на сайтах по подготовке к ЕГЭ по информатике.
Калужский Александр 15-10-2020 в 18:57:40
Глеб Цыбрий 15-11-2020 в 10:30:33
Ольга Владимировна Сорокина 05-03-2021 в 12:09:08
Ольга Владимировна Сорокина 05-03-2021 в 12:09:14
В этом уроке мы поговорим о задании 4 из ЕГЭ по информатике 2022.
Задание 4 включает в себя понятие кодирование и декодирование информации.
Приступим к тренировочным заданиям из ЕГЭ по информатике 2022.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 00, 01, 100, 110. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Используем приём Дерево Фано. Расставим на этом дереве те буквы, для которых уже известны кодовые слова.
Дерево рисуется обычно сверху вниз. В начале от дерева рисуются две ветки: ветка 0 и ветка 1. От каждой ветки можно нарисовать ещё две ветки, так же 0 и 1, и т. д.
Для удобства ветки с 1 будем направлять вправо, а ветки с 0 будем направлять влево.
В конце каждой ветки можно размещать буквы, но если мы разместили букву, то эта ветка блокируется, и от этой ветки больше нельзя делать новые ответвления.
Нам осталось закодировать (расположить на дереве) две буквы: Д и Е.
Мы можем нарастить ещё две ветки от точки 1-1. Тогда получится код 111. И от точки 1-0. Тогда получится код 101.
Для буквы Д нужно выбрать код с наименьшим числовым значением. Значит, для буквы Д выбираем код 101, а для буквы Е выбираем код 111.
Закрепим приём дерево Фано на ещё одной примерной задаче из ЕГЭ по информатике 2022.
Задача(Стандартная, закрепление)
Для кодирования некоторой последовательности, состоящей из букв Н, О, П, Р, С, Т, У, Ф решили использовать неравномерный двоичный код, удовлетворяющий условию, что ни одно кодовое слово не является началом другого кодового слова. Для букв Н, О, П, Р, С, Т использовали соответственно кодовые слова 10, 110, 010, 0110, 111, 0111. Укажите кратчайшее возможное кодовое слово для буквы У, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Здесь код так же должен удовлетворять Условию Фано, т.к. сказано, что ни одно кодовое слово не является началом другого кодового слова .
Значит, можем воспользоваться Деревом Фано . Расположим на Дереве Фано буквы, для которых уже известны кодовые слова.
Нам нужно закодировать ещё две буквы: У, Ф. У нас единственная возможность осталась прорастить ветку от точки 0. От этой точки проращиваем ветку 0 и от этой ветки проращиваем ещё две ветки 0 и 1.
Букву У размещаем на позиции 000, потому что для этой буквы нужно выбрать код с наименьшим числовым значением.
Ещё одна примерная задача из ЕГЭ по информатике 2022 является частым гостем в различных тренировочных вариантах.
Задача (Стандартная, закрепление)
Расставим на дереве Фано буквы, для которых известны коды.
Нам осталось расположить 4 буквы: Д, Л, E, Н.
Буква Е встречается три раза в слове ДЕЛЕНИЕ, значит, ей нужно постараться присвоить самый короткий код. По дереву видно, что можно букве Е присвоить код 10.
Буквы Д, Л, Н встречаются в слове ДЕЛЕНИЕ 1 раз. Одну букву можно разместить на позицию 111. Так же можно продлить ветку из точки 00, а затем от позиции 001 сделать два отростка. У нас получатся ещё два свободных места: 0011 и 0010.
Можно оставшиеся буквы разместить следующим образом:
Подсчитаем какое количество двоичных знаков потребуется для кодирования слова ДЕЛЕНИЕ.
3+2+4+2+4+3+2=20
Ответ: 20
Далее решим непростую задачу из тренировочных вариантов ЕГЭ по информатике 2022. Похожая задача была в сборнике С. С. Крылова в 2021 году.
Для букв М, Н, Р используются такие кодовые слова: М: 00011, Н: 1001, Р: 01100.
Укажите кратчайшее кодовое слово для буквы Т, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Нужно, чтобы код декодировался однозначно. Чтобы код декодировался однозначно, можно использовать условие Фано. Мы видим, что в уже известных кода не нарушается условие Фано. Узнаем код для буквы Т по дереву Фано. Отметим известные буквы.
Куда разместить букву Т? Чтобы кодовое слово было кратчайшее, разместим букву Т на позицию 11.
Сложность этой задачи заключается в том, что явно не указано, что нужно использовать условие Фано. Так же однозначное декодирование будет, если используется обратное условие Фано.
Кодовое слово 0 мы использовать не можем, потому что 0 - это окончание кодового слова буквы Р. Кодовое слово 1 - это окончание кодовых слов букв М и Н. Кодовое слово 00 - это окончание кодового слова буквы Р. А вот 10 подходит для буквы Т.
Получилась следующая ситуация. Если кодовые слова будут удовлетворяют условию Фано, то для буквы Т можно написать кратчайшее кодовое слово 11 с минимальным числовым значением. Если кодовые слова будут удовлетворяют обратному условию Фано, то для буквы Т можно написать кратчайшее кодовое слово 10 с минимальным числовым значением.
И в том и в другом случае будет однозначное декодирование. Но мы выбираем тот случай, когда кодовое слово будет наименьшим числовым значением. Таким образом, в ответе напишем 10.
Разберём ещё один нюанс в подобных задах из ЕГЭ по информатике.
Задача (Ещё раз про однозначное декодирование)
Здесь условие похоже на то, которое было в предыдущей задаче. Но обратное условие Фано здесь не применимо, т.к. код для буквы О является окончанием для кода буквы М.
Выбираем из двух вариантов: 110 и 101. Но останавливаемся на 101, т.к. это кодовое слово с наименьшим числовым значением.
Решим задачу, которая часто встречается в бумажных сборниках по подготовке к ЕГЭ по информатике.
Задача (код не удовлетворяет условию Фано)
Укажите самое короткое кодовое слово для буквы E, при котором код не будет удовлетворять условию Фано, при этом в записи самого этого слова должно использоваться более одного символа, а само слово не должно совпадать ни с одним из используемых слов для букв с известными кодами.
Если таких слов несколько, то укажите слово с наименьшим числовым значением.
Здесь код не должен однозначно декодироваться.
Подходит код 00, т.к. длина этого кодового слова больше чем 1 символ. Этот код не совпадает ни с одним кодом для известных букв. Этот код нарушает принцип условия Фано, видно, что он является началом кодового слова буквы D. И этот код имеет самое маленькое числовое значение.
В 4 задании из ЕГЭ по информатике 2022 не обязательно может попасться задача, связанная с условием Фано. Может просто быть задача на кодирование и декодирование информации.
Для кодирования букв X, К, Л, О, Д решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ХОЛОДОК таким способом и результат запишите шестнадцатеричным кодом.
Распишем, как кодируются все буквы в двоичной системе. Ноль и один кодируются одним разрядом, поэтому к ним слева приписывается ноль, как написано в условии.
Выписываем слово ХОЛОДОК и под ним кодовые слова букв.
Чтобы перевести из двоичной системы число в шестнадцатиричную систему, мы должны двоичные цифры разбить по четвёркам, начиная с правого края. Каждая четвёрка превращается в цифру в шестандцатиричной системе. Таблицу перевода четвёрок двоичных цифр в шестнадцатиричную систему можно посмотреть в этой статье.
Т.к. ЕГЭ по информатике сдаётся в компьютерной форме, то можно воспользоваться стандартным калькулятором в режиме программист.
Продолжаем анализ демонстрационного варианта ЕГЭ по информатике 2022.
В этой статье разберём с 22-ого по 27 задание.
ЕГЭ по информатике 2022 будет повержено!
Ниже на четырёх языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 4, а потом 5.
Решение данного задания будет похоже на решение 6 задания из ЕГЭ по информатике 2022.
С помощью перебора на языке Python найдём при каких значениях переменная L=4 И переменная M=5 в конце программы.
Наибольшее значение равно 49.
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Решим задачу c помощью шаблона на языке Python.
Число x, это то число, с которым мы работаем. Число y - это куда нужно прийти.
Если число x достигло пункта назначения, то возвращаем 1. Если оно перескочило y, то возвращаем 0. А если ещё не дошло до y, то продолжаем вычисления с помощью рекурсии.
У нас число 10 обязательное, поэтому разбиваем функцию следующим образом F(1, 10)*F(10, 20), через умножение. Это и будет ответ. Получается 28.
Текстовый файл состоит из символов P, Q, R и S.
Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых нет идущих подряд символов P. Для выполнения этого задания следует написать программу.
Напишем решение на языке Python.
Подсчитываем символы, пока не встретилась комбинация двух P подряд. Как только встретилась данная комбинация, сбрасываем счётчик на 1. Здесь мы сбрасываем счётчик на значение 1, чтобы учесть один символ, которые находится в самой комбинации PP. И в начале мы тоже устанавливаем счётчик в значение 1 по этой же причине.
Мы проходим в цикле for до длины строки минус один. Значение 1 в счётчике при сбросе и в начале программы так же компенсирует и тот момент, что мы не подсчитываем последний символ!
При изменении счётчика, сохраняем максимальное значение в переменной mx
Если бы у нас была вместо PP другая комбинация, состоящая к примеру из 5 символов, то мы бы тогда в начале и при сбросе писали в счётчик значение 5-1=4.
В этой задаче получается ответ 188.
Пусть M – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то значение M считается равным нулю.
Напишите программу, которая перебирает целые числа, бо́льшие 700 000, в порядке возрастания и ищет среди них такие, для которых значение M оканчивается на 8. Выведите первые пять найденных чисел и соответствующие им значения M.
Формат вывода: для каждого из пяти таких найденных чисел в отдельной строке сначала выводится само число, затем – значение М. Строки выводятся в порядке возрастания найденных чисел.
Количество строк в таблице для ответа избыточно.
На ЕГЭ по информатике 2022 удобно писать программы на языке Python.
В данной программе перебираются числа в цикле for, начиная с 700001.
Переменная b-считается наибольшим делителем числа i. Затем, с помощью ещё одного цикла for перебираются числа с 2 до корня числа i (включительно). Ищем тем самым наименьший делитель.
Если до корня числа включительно не встретился ни один делитель, значит, у числа нет делителей, кроме 1 и самого числа.
Пусть у нас есть число A. Если у этого числа есть делитель d1, то он находится до корня этого числа. А вот то число (так же делитель), на которое умножается это число d1, чтобы получить A, будет находиться после корня A.
Получается, что у каждого делителя есть своя пара. У единицы - это само число. Причём один делитель из пары находится до корня, другой после корня. Исключением будет тот случай, когда из числа А извлекается целый корень. Тогда для этого корня не будет пары (парой и будет само это число √A * √A = A).
Таким образом, первый найденный делитель будет являться наименьшим делителем. А вот делительный, который находится в паре с наименьшим делителем, будет наибольшим.
После того, как мы нашли наименьший делитель (он будет сидеть в переменной j) и наибольший делитель b, выходим из второго цикла for.
Если переменная b осталась равна нулю, то, значит, у числа i нет указанных делителей, и переменная M должна равняться 0. Если b не равна нулю, то M=j+b.
Проверить, на что оканчивается число, можно узнав остаток от деления числа на 10.
Переменная count следит, чтобы было распечатано ровно 5 чисел, которые удовлетворяют условию задачи.
Ответ:
700005 | 233338 |
700007 | 100008 |
700012 | 350008 |
700015 | 140008 |
700031 | 24168 |
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов.
Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
В первой строке входного файла находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 10 000) и N – количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое – в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем – максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов – 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера:
Решим задачу с помощью Excel. Чтобы открыть текстовый файл в программе Excel, выбираем Файл->Открыть, выбираем нужную папку и указываем, чтобы в папке были видны все типы файлов.
И выбираем наш текстовый файл.
Выскочит окно Мастер текстов (импорт). Здесь оставляем выбранный пункт с разделителями и кликаем Далее.
В следующем окне поставим ещё галочку пробел. В итоге Символами-разделителем будут знак табуляции и пробел.
Кликаем ещё раз Далее и Готово.
Наши данные вставятся, как нужно!
Число 8200 (размер свободного места) нужно запомнить или записать на черновике. Число 970 (количество файлов) нам в принципе не нужно при таком подходе решения.
Теперь удаляем первую строчку. Выделяем две ячейки в первой строчке, через контекстное меню мыши нажимаем Удалить. . Выбираем ячейки, со сдвигом вверх.
1. Найдём максимальное количество файлов.
Выделяем весь столбец A и сортируем его по возрастанию.
Теперь выделяем ячейки сверху мышкой, а справа в нижней части программы будет показываться сумма выделенных ячеек.
Мы должны выделить максимальное количество ячеек, но чтобы сумма не превышала число 8200.
Получается максимальное количество файлов, которое можно сохранить, равно 568.
2. Найдём максимальный размер файла при максимальном количестве файлов.
Если мы сохраним максимальное количество файлов, то у нас ещё останется свободное место 8200-8176=24, т.к. сумма выделенных ячеек равна 8176.
Мы можем заменить наибольший файл (последняя выделенная ячейка равная 29) ещё большим файлом, размер которого не превышает 24+29=53.
Если покрутим таблицу вниз, то найдём такой файл размером 50. Это и будет наибольший файл при максимальном количестве файлов.
Ответ:
568 | 50 |
Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.
Пример организации исходных данных во входном файле:
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем – для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Напишем программу на Python.
Переменная s - это сумма от первого до текущего элемента i. На каждом шаге вычисляется остаток от деления s на 43. И записывается в массив sum_ost эта сумма s для каждого остатка.
Тогда кандидатом для ответа будет цепочка, которая получается, если от цепочки с суммой s "отрезать" цепочку с суммой из массив sum_ost, которая соответствует текущему остатку (переменная ost).
В массив sum_ost для каждого остатка записывается сумма только один раз, т.к. нам нужна именно минимальная сумма для каждого остатка, чтобы кандидат для ответа был как можно больше.
В начале массив sum_ost инициализируется очень большим числом 1096594666. Это число больше, чем сумма всех элементов в файле. Оно было найдено до основного решения, с помощью простой программы.
В процессе решения мы ищем среди кандидатов для ответа цепочку с максимальной суммой. Делаем это стандартным образом: кто больше, то и победил. Мы инициализируем большими числом 1096594666 элементы массива sum_ost для того, чтобы условие нормально сработало, когда в массиве sum_ost ещё нет суммы для данного остатка.
Так же мы сохраняем индексы элементов в массив k, когда записываем суммы для различных остатков в массив sum_ost. Это делается для того, чтобы можно было вычислить длину цепочки.
Для случая, когда остаток равен 0, устанавливаем сумму в массиве sum_ost равной нулю, потому что кандидатом на ответ будет цепочка от самого первого до i-ого элемента. Это, можно сказать, исключительный случай. И чтобы правильно вычислялась длина цепочки, для случая, когда остаток равен нулю, индекс в массив k делаем равным -1.
Задание 14 № 10566
В электронную таблицу занесли данные о тестировании учеников по выбранным ими предметам.
A | B | C | D | |
---|---|---|---|---|
1 | округ | фамилия | предмет | балл |
2 | C | Ученик 1 | Физика | 240 |
3 | В | Ученик 2 | Физкультура | 782 |
4 | Ю | Ученик 3 | Биология | 361 |
5 | СВ | Ученик 4 | Обществознание | 377 |
В столбце A записан код округа, в котором учится ученик; в столбце B — фамилия, в столбце C — выбранный учеником предмет; в столбце D — тестовый балл. Всего в электронную таблицу были занесены данные по 1000 учеников.
Выполните задание.
Откройте файл с данной электронной таблицей. На основании данных, содержащихся в этой таблице, ответьте на два вопроса и выполните задание.
1. Определите, сколько учеников, которые проходили тестирование по информатике, набрали более 600 баллов. Ответ запишите в ячейку H2 таблицы.
2. Найдите средний тестовый балл учеников, которые проходили тестирование по информатике. Ответ запишите в ячейку H3 таблицы с точностью не менее двух знаков после запятой.
3. Постройте круговую диаграмму, отображающую соотношение числа участников из округов с кодами «В», «Зел» и «З». Левый верхний угол диаграммы разместите вблизи ячейки G6.
1. Запишем в ячейку E2 следующую формулу =ЕСЛИ(И(D2>600; C2="информатика");D2;0) и скопируем ее в диапазон E3:E1001. Применив операцию =ЕСЛИ(E2>0;1;0), получим столбец (F): с единицами и нулями. Далее, используем операцию =СУММ(F2:F1001). Получим количество учеников, которые проходили тестирование по информатике и набрали более 600 баллов. Таких 32 человека.
2. Для ответа на второй вопрос используем операцию «ЕСЛИ». Запишем в ячейку G2 следующее выражение: =ЕСЛИ(C2="информатика"; D2;0), в результате применения данной операции к диапазону ячеек G2:G1001, получим столбец, в котором записаны баллы только учеников, сдававших информатику. Сложив значения в ячейках, получим сумму баллов учеников: 39 371. Найдём количество учеников, сдававших информатику, с помощью команды =СЧЁТЕСЛИ(C2:C1001;"информатика"), получим 72. Разделив сумму баллов на количество учеников, получим: 546,8194 — искомый средний балл.
3. В ячейку J2 вставим формулу =СЧЁТЕСЛИ(A2:A1001; "В"), в ячейку J3 вставим формулу =СЧЁТЕСЛИ(A2:A1001; "Зел"), в ячейку J4 вставим формулу =СЧЁТЕСЛИ(A2:A1001; "З"). Теперь построим по полученным значениям круговую диаграмму, подпишем сектора.
Ответ: 1) 32; 2) 546,82.
Задание 14 № 10567
В электронную таблицу занесли данные о тестировании учеников. Ниже приведены первые пять строк таблицы:
A | B | C | D | |
---|---|---|---|---|
1 | округ | фамилия | предмет | балл |
2 | C | Ученик 1 | обществознание | 246 |
3 | В | Ученик 2 | немецкий язык | 530 |
4 | Ю | Ученик 3 | русский язык | 576 |
5 | СВ | Ученик 4 | обществознание | 304 |
В столбце А записан округ, в котором учится ученик; в столбце В — фамилия; в столбце С — любимый предмет; в столбце D — тестовый балл. Всего в электронную таблицу были занесены данные по 1000 ученикам.
Выполните задание.
Откройте файл с данной электронной таблицей. На основании данных, содержащихся в этой таблице, ответьте на два вопроса.
1. Сколько учеников в Восточном округе (В) выбрали в качестве любимого предмета информатику? Ответ на этот вопрос запишите в ячейку Н2 таблицы.
2. Каков средний тестовый балл у учеников Северного округа (С)? Ответ на этот вопрос запишите в ячейку НЗ таблицы с точностью не менее двух знаков после запятой.
3. Постройте круговую диаграмму, отображающую соотношение числа участников, сдающих информатику, русский язык и обществознание. Левый верхний угол диаграммы разместите вблизи ячейки G6.
1. Запишем в ячейку E2 следующую формулу =ЕСЛИ(A2="В";C2;0) и скопируем ее в диапазон E3:E1001. В ячейку столбца E будет записываться название предмета, если ученик из Восточного округа и «0», если это не так. Применив операцию =ЕСЛИ(E2="информатика";1;0), получим столбец (F): с единицами и нулями. Далее, используем операцию =СУММ(F2:F1001). Получим количество учеников, которые считают своим любимым предметом информатику. Таких 10 человек.
2. Для ответа на второй вопрос используем операцию «ЕСЛИ». Запишем в ячейку G2 следующее выражение: =ЕСЛИ(A2="С";D2;0), в результате применения данной операции к диапазону ячеек G2:G1001, получим столбец, в котором записаны баллы только учеников Северного округа. Сложив значения в ячейках, получим сумму баллов учеников: 56 737. Найдём количество учеников Северного округа с помощью команды =СЧЁТЕСЛИ(A2:A1001;"С"), получим 105. Разделив сумму баллов на количество учеников, получим: 540,352 — искомый средний балл.
3. В ячейку J2 вставим формулу =СЧЁТЕСЛИ(C2:C1001; "информатика"), в ячейку J3 вставим формулу =СЧЁТЕСЛИ(C2:C1001; "русский язык"), в ячейку J4 вставим формулу =СЧЁТЕСЛИ(C2:C1001; "обществознание"). Теперь построим по полученным значениям круговую диаграмму, подпишем сектора.
Ответ: 1) 10; 2) 540,35.
Задание 14 № 10568
В электронную таблицу занесли данные о тестировании учеников. Ниже приведены первые пять строк таблицы:
A | B | C | D | |
---|---|---|---|---|
1 | округ | фамилия | предмет | балл |
2 | C | Ученик 1 | обществознание | 246 |
3 | В | Ученик 2 | немецкий язык | 530 |
4 | Ю | Ученик 3 | русский язык | 576 |
5 | СВ | Ученик 4 | обществознание | 304 |
В столбце А записан округ, в котором учится ученик; в столбце В — фамилия; в столбце С — любимый предмет; в столбце D — тестовый балл. Всего в электронную таблицу были занесены данные по 1000 ученикам.
Выполните задание.
Откройте файл с данной электронной таблицей (расположение файла Вам сообщат организаторы экзамена). На основании данных, содержащихся в этой таблице, ответьте на два вопроса.
1. Сколько учеников в Северо-Восточном округе (СВ) выбрали в качестве любимого предмета математику? Ответ на этот вопрос запишите в ячейку Н2 таблицы.
2. Каков средний тестовый балл у учеников Южного округа (Ю)? Ответ на этот вопрос запишите в ячейку Н3 таблицы с точностью два знака после запятой.
3. Постройте круговую диаграмму, отображающую соотношение числа участников, сдающих информатику, немецкий язык и обществознание. Левый верхний угол диаграммы разместите вблизи ячейки G6.
1. Запишем в ячейку H2 следующую формулу =ЕСЛИ(A2="СВ";C2;0) и скопируем ее в диапазон H3:H1001. В таком случае, в ячейку столбца Н будет записываться название предмета, если ученик из Северо-Восточного округа и «0», если это не так. Применив операцию =ЕСЛИ(H2="математика";1;0), получим столбец(J) с единицами и нулями. Далее, используем операцию =СУММ(J2:J1001). Получим количество учеников, которые считают своим любимым предметом математику. Таких учеников 17.
2. Для ответа на второй вопрос используем операцию «ЕСЛИ». Запишем в ячейку E2 следующее выражение: =ЕСЛИ(A2="Ю";D2;0), в результате применения данной операции к диапазону ячеек Е2:Е1001, получим столбец, в котором записаны баллы только учеников Южного округа. Просуммировав значения в ячейках, получим сумму баллов учеников: 66 238. Далее посчитаем количество учеников Южного округа с помощью команды =СЧЁТЕСЛИ(A2:A1001;"Ю"), получим: 126. Разделив сумму баллов на количество учеников, получим: 525,70 — искомый средний балл.
3. В ячейку J2 вставим формулу =СЧЁТЕСЛИ(C2:C1001; "информатика"), в ячейку J3 вставим формулу =СЧЁТЕСЛИ(C2:C1001; "немецкий язык"), в ячейку J4 вставим формулу =СЧЁТЕСЛИ(C2:C1001; "обществознание"). Теперь построим по полученным значениям круговую диаграмму, подпишем сектора.
Ответ: 1) 17; 2) 525,70.
Задание 14 № 10569
В электронную таблицу занесли данные о тестировании учеников. Ниже приведены первые пять строк таблицы:
A | B | C | D | |
---|---|---|---|---|
1 | округ | фамилия | предмет | балл |
2 | C | Ученик 1 | обществознание | 246 |
3 | В | Ученик 2 | немецкий язык | 530 |
4 | Ю | Ученик 3 | русский язык | 576 |
5 | СВ | Ученик 4 | обществознание | 304 |
В столбце А записан округ, в котором учится ученик; в столбце В — фамилия; в столбце С — любимый предмет; в столбце D — тестовый балл. Всего в электронную таблицу были занесены данные по 1000 ученикам.
Выполните задание.
Откройте файл с данной электронной таблицей (расположение файла Вам сообщат организаторы экзамена). На основании данных, содержащихся в этой таблице, ответьте на два вопроса.
1. Сколько учеников в Северо-Западном округе (СЗ) выбрали в качестве любимого предмета русский язык? Ответ на этот вопрос запишите в ячейку Н2 таблицы.
2. Каков средний тестовый балл у учеников Западного округа (3)? Ответ на этот вопрос запишите в ячейку Н3 таблицы с точностью не менее двух знаков после запятой.
3. Постройте круговую диаграмму, отображающую соотношение числа участников, сдающих химию, немецкий язык и математику. Левый верхний угол диаграммы разместите вблизи ячейки G6.
1. Запишем в ячейку H2 следующую формулу =ЕСЛИ(A2="СЗ";C2;0) и скопируем ее в диапазон H3:H1001. В таком случае, в ячейку столбца Н будет записываться название предмета, если ученик из Северо-Западного округа (СЗ) и «0», если это не так. Применив операцию =ЕСЛИ(H2="русский язык";1;0), получим столбец(J) с единицами и нулями. Далее, используем операцию =СУММ(J2:J1001). Получим количество учеников, которые считают своим любимым предметом русский язык. Таких 11 человек.
2. Для ответа на второй вопрос используем операцию «ЕСЛИ». Запишем в ячейку E2 следующее выражение: =ЕСЛИ(A2="З";D2;0), в результате применения данной операции к диапазону ячеек Е2:Е1001, получим столбец, в котором записаны баллы только учеников Западного округа. Просуммировав значения в ячейках, получим сумму баллов учеников: 57 807. Далее посчитаем количество учеников Западного округа с помощью команды =СЧЁТЕСЛИ(A2:A1001;"З"), получим: 108. Разделив сумму баллов на количество учеников, получим: 535,25 — искомый средний балл.
3. В ячейку J2 вставим формулу =СЧЁТЕСЛИ(C2:C1001; "химия"), в ячейку J3 вставим формулу =СЧЁТЕСЛИ(C2:C1001; "немецкий язык"), в ячейку J4 вставим формулу =СЧЁТЕСЛИ(C2:C1001; "математика"). Теперь построим по полученным значениям круговую диаграмму, подпишем сектора.
Читайте также: