Как подготовиться к 27-му заданию ЕГЭ на Python?

Question

[Eli_sh]

В принципе обращаюсь к тем кто сдавал/сдает ЕГЭ по информатике. Пишу все на Python и столкнулась с тем что велика разница в сложности между заданием 27 и всеми остальными. Готовлюсь по справочнику Полякова у него есть ответы к 27-му заданию на Питоне, но выглядят они мудрено и нет комментариев какая строка что делает. Прошла курсы по Python на Stepik и GeekBrains, все так же тяжело расшифровывать его решения.
Какими источниками вы пользовались для подготовки к этому заданию: статьи, справочники и т.д., корме Полякова?

Comments

[Зелимхан Бельтоев]

Задание покажите: 90% аудитории ЕГЭ не сдавало или сдавало лет 5 назад. Так что сейчас вопрос слишком общий

[Александр]

Мне вот лень искать это задание 27, справочник Полякова.

Answer 1

[timurkin]

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

Answer 2

[Владимир Олохтонов]

infbu.ru/catalog/1027

На примере этого задания:
Все полученные данные можно представить в виде списка неотрицательных целых чисел. От вас требуется пройти окошком ширины 5 этот список и посчитать сумму в каждом окошке.

Например:
Первое окно - это элементы с 0 по 4, второе - с 1 по 5, третье - с 2 по 6 и так далее вплоть до окна с (n-4) по n, в каждом по 5 элементов.

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

Comments

[devalone]

Сдвигать массив на каждой итерации - хорошее решение?(это я про решение по ссылке) А если "окно" станет шире пяти элементов? Тогда лучше использовать очередь, с одной стороны забрал элемент, с другой вставил. А я решил вот так: pastebin.com/6AKxC24L

[Владимир Олохтонов]

devalone: вы не сдвигаете массив, просто инкрементируете индексы, стоимость операции - константа. Решение этой задачи за линейной время асимптотически оптимально, остальное - микрооптимизации, первой из которых может быть подсчет массива частичных сумм, чтобы не считать их несколько раз (тогда сумма элементов в окне считается за одно действие, как разность двух частичных сумм).

[Владимир Олохтонов]

devalone: Не сразу понял о чём вы. То решение о котором вы говорите используется для экономии памяти. Чтобы не считывать в память сразу все элементы (1440*4~5Kb), автор предлагает проходить по этим числам тем же самым окном ширины 5, но считывать в память только числа, входящие в текущее окно. С точки зрения экономии памяти - хорошее решение, более того, стандартное для поточных задач.

Если вам интересно с такими вещами более подробно разобраться - прорешайте (а не прочитайте) Кормена "Алгоритмы. Вводный курс.", потом можете почитать его же книжку "Алгоритмы. Построение и анализ", но это тот еще талмуд :) Главное, что нужно вынести - асимптотики выполнения операций над структурами данных.

[devalone]

Владимир Олохтонов:
> вы не сдвигаете массив, просто инкрементируете индексы
да, я в курсе, что делает мой код)
Я говорил про решение по ссылке, которую вы в посте предоставили, оно похоже на моё, только там сдвигается массив а этого можно избежать.

[Владимир Олохтонов]

devalone: я использовал ссылку просто как запись задания :) Конечно, если можно не копировать части массива лишний раз, лучше этого не делать.