Самые сложные задачи по информатике егэ

Пройти тестирование по 10 заданиям
Пройти тестирование по всем заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

Пройти тестирование по этим заданиям

Сложные задания ЕГЭ

Колледж экономических международных связей

Для выпускников 9 и 11 классов.

Высшее образование онлайн

Федеральный проект дистанционного образования.

Я б в нефтяники пошел!

Пройди тест, узнай свою будущую профессию и как её получить.

Технологии будущего

Вдохновитесь идеей стать крутым инженером, чтобы изменить мир

Студенческие проекты

Студенты МосПолитеха рассказывают о своих изобретениях

Химия и биотехнологии в РТУ МИРЭА

120 лет опыта подготовки

Международный колледж искусств и коммуникаций

МКИК — современный колледж

Английский язык

Совместно с экспертами Wall Street English мы решили рассказать об английском языке так, чтобы его захотелось выучить.

15 правил безопасного поведения в интернете

Простые, но важные правила безопасного поведения в Сети.

Олимпиады для школьников

Перечень, календарь, уровни, льготы.

Первый экономический

Рассказываем о том, чем живёт и как устроен РЭУ имени Г.В. Плеханова.

Билет в Голландию

Участвуй в конкурсе и выиграй поездку в Голландию на обучение в одной из летних школ Университета Радбауд.

Цифровые герои

Они создают интернет-сервисы, социальные сети, игры и приложения, которыми ежедневно пользуются миллионы людей во всём мире.

Работа будущего

Как новые технологии, научные открытия и инновации изменят ландшафт на рынке труда в ближайшие 20-30 лет

Профессии мечты

Совместно с центром онлайн-обучения Фоксфорд мы решили узнать у школьников, кем они мечтают стать и куда планируют поступать.

Экономическое образование

О том, что собой представляет современная экономика, и какие карьерные перспективы открываются перед будущими экономистами.

Гуманитарная сфера

Разговариваем с экспертами о важности гуманитарного образования и областях его применения на практике.

Молодые инженеры

Инженерные специальности становятся всё более востребованными и перспективными.

Табель о рангах

Что такое гражданская служба, кто такие госслужащие и какое образование является хорошим стартом для будущих чиновников.

Карьера в нефтехимии

Нефтехимия — это инновации, реальное производство продукции, которая есть в каждом доме.

Автор статьи — репетитор-профессионал Лада Борисовна Есакова.

Поговорим о задаче 27 (С4) на ЕГЭ по информатике. Она оценивается следующим образом:

— 4 балла, если написанная программа работает верно, она эффективна и содержит до трех синтаксических ошибок;
— 3 балла, если написанная программа работает верно, она не эффективна по памяти (но эффективна по времени), содержит не более пяти синтаксических ошибок и не более одной смысловой ошибки;
— 2 балла, если написанная программа работает верно, но она неэффективна, содержит не более семи синтаксических ошибок и не более двух смысловых ошибок;
— 1 балл, если программа не написана или работает неверно, однако алгоритм решения описан правильно.

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

Давайте выделим основные моменты в решении этой самой сложной задачи.

к оглавлению ▴

1. Правильный алгоритм

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

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

к оглавлению ▴

2. Эффективность.

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

Эффективность в данном смысле – это умение экономно расходовать основные ресурсы: память компьютера и время.

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

к оглавлению ▴

2.1. Эффективность по времени.

Наиболее ценным ресурсом в этой задаче считается время. Эффективность по времени расценивается «дороже», чем эффективность по памяти. Как же написать эффективную по времени программу?

Обозначим время выполнения программы T. Допустим, нам нужно последовательно просмотреть в цикле N элементов массива. Тогда время выполнения программы будет прямо пропорционально количеству элементов (T~N).

Если же для каждого из N элементов нам нужно заново просмотреть весь массив (цикл в цикле), то время будет пропорционально квадрату количества элементов.

Эта программа менее эффективна, чем первая.
Очевидно, что третий вложенный цикл даст нам уменьшение эффективности еще в N раз.

Таким образом, нужно стараться избегать вложенных циклов. Это не всегда возможно. Любая сортировка (например, метод пузырька) обязывает нас использовать цикл в цикле.

к оглавлению ▴

2.2. Эффективность по памяти.

Все, что выполняет наша программа, происходит в памяти компьютера.
Объявляя переменные, мы резервируем ячейки памяти (переменная типа Integer занимает в классическом Паскале 2 байта, переменная типа Real – 6 байт).
Записывая введенные данные в массив или переменные, мы используем память.

Поэтому основные приемы экономии памяти:
— Правильно выбирать тип переменной;
— При возможности не сохранять вводимые данные в массив или переменные, а анализировать сразу при вводе;
— Экономно использовать переменные (если возможно, использовать одну переменную для разных целей).
И опять же, позаботьтесь о проверяющем. После написания программы сделайте анализ эффективности. Объясните, почему вы выбрали такие типы переменных. Укажите, где вы экономно использовали одну и ту же переменную в разных целях. Возможно, Вы сознательно уменьшили эффективность по памяти для увеличения эффективности по времени.

к оглавлению ▴

3. Культура оформления программного кода.

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

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

Настоятельно рекомендую выполнять следующие правила, которые не добавят Вам лишний балл, но позитивно настроят проверяющего и застрахуют от возможной недооценки вашей работы:
— Используйте имена переменных, указывающие на их назначение. Например, для обозначения переменной, хранящей максимальную сумму можно использовать наименование maxsum, для массива с номерами школ – schoolnum. Только не переусердствуйте! Под счетчики достаточно ввести переменные i, j…

— Форматируйте текст отступами, обозначая начало-конец программных блоков. Такое форматирование избавит Вас от потери закрывающих скобок и упростит чтение текста;

— Используйте комментарии, коротко описывающие основной смысл происходящего.

Выполнив эти несложные требования, Вы гарантированно получите высший балл за самую сложную задачу ЕГЭ по информатике!

Подготовка к ЕГЭ по информатике

Как устроен ЕГЭ по информатике в 2023 году

Экзамен по информатике длится 3 часа 55 минут (235 минут). Всего на ЕГЭ школьник должен будет справиться с 27 заданиями, 11 из которых нужно будет выполнять с помощью специального ПО.

Будьте внимательны: в ЕГЭ по информатике нет привычного разделения на 1-ю и 2-ю части. Ответы на все задания нужно будет записать в одном формате — кратком. Но при этом работа с самого начала экзамена будет проходить за компьютером.

Также задания делятся по уровням сложности:

• базовый — 11 заданий;

• повышенный — 11 заданий;

• высокий — 5 заданий.

Как изменится экзамен по сравнению с 2022 годом

В отличие от ОГЭ, в структуре ЕГЭ по информатике будущих выпускников ждут небольшие перемены:

• Задание № 6 теперь будет проверять, умеет ли школьник анализировать алгоритм для конкретного исполнителя, а также определять возможные результаты этих алгоритмов.

• Задание № 22 посвятят параллельному программированию, технологиям организации многопоточных вычислений. Это задание нужно будет выполнять с помощью файла с информацией, необходимой для решения задачи.

• К списку языков для решения задач по программированию добавили C# и Java.

Учитывайте эти изменения с 2022 года, когда будете составлять план по подготовке к ЕГЭ по информатике.

Как оценивают готовые работы на ЕГЭ по информатике

Теперь давайте разберёмся, какие задания принесут вам больше баллов, а какие — меньше. Это поможет, если у вас мало времени, и нужно планировать подготовку к ЕГЭ по информатике с нуля.

Если вы верно решите задания № 1–25, то получите по 1 баллу за каждое. При этом правильным ответом будут считать тот, который записан в нужной форме по инструкции в условии. Ответ должен полностью совпадать с эталоном.

Задания № 26 и 27 могут принести вам по 2 балла. Условия те же, что и для № 1–25, — полное совпадение с эталоном. Если же числа перепутаны местами или верное число есть только в одной из ячеек таблицы, за такой ответ вы получите 1 балл. Во всех остальных случаях его оценят в 0 баллов.

Сколько баллов набрать, чтобы получить 3, 4 и 5 на ЕГЭ по информатике

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

Будьте внимательны: в таблице ниже мы привели только примерный перевод тестовых и первичных баллов в оценку по пятибалльной шкале. Официально её отменили и больше не используют. Но если вам так проще оценить свои знания, воспользуйтесь таблицей ниже.

5 полезных советов, как подготовиться к ЕГЭ по информатике

Теперь поговорим о том, что поможет вам как можно лучше сдать экзамен. В этом разделе мы собрали 5 советов от преподавателей Skysmart, которые подскажут, с чего начать подготовку к ЕГЭ по информатике. Пользуйтесь ими, и ваши шансы на высокие баллы вырастут.

Совет № 1. Начинайте готовиться заранее

К занятиям лучше приступать до 11 класса, ещё в 10-ом. Тем более, если речь идёт о самостоятельной подготовке к ЕГЭ по информатике с нуля. Так у вас будет больше времени, чтобы охватить все нужные темы. А если вы успеете повторить всё, можно будет направить остаток времени на практику. Она всегда полезна.

Помните: чем больше материала вам нужно будет освоить в короткий срок, тем больше шансов что-то упустить. А ещё — это большой стресс. И он может повлиять на результаты не только ЕГЭ по информатике, но и других экзаменов в 11 классе. Будьте умнее — грамотно распределяйте время. И тогда ваши усилия принесут плоды.

Совет № 2. Сочетайте разные методы подготовки

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

Но самоподготовка будет ещё полезнее, если сочетать её с другими методами. Не пропускайте уроки информатики в школе — преподаватель может рассказать много важных деталей. Также подумайте о дополнительных занятиях. Например, на курсе подготовки к ЕГЭ по информатике в Skysmart наши учителя расскажут вам всё, что нужно знать об экзамене, и помогут подготовиться по индивидуальному плану. Даже в сжатые сроки, если будет нужно.

Совет № 3. Не готовьтесь «вслепую»

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

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

Второй шаг — оценить время на подготовку. Чем больше месяцев до экзамена, тем свободнее будет ваш график и тем больше вы успеете освоить. И наоборот — если осталось всего полгода или меньше, готовиться нужно будет интенсивно.

Третий шаг — составить план подготовки к ЕГЭ по информатике. У вас уже есть все нужные переменные: темы для изучения, объём практики и срок. Теперь нужно распределить работу по неделям. Не забывайте чередовать методы подготовки — так будет легче усваивать полезную информацию. И обязательно оставьте 1–2 дня для выходных. Отдыхать — это важно.

Совет № 4. Занимайтесь программированием

Как видно из спецификации ЕГЭ по информатике, 50% заданий экзамена связаны с программированием. Причём в 10 и 11 классах у ученика есть чуть больше вариантов для выбора языка, чем в 9-м. Так, школьник может решать задачи с помощью:

• КуМир;

• C#;

• C++;

• Pascal;

• Java;

• Python.

Обратите внимание: не нужно учить все эти языки. Достаточно выбрать только один и освоить его на базовом уровне. Это ваш ключ к решению всех задач на программирование в ЕГЭ по информатике и высоким баллам.

Какой конкретно язык выбрать — решать только вам. Но если вы колеблетесь с решением, мы кратко расскажем о каждом из них.

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

C++ — перспективный, но сложный язык программирования. У него не самый дружелюбный синтаксис, а потому мы не советуем учить его для ЕГЭ. Выбирайте его только в том случае, если уже знаете более лёгкие ЯП, например Python.

C# — более простой «брат» Java. По уровню сложности находится между ним и Python, причём он не менее перспективный. C# считают языком программирования для начинающих, поэтому в 11 классе уже можно начать изучать его. В т. ч. — и для решения ЕГЭ.

Pascal — лёгкий, но уже бесполезный в 2023 году язык программирования. Да, он поможет вам справиться с заданиями, однако больше нигде не пригодится. Как и в случае с КуМир, выбирайте его тогда, когда не хотите изучать код после школы.

Java — один из самых популярных языков программирования, который открывает неплохие профессиональные перспективы. По простоте освоения он ближе к среднему уровню, и начать знакомиться с ним можно уже в 11 классе. Хотя, скорее всего, знакомство пройдёт не без сложностей. Но если вам интересно программирование, вы справитесь!

Python — один из самых лёгких и перспективных языков. Именно с него программисты чаще всего начинают свой путь. Но для него, как и для всех ЯП, кроме КуМир, нужен английский язык, а потому придётся подтянуть его уровень. Выбирайте Python, если хотите дальше погружаться в IT, но нет желания кодить на C++.

Совет № 5. Пользуйтесь ресурсами для подготовки к ЕГЭ по информатике

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

Как именно строить план и какую цель выбрать — решать только вам. Но помните, что лучшая подготовка к ЕГЭ по информатике — это та, которая учитывает все ваши данные. Поэтому важно планировать её с опытным преподавателем. На курсе подготовки к ЕГЭ по информатике в Skysmart мы поможем найти слабые места в ваших знаниях и разобрать самые сложные темы. А ещё — научим заполнять бланки, расскажем о частых ошибках учеников и познакомим с ПО, который встретится на экзамене. Начните с вводного занятия — это бесплатно!

Как пройдёт ЕГЭ по информатике в 2023 году

Экзамен в 2023 году будет состоять из 27 заданий разных уровней сложности: базового (11), повышенного (11), высокого (5). На решение дадут 235 минут. Громов рекомендует распределить их следующим образом:

• Первая часть состоит из 23 вопросов с коротким ответом. Лучше выделить на неё не более 90 минут. 

• Вторая часть состоит из четырёх заданий, и на каждое нужно дать развёрнутый ответ. Эта часть самая трудоёмкая – на неё лучше потратить около 120 минут.

• Оставшееся время можно оставить на проверку и возвращение к ответам, в которых вы сомневаетесь.

Тематические разделы экзамена:

• Теория алгоритмов и программирование.
• Математические расчеты в информатике.
• Моделирование и информационные процессы.
• Работы с таблицами и базами данных.
• Углублённое программирование и обработка числовых последовательностей.
• Алгебра логики и теория игр.

Критерии оценивания. Задания первой части (1–25) оцениваются в один первичный балл. За правильные ответы на задания 26 и 27 даётся два первичных балла. Максимум — 29 первичных баллов. Они же равны 100 баллам ЕГЭ.

Что изменилось в ЕГЭ по информатике в 2023 году

Кардинально изменились два задания: 6 и 22. Раньше нужно было просто читать программы, а теперь учащиеся должны показать знания многопоточного программирования и аналитики.

Пример задания 6, fipi.ru

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

Пример задания 22, fipi.ru

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

Онлайн-курсы

Запишись на онлайн-курсы по информатике и сдай ЕГЭ на 100 баллов

Узнать подробнее

Как справиться с самыми сложными заданиями и темами

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

Больше всего трудностей у школьников вызывают темы, связанные с глубоким знанием программирования (задания 22–27). Самая сложная задача – 27, её решают лишь 60–70% учеников, потому что она не типовая. Каждый год сдающих ждёт эксклюзив от создателей ЕГЭ, который вряд ли встретится при подготовке.

Вот несколько лайфхаков, которые помогут справиться с трудностями:

• уделите особое внимание задачам 9, 11, 12, 14, 15, 16, 23, 24, 25, 26, 27, ведь именно с ними в прошлом году возникали трудности (даже у отличников);

• в задании 27 иногда лучше написать неэффективную программу и получить один первичный балл, чем допустить смысловую ошибку (не вычислительную, а в подходе к решению) и получить ноль; 

• выучите наизусть степени числа 2, чтобы упростить счёт;

• запомните стандартные алгоритмы в программировании (проверка чисел на простоту, делимость, перебор потока чисел), чтобы уверенно владеть процессами и не тратить время;

• тренируйтесь на демоверсии станции КЕГЭ (именно на ней будет проходить экзамен), решите на ней как можно больше вариантов;

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

Хватит ли школьных знаний для сдачи ЕГЭ по информатике

Школы бывают разные, но, как правило, без дополнительной подготовки хватает знаний, чтобы набрать 40–50 баллов. Это связано с тем, что на уроках отводится недостаточно времени сложным задачам на программирование. Можно разбираться в них самому с помощью книг и YouTube, но без серьёзной базы знания будут казаться разрозненными и непонятными. Намного эффективнее и проще вникать в предмет с репетитором или на специальных курсах.

При подготовке школьники изучают языки программирования (С++, Java, C#, Pascal, Python), работают с инструментами анализа данных и даже пишут собственный код. Кроме того, учащиеся осваивают теорию игр и работу с таблицами Excel.

Бонус в том, что весь этот набор знаний и навыков нужен не только для того, чтобы успешно сдать ЕГЭ по информатике. Он может послужить хорошим стартом для обучения IT-профессии.

Как готовиться к ЕГЭ по информатике

Александр Громов даёт следующие рекомендации:

Сколько баллов нужно набрать на ЕГЭ по информатике, чтобы поступить

Согласно приказу Минобрнауки, минимальный балл ЕГЭ по информатике в 2023 году — 44. С меньшим показателем поступить не получится даже на платное обучение.

Если претендуете на бюджет в престижном вузе, боритесь за каждый балл. Так, на факультете информатики в Бауманке в 2022 году проходные баллы были — 257–291 за три экзамена (русский язык, математика, информатика или физика).

На факультете ВМК МГУ в 2022 году проходили на бюджет абитуриенты с результатами 402–405 баллов за пять экзаменов (русский язык, математика, информатика, физика, дополнительный внутренний экзамен по математике). Причём минимум по информатике в МГУ — 65 баллов, даже на договорной основе.

В МФТИ в 2022 году требовалось набрать 245–294 балла за три экзамена, 378 баллов за четыре экзамена.

Онлайн-курсы

Запишись на онлайн-курсы по информатике и сдай ЕГЭ на 100 баллов

Занятия проходят дважды в неделю по 1,5 часа. Вы получите полноценную подготовку с написанием пробников, а также поддержку наставников, психолога и тьютора.

Узнать подробнее

МЕТОДИКА РЕШЕНИЯ ЗАДАЧ ЕГЭ ВЫСОКОГО УРОВНЯ 27 (С4)

Автор: учитель информатики Гришенкова М.А.

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

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

Характеристика	Значение
Что проверяется	Умение создавать собственные программы (30–50 строк) для решения задач средней сложности
Требования к проверяемым элементам содержания	Основные этапы разработки программ. Разбиение задачи на подзадачи.
Проверяемые требования к уровню подготовки	Создавать программы на языке программирования по их описанию
Уровень сложности	Высокий
Максимальный балл	4
Примерное время выполнения	55 мин

Заметим, что эта задача
имеет самый высокий балл, и на ее выполнение разработчики задания выделают
практически четверть общего времени, отводимого на
экзамен.

Проанализируем результаты решения этой задачи
в 2015-2016 учебном году. Процент выполнения этой задачи представлен в
следующей таблице:

Полученные баллы	1	2	3-4	>0
Процент участников	7%	3,7%	5,7%	16,2%

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

Итак, как же научиться решать эти задания?

Перечислим необходимые для этого знания и
умения, базовые алгоритмические задачи и методы:

•     
понятие сложности алгоритма;

•     
объявление, ввод массива;

•     
записи (структуры данных);

•     
работа со строками и символьными переменными;

•     
нахождение максимума и минимума в массиве, в 
последовательности;

•     
нахождение суммы, произведения элементов массива, последовательности;

•     
свойства кратности, делимости сумм и произведений
чисел;

•     
сдвиг элементов массива;

•     
использование вложенных циклов для полного
перебора.

В качестве особенностей решения задачи можно
выделить следующие:

•     
большое количество возможных вариаций задач и их
формулировок;

•     
от учащегося требуются хорошие практически навыки
программирования;

•     
требуется знать свойства делимости;

•     
большое количество приемов и способов решения,
которые трудно формализовать;

•     
организация оптимального решения требует
творческого подхода и тщательного анализа задачи.

Перед тем как говорить о решении задач,
вспомним необходимые понятия.

Сложность алгоритмов

Сложность алгоритма – это количественная характеристика ресурсов,
необходимых алгоритму для работы (успешного решения задачи).

Основные ресурсы:

•     
время (временнáя
сложность) и

•     
объем памяти (ёмкостная
сложность).

Наиболее важной характеристикой является время.

Сложность задачи может быть разной для разных
входных данных (экземпляров задачи).

Различают сложность в худшем случае и сложность
в среднем.

В теории сложности чаще оперируют понятием
сложности в худшем случае.

Обычно оценивают порядок роста сложности при n®¥: T = O(f(n)).

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

•     
Именно порядок роста сложности ограничивает размер
решаемых задач.

Например, если сравнивать порядок зависимости
времени решения задачи, можно привести данные,представленные в таблице:

Выделим основные типы и темы заданий:

      
I.           
Обработка данных, вводимых в виде символьных строк
или последовательности чисел.

    II.           
Проверка контрольного значения среди
последовательности чисел.

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

IV.           
Выбор подмножества элементов с определенным набором
свойств.

   V.           
Выбор одного значения из пары с нахождением суммы
или произведения с определёнными свойствами.

Рассмотрим
каждый тип задачи отдельно.

Возможная формулировка задания (тип I)

 На вход программе подаются сведения о номерах
школ учащихся, участвовавших в олимпиаде. В первой строке сообщается количество
учащихся N, каждая из следующих N строк имеет формат:

<Фамилия><Инициалы><номер школы>

где <Фамилия> – строка, состоящая не
более чем из 20 символов, <Инициалы> – строка, состоящая из 4-х символов
(буква, точка, буква, точка), <номер школы> – не более чем двузначный
номер.<Фамилия> и <Инициалы>, а также <Инициалы> и <номер
школы> разделены одним пробелом. Пример входной строки:

Иванов П.С. 57

Требуется написать
как можно более эффективную программу (укажите используемую версию языка
программирования, например, BorlandPascal 7.0), которая будет выводить на экран
информацию, из какой школы было меньше всего участников (таких школ может быть
несколько). При этом необходимо вывести информацию только по школам, пославшим
хотя бы одного участника. Следует учитывать, что N>=1000.

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

Необходимые знания
и умения:

1.     Решение задачи разбиения строки на подстроки по пробелам.

Функцииипроцедуры
(Pascal) : pos, copy, delete, length, insert.

2.     Преобразование строки в число, в цифры.

Функцииипроцедуры
(Pascal) :val, StrToInt (Delphi).

3.     Работа с символами. Функции (Pascal): ord, chr.

4.     Работа с записями (структурами).

TypeRec=record

         {поля
записи}

F:string[20]; {фамилия}

         IO: string[4]; {инициалы}

         num: integer;{номершколы}

end;

Подробно
останавливаться не будем из-за неактуальности.

Возможная формулировка задания (тип II)

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

1) R — сумма двух различных переданных
элементов последовательности («различные» означает, что нельзя просто удваивать
переданные числа, суммы различных, но равных по величине элементов
допускаются);

2) R — нечётное число.

Если чисел, соответствующих приведённым
условиям, нет, считается, что R = –1. В результате помех при передаче как сами
числа, так и контрольное значение могут быть искажены.

Напишите эффективную, в том числе по
используемой памяти, программу (укажите используемую версию языка
программирования, например, FreePascal 2.6.4), которая будет проверять
правильность контрольного значения.

Перед текстом программы кратко опишите
используемый Вами алгоритм решения.

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

Пример входных данных:

6

100

8

33

45

19

90

145

Пример выходных данных:

145

Рассмотрим
неоптимальное решение полным перебором, которое оценивается в 2 балла.

Организация полного перебора

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

Текстпрограммы (авторский).

Vara:array [1..10000]
ofinteger;

n, i, j: integer;

Rmin, R : integer;

Begin

readln(n);

for i:=1 to n do

readln(a[i]);

Rmin:=2001;

for i:=1 to n-1 do

for   j:=i+1 to n do

begin

                            R:=a[i]+a[j];

                            {проверка условия
контрольного значения}

if(R<Rmin)and(R mod
3=0)then     Rmin:=R;

                   end;

ifRmin=2001 then
Rmin:=-1; 

writeln(Rmin);

End.

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

Например, число
2001 взято как максимально возможная сумма двух элементов плюс 1, т.е. это
невозможное значение для суммы двух чисел, которое будет заведомо больше чем
реальная сумма. Поэтому, если после обработки данных число осталось прежним,
это говорит о том, что искомой пары так и не было найдено. Условие подчеркнуто,
потому как в задаче можно искать минимум, а можно максимум, в данной ситуации
еще требовалось, чтобы это число было кратно трем, в другой задаче может быть
другое условие, поэтому именно здесь надо будет поменять данные.

Как видно, для
данного типа задач можно подготовить шаблонное неоптимальное решение на 2
балла.

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

Оптимальное решение.

Если не хранить все
числа, то тогда во время ввода данных какие именно хранить?

ИДЕЯ: Хранить в
памяти не все введенные ранее числа, а только те, которые «лучше» остальных.

Чтобы сумма была
меньше, нужно брать меньшие числа, достаточно хранить только минимальные,
удовлетворяющие условию.

Сколько таких
чисел хранить и какие должны быть условия?

По условию сумма
должна быть наименьшей и кратной трем. Хранить только наименьшее нет смысла,
потому как с другим наименьшим оно может не дать нужного остатка при делении на
3.

Вывод: следует
хранить все минимальные числа, имеющие разные остатки при делении на 3.

Попытаемся словесно
сформулировать алгоритм решения.Назовем парным остатком такой остаток, который
в сумме с текущим будет делиться на 3.

Алгоритм оптимального решения

1.    
Считываем
количество чисел n.

2.    
Инициализируем
переменные.

3.    
Цикл из  n
итераций

3.1.
Чтение
очередного числа a.

3.2.
Вычисление
его остатка от деления на 3.

3.3.
Выбираем
число, остаток от деления на 3 от которого  в сумме с остатком деления  a
на 3 кратен 3 (парный).

3.4.
Если их
сумма меньше контрольного значения, запоминаем ее как контрольное значение.

3.5.
Если
число a меньше минимального, имеющего тот же остаток от деления
на 3, запоминаем его.

4.    
Если
контрольное число не изменилось, запоминаем в него 1.

5.    
Вывод
контрольного значения.

Программа для оптимального решения

VarR, Rmin: integer;

         n, a, I,m1,m2:integer;             

b :array[0..2] ofinteger; {массив, хранящийминимальные значения с разными остатками при делении
на 3.}

Begin

         Rmin:=2001;

         fori:=0 to 2 dob[i]:=1001; // заполняем
массив «невозможными» числами

         readln(n);

         for i:=1 to n do

         begin

               readln(a);

               m1:=(amod 3); //смотрим остаток от деления на 3

m2:=( 3-m1)mod 3;//смотрим
парный остаток от деления на 3

               ifb[m2]<>1001 then

               beginR:=a+b[m3]; {читаемсумму текущего
элемента с минимальным, имеющим парный остаток}

                            if
R<Rmin then

                                      Rmin:=R;

               end;

{проверяем, не является ли текущий элемент
лучше предыдущего, имеющего такой же остаток }

               ifa<b[m1] then

                   b[m1]:=a;

         end;

ifRmin=2001 thenRmin:=-1;  //еслисуммане нашлась такая

writeln(Rmin);

End.

Как мы видим, что
алгоритм сложнее, но, тем не менее, тоже может быть формализован.

Возможная формулировка задания (тип III)

Для заданной последовательности
неотрицательных целых чисел необходимо найти минимальную сумму двух её
элементов, номера которых различаются не менее чем на 4. Значение каждого
элемента последовательности не превышает 1000. Количество элементов
последовательности не превышает 10000.

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

Задача Б (4 балла). Напишите программу для
решения поставленной задачи, которая будет эффективна как по времени, так и по
памяти (или хотя бы по одной из этиххарактеристик).

Программа считается эффективной по времени,
если время работы программы пропорционально количеству элементов
последовательности N, т.е. при увеличении N в k раз время работы программы
должно увеличиваться не более чем в k раз. Программа считается эффективной по
памяти, если размер памяти, использованной в программе для хранения данных, не
зависит от числа N и не превышает 1 килобайта.

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

Решение задачи А (не оптимальное)

Полный перебор похож на решение предыдущей задачи,
только нужно брать не соседние пары, а через 4 элемента.

Var a:array [1..10000] of integer;

n, i, j: integer;

Rmin, R : integer;

Begin

readln(n);

for i:=1 to n
do

readln(a[i]);

Rmin:=2001;

for i:=1 to n-4 do

for   j:=i+4 to n
do

begin

                            R:=a[i]+a[j];

                            if (R<Rmin)
then  {проверка условия контрольного значения}

                            Rmin:=R;

                   end;

writeln(Rmin);

End.

Как и прошлый раз,
здесь подчеркнуты те части, которые могут модифицироваться в зависимости от
условия задачи.

Оптимальное решение

Намного интереснее
найти оптимальное решение. Как всегда нужно сформулировать идею.

Рассмотрим
следующую последовательность:

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

Если нельзя
хранить все введенные ранее числа, то сколько чисел хранить в памяти и какие?

Во-первых,
необходимо хранить числа — «кандидаты» в лучшие для составления с новым
полученным числом контрольного значения. Эти числа были получены как минимум за
4 (согласно условию задачи) числа дотекущего. В текущем примере это только
число 4, которое минимально из всех предыдущих чисел.

Во-вторых,
необходимо хранить предпоследние 3 числа, которые пока не могут быть
использованы для формирования контрольного значения, но могут пригодиться для
последующих чисел. В данном случае мы видим, что в красной зоне есть числа 3 и
1, которые меньше 4, и для будущих чисел могут составить лучше пару, но пока
еще использоваться не могут.

Внимание: если
условие для контрольного значения сложное, «кандидатов» может быть несколько,
как в предыдущей задаче.

Сформулируем
алгоритм решения.

Алгоритмрешениязадачи Б

1.    
Считываем
количество чисел n.

2.    
Инициализация
переменных, считываем первое число, сохраняем как лучшее.

3.    
Считываем
3 числа, запоминаем в массив.

4.    
Цикл из  n-4 итераций

4.1.
Чтение
очередного числа a.

4.2.
 Складываем
с лучшим. Если их сумма меньше контрольного значения, запоминаем ее как
контрольное значение.

4.3.
 Сравниваем
первый элемент массива и лучшее, запоминаем из них лучшее.

4.4.
 Сдвигаем
влево на 1 элементы массива.

4.5.
 Запоминаем
a в последний элемент массива.

5.    
Вывод
контрольного значения.

Программа для решения задачи Б

Constdelta=4; {минимальный интервал}

VarR :integer;
{минимальная сумма}

         n, a, m:integer;      {количество
чисел, очередное значение, лучшее}

b :array[1..delta-1] ofinteger;
{массив промежуточных значений}

Begin

         R:=2001;

         readln(n);

         readln(m); {читаем первое, считаем его  «лучшим»}

{ Считываем 3
числа, запоминаем в массив }

         for i:=1 to delta-1 do
readln(b[i]);  

         for i:= delta+1 to n do

         begin { Чтение очередного числа a}

                   readln(a);

{Складываем с лучшим.Если их сумма меньше контрольного значения,
запоминаем ее как контрольное значение.}

                   If  (m+a)<R then
R:=a+m;      

{Сравниваем
первый элемент массива и лучшее, запоминаем из них лучшее}

                   if b[1]<m then m:=b[1];

                   {Сдвигаем влево на 1
элементы массива}

                   for j:=1 to delta-2
do b[j]:=b[j+1];

                   {Запоминаем a в последний
элемент массива}

                            b[delta-1]:=a;

         end;

writeln(R);

End.

Модификация задачи (тип III)

Для заданной последовательности положительных
целых чисел необходимо найти минимальное, кратное пяти произведение двух её
элементов, номера которых различаются не менее чем на 6. Если таких чисел нет,
вывести 0.

Значение каждого элемента последовательности
не превышает 1000. Количество элементов последовательности не превышает 10000.

Можно заметить, что
задача очень похожа на предыдущую, но появляется дополнительное условие, а
именно необходимость кратности пяти произведения. Получается некий симбиоз
задачи типа II и типа III. Объединим
идеи.

Решение задачи А (не оптимальное)

Var a:array [1..10000] of integer;

n, i, j: integer;

Rmin, R :longint;

Begin

readln(n);

for i:=1 to n do      

readln(a[i]);

Rmin:=1000001;

for i:=1 to n-6  do

for   j:=i+6to n
do

begin

                            R:=a[i]+a[j];

                            if(R<Rmin) and (R mod 5
=0)  then 

                            Rmin:=R;

                   end;

ifRmin=1000001
then

                   Rmin:=0;

writeln(Rmin);

End.

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

Во-первых нам надо
хранить не только наименьшее значение из предыдущей последовательности, но и
число, которое наименьшее из кратных 5, потому как оно точно даст произведение,
кратное 5, а вот другое наименьшее может не подойти. Приведем полный текст с
комментариями.

Программа для решения задачи Б

Constdelta=6;
{минимальный интервал}

VarR :longint ;{минимальное произведение}

         n, a:integer;{количество
чисел, очередное значение}

m, m5:integer;{наименьшее, наименьшее из кратных 5}

b :array[1..delta-1] ofinteger;
{массив промежуточных значений}

Begin

         R:=1000001;

         readln(n);readln(m);

         if (m mod 5)=0 then

 m5:=m

else

  m5:=0;

         for i:=1 to delta-1 do

readln(b[i]);

         for i:= delta+1 to n do

         begin readln(a);

                   {проверяемпроизведение
снаименьшим, кратным 5}

                   if
((m5<>0)  and ((m5*a)<R) then

 R:=a*m5;

                   {проверяем
произведение с наименьшим и чтобы оно было кратно 5}

                 if
((a mod 5)=0) and (a*m<R)) then

                                  R:=a*m;

{проверяем, не
является ли 1-е число в массиве наименьшим и наименьшим, кратным 5}

                   ifb[1]<mthen

                             m:=b[1];

                   if (b[1]mod
5=0)and (b[1]<m5) then

                             m5:=b[1];

{сдвиг в массиве}

                   for
j:=1 to delta-2 do b[i]:=b[i+1];

                   b[delta-1]:=a;

         end;

ifRmin=1000001 then Rmin:=0;

writeln (Rmin);

End.

Возможная формулировка задания (тип IV)

На ускорителе для большого числа частиц
производятся замеры скорости каждой из них. Скорость частицы — это целое
неотрицательное число. Частиц, скорость которых измерена, может быть очень
много, но не может быть меньше трёх. Скорости всех частиц различны. Скорость,
по крайней мере, одной частицы нечётна.

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

При данной формулировке задачи проще сразу
рассмотреть оптимальное решение.

Поскольку задачу
нужно решать в один проход (если делать оптимальное решение), то сумму надо
считать одновременно с чтением данных.

Проблема 1: сумма должна быть максимальной по значению, но минимальной по
количеству.

Вывод: нужно брать все положительные элементы и не брать нулевые.

Проблема 2: не все  числа должны входить в эту сумму, чтобы она была нечетной.

Вывод: надо запоминать «кандидатов» на удаление из последовательности, если
сумма вдруг получится четной. Это должно быть нечетное число с одной стороны и
минимальное из нечетных, чтобы сумма уменьшилась на минимальное возможное
значение.

Текст оптимального
решения представлен ниже.

Программа оптимального решения

Vars: longint ;       {сумма}

         n, a:integer; {количествочисел, очередноезначение}

m :integer;   {наименьшеенечетное}

Begin

         S:=0;

readln(n);   

m:=0;

         for i:= 1 to n do

         begin

                   readln(a);

                   S:=s+a;

                   if ( (a mod 2)=1)  and ((m=0)or (a<m))
then

                            m:=a;

         end;

         if (s mod 2)=0 then

s:=s-m;

writeln(R);

End.

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

Возможная формулировка задания (тип V)

На вход даны пары чисел. Нужно выбрать из
каждой пары по одному числу так, чтобы сумма всех выбранных чисел не была
кратна 6 и при этом была минимально возможной. Напишите программу, выводящую такую
сумму на экран. Если же ее невозможно получить, выведите 0. Баллы начисляются
за ту из подзадач, что решена на большее количество баллов. Задача А дает 2
балла, задача Б — 4 балла. В задаче А приведите неэффективный алгоритм. При
решении указывайте, какую подзадачу делаете. За алгоритм, неэффективный по
времени ИЛИ памяти, дается 3 балла, по времени И памяти — 2 балла.

Задача А. Количество пар известно заранее и
равно 6. Числа не превышают 30 000.

Пример входных данных:

6

5 4

3 2

1 1

18 3

11 12

2 5

Пример выходных данных:

23

Полный перебор представляет собой вложенные
циклы для перебора всех возможных пар значений.

РешениезадачиА

Var a:array[1..6,1..2]of integer;

         i,j1,j2,j3,j4,j5,j6,s,smin: integer;

Begin

for i:=1 to 6 do

for j1:=1 to 2 do  

read(a[I,j1]);

smin:=1000*6+1;

for j1:=1 to 2 do

for j2:=1 to
2 do

for j3:=1 to 2
do 

for j4:=1
to 2 do       

                            for j5:=1 to 2 do   

                                     for j6:=1 to 2 do

                                      begin

                            s:=a[1,j1]+ a[2,j2] +a[3,j3]+
a[4,j4]+ a[5,j5] +a[6,j6];

                                               if
(s<smin)and(s mod 6 <>0) then smin:=s

                                     end;

ifsmin=
1000*6+1 then smin:=1;

writeln(smin);

End.

Идея решения задачи Б

Поскольку задачу нужно решать в один проход
(если делать оптимальное решение), то сумму надо считать одновременно с чтением
данных.

Проблема 1: сумма
должна быть минимальной по значению.

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

Проблема 2: Сумма
может получиться кратной 6.

Вывод: надо
запоминать «кандидатов» на замену одного числа из пары на другое, если сумма
вдруг получится кратной 6. Число должно иметь, во первых, минимальную разницу с
заменяемым, а во-вторых, должно иметь другой остаток при делении на 6, чтобы и
сумма поменяла свой остаток от деления. Сумма при этом увеличится именно на
разницу между числами, поэтому проще запоминать именно ее.

Ниже приведен полный текст решения задачи.

Решение задачи Б

Varn:integer; {количествочисел}

a, b : integer; {очереднаяпарачисел}

         dmin, d : integer; {минимальная разница между числами в
паре}

         s:integer; i:integer;

Begin

readln(n);

s:=0; d:=1001;

for i:=1 to n do  

begin

readln(a,b);

                   {добавляем минимальное
число в сумму}

ifa<bthen

s:=s+a

else

s:=s+b;

                   {вычисляем разницу между
числами}

d:=abs(a—b);

                   {если разница минимальна и
не кратна 6, запоминаем ее}

if (d<dmin)and(dmod 6
<>0) then

dmin:=d;

end;

{если сумма
получилась кратной 6, увеличиваем ее на dmin}

If(s mod 6) =0 then

Ifdmin=1001 then

s:=0

else

s:=s+dmin;

writeln(s);

end.

Список
использованных источников

1)    В.Р. Лещинер, М.А. Ройтберг. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ для учителей,
подготовленные на основе анализа типичных ошибок Участников ЕГЭ 2016 года  по
ИНФОРМАТИКЕ и ИКТ. – http://www.fipi.ru/ege—i—gve-11/analiticheskie—i—metodicheskie—materialy.

2)    КИМ ЕГЭ «Информатика и ИКТ» http://www.ege.edu.ru/ru/classes-11/preparation/demovers/

3)    Материалы сайта Полякова К.Ю. по подготовке к ЕГЭ http://kpolyakov.spb.ru/school/ege.htm.

4)    Информатика и ИКТ. Подготовка к ЕГЭ 2016. 20 тренировочных вариантов по
демоверсии на 2016 год: учебно-методическое пособие./Под ред. Л. Н. Евич, С.Ю.
Кулабухова. – Ростов наДону: Легион, 2015.

5)    Каталог заданий сайта «Решу ЕГЭ». –

         https://inf—ege.sdamgia.ru/test?a=catlistwstat