Написание сложной программы.

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

Поговорим о задаче 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...

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

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

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