Методика решения и оценивания задач части «С» Единого Государственного Экзамена Информатика Ульяновск, 2009 г

Задание С1 Тема: Исправление ошибок в простой программе с условными операторами. Цель задания: Умение прочесть фрагмент программы на языке программирования и исправить допущенные ошибки Время на решение: 30 минут.

Что нужно знать по С1 правила построения программы на Паскале правила работы с переменными (объявление, ввод, вывод, оператор присваивания) правила использования составного оператора begin-end правила организации ветвлений с использованием оператора if-then-else (в полной и сокращенной форме) простые отношения, используемые для организации условий (, >=, =, <>) правила построения сложных условий с использованием логических операций or (логическое ИЛИ), and (логическое И) и not (отрицание). приоритетность выполнения логических операций or, and, not математику!!!

Пример задания С1 Требовалось написать программу, которая вводит с клавиатуры координаты точки на плоскости (x, y – действительные числа) и определяет принадлежность точки заштрихованной области, включая ее границы. Программист торопился и написал программу неправильно. Вот она: var x,y: real; begin readln(x,y); if y <= 1 then if x >= 0 then if y >= sin(x) then write('принадлежит') else write('не принадлежит') end. Последовательно выполните следующее: 1) Приведите пример таких чисел x, y, при которых программа неверно решает поставленную задачу. 2) Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, поэтому можно указать любой способ доработки исходной программы).

Методика решения задач типа С1 1. Отложим программу в сторону и определим по графику набор условий, которые должны быть выполнить справа от оси y, что равносильно условию x>=0 слева от первого максимума функции; из математики мы знаем, что эта функция достигает максимума при x = pi/2, поэтому получаем второе условие x <= pi/2 ниже линии y = 1, откуда следует третье условие y <= 1 выше линии y = sin(x), что дает четвертое условие y >= sin(x) Вывод: точка принадлежит указанной области, только если выполняются все 4 условия!!!

Методика решения задач типа С1 2. Из программы видно, что не хватает одного условия x <= pi/2, поэтому можно определить точку, которая не принадлежит указанной области, но в программе не обрабатывается Это может быть точка с координатами x = 3.14, y = 0.5 или любая другая, для которой выполняется условие y>=sin(x) и x > pi/2

Методика решения задач типа С1 3.Выясним, когда программа выдает сообщение «Не принадлежит». Для этого запишем ее «лесенкой» или «составим блок-схему» по схеме видим, что если первое условие ложно, или второе условие ложно, то программа вообще не выдает никакого сообщения, то есть, работает неправильно if y <= 1 then if x >= 0 then if y >= sin(x) then write('принадлежит') else write('не принадлежит')

Методика решения задач типа С1 4. Исправим программу, чтобы она работала корректно данное решение является правильным, но не совсем элегантным, поскольку для такой простой программы выводит 4 раза надпись «Не принадлежит»… однако баллы за это не снимаются!!!! if x <= pi/2 then if y <= 1 then if x >= 0 then if y >= sin(x) then write('принадлежит') else write('не принадлежит') else write('не принадлежит');

Методика решения задач типа С1 5. Более красивое решение для этой задачи состоит в использовании одного сложного условия, построенного с помощью логической операции and. var x,y: real; begin readln(x,y); if (x >= 0) and (x <= pi/2) and (y = sin(x)) then write('принадлежит') else write('не принадлежит'); end.

Возможные проблемы в задачах С1 1. как правило, в этой задаче требуется использовать знания из курса математики (решение уравнений, графики функций, составление уравнений прямой по приведенному графику) 2. как показывает анализ опубликованных задач этого типа, нужно уметь, прежде всего, разбираться в серии вложенных условных операторов в полной и неполной форме 3. неправильная «лесенка» в записи сбивает с толку и подталкивает к неверному решению; чтобы разобраться в программе, лучше на черновике построить блок-схему алгоритма и правильную «лесенку» 4.проверяйте, все ли необходимые условия учтены в программе, это особенно актуально для немонотонных функций типа синуса или косинуса (немонотонные функции на некоторых участках возрастают при увеличении аргумента, а на некоторых – убывают);

Возможные проблемы в задачах С1 5. не перепутайте, где нужно использовать операцию and («И», одновременное выполнение условий), а где – or («ИЛИ», хотя бы одно условие) 6. нужно внимательно проверять, всегда ли программа выдает сообщение, если заданное условие не выполняется 7. часто бывает полезно нарисовать блок-схему алгоритма, которая позволяет увидеть ход выполнения программы при всех возможных вариантах 8.проверяйте, включает ли заданная область свои границы; если включает – в отношениях будут нестрогие неравенства ( =), если не включает – строгие ( )

Критерии оценивания С1 Обратите внимание! В задаче требовалось выполнить три действия: Указать пример входных данных, при которых программа работает неверно. Исправить ошибку неправильного использования условного оператора, в результате чего при невыполнении первого или второго условия программа не выдавала ничего (отсутствуют случаи ELSE). Исправить ошибку согласно которой в программе приведенным трем ограничениям удовлетворяют также те точки плоскости, у которых y>= sin(x) и x> pi/2

За что снимаются баллы неправильно определены входные данные, при которых исходная программа работает неверно исправлены не все ошибки в программе, например, легко «просмотреть», что необходимо еще условие программа работает правильно в большем количестве случаев, чем исходная, но не для всех возможных исходных данных перепутаны знаки, логические операции or и and неверно расставлены операторные скобки begin-end синтаксические ошибки (знаки пунктуации – запятые, точки, точки с запятой; неверное написание ключевых слов); чтобы получить 3 балла, нужно сделать не более одной синтаксической ошибки; на 2 балла – до двух ошибок, на 1 балл – до трех ошибок

Замечания по оцениванию С1 В качестве примера входных данных можно приводить не только число (или числа), но и множество, интервал, неравенство. Если в первой части задания приводится несколько чисел, причем среди них есть как правильные, так и НЕ правильные, то результат не засчитывается.

Задача для решения… Требовалось написать программу, в которой нужно было проверить, лежит ли число x на числовой оси между числами a и b ("между" понимается в строгом смысле, т.е. случай x=a или x=b недопустим). Числа x, a, b являются натуральными, и известно, что a отлично от b (но неизвестно: a>b или b>a). Входная информация вводится с клавиатуры, а на выходе должно быть сообщение вида "x между a,b" (если это действительно так), в противном случае никакой выходной информации не выдается. Программист торопился и написал программу некорректно. VAR a,b,x: integer; BEGIN readln(a,b,x); if (a>x) AND (x>b) then writeln('x между a,b'); END. Последовательно выполните следующее 1) Привести пример таких чисел a, b, x, при которых программа работает неправильно. 2) Указать, как нужно доработать программу, чтобы не было случаев ее неправильной работы. 3) Наложено дополнительное условие: доработанная программа не должна использовать логических операций AND или OR. Указать, как можно доработать программу, соблюдая это условие.

Варианты решения и оценка Оценка: 1) 0 2) 1 3) 0ИТОГО: 1 балл

Варианты решения и оценка Оценка: 1) 0 2) 0 3) 1ИТОГО: 1 балл

Варианты решения и оценка Оценка: 1) 1 2) 1 3) 1ИТОГО: 3 балла

Задание С2 Тема: Обработка массива Цель задания: Умение написать короткую (10-15 строк) простую программу обработки массива на языке программирования или записать алгоритм на естественном языке. Время на решение: 30 минут.

Что нужно знать по С2 определение массива и правил его объявления (одномерного и двумерного); правила обращения к элементам массива по индексу; использование операторов цикла for, while, repeat для обработки массива основные функции обработки одномерных массивов (подсчет суммы элементов массива, подсчет количества элементов массива, поиск максимального и минимального элементов и их местоположения, сортировка массива) основные функции обработки двумерных массивов (обработка отдельных строк и столбцов, подсчет суммы элементов массива, подсчет количества элементов массива, поиск максимального и минимального элементов и их местоположения)

Пример задания С2 Опишите на русском языке или одном из языков программирования алгоритм подсчета максимального количества подряд идущих совпадающих элементов в целочисленном массиве длины 30.

Методика решения задач типа С2 1. Разобраться в сути задачи, понять ее и нарисовать пример массива

Методика решения задач типа С2 2. Сформулировать для себя (может быть пока не полный и не точный) алгоритм, например такой: «Пройти весь массив, подсчитывая для каждого элемента длину цепочки подряд идущих одинаковых чисел, если эта длина больше текущей, то запомнить ее» Для этого понадобятся как минимум две переменные: k – текущая длина цепочки повторений kMax – максимальная длина цепочки K kMax

Методика решения задач типа С2 3. Сформулируем окончательный алгоритм на русском языке: «Выделим две вспомогательные переменные, k и kMax, и запишем в каждую из них по единице. В цикле рассматриваем все элементы массива со второго до последнего, если очередной элемент равен предыдущему, увеличиваем k; если k > kMax, записываем в kMax значение k. В конце цикла в kMax окажется требуемое значение».

Методика решения задач типа С2 4. Сформулируем окончательный алгоритм на Паскале: const N =30; var a: array[1..N] of integer; i, k, kMax: integer; begin k := 1; { обрабатываем A[1] } kMax := 1; for i:=2 to N do begin { а теперь в цикле A[2]...A[N} } if A[i] = A[i-1] then { цепочка продолжается } k := k + 1 else k := 1; { цепочка закончилась } if k > kMax then kMax := k; end; writeln(kMax); end.

Возможные проблемы в задачах С2 проверьте, что будет записано в переменные до начала цикла (определены ли их начальные значения) проверяйте, не выйдет ли индекс за границу массива в начале или в конце цикла будьте внимательны с «крайними» случаями, например, нужно обязательно убедиться, что программа работает, когда интересующая нас цепочка стоит в самом начале или в самом конце массива

Критерии оценивания С2 Задание С2 относится к высокому уровню сложности. За решение этого задания можно получить два балла. По содержанию проверяет умение формально описывать известный (изученный в школе) алгоритм на естественном языке или на языке программирования.

За что снимаются баллы задано неверное начальное значение переменных (или вообще не задано) неверно указано условие завершения цикла «забыли» изменять переменную цикла в цикле while (repeat) перепутаны знаки, логические операции or и and неверно расставлены операторные скобки begin-end программа не выводит результат или выводит не то, что спрашивают синтаксические ошибки (знаки пунктуации – запятые, точки, точки с запятой; неверное написание ключевых слов) допускаются в разумных пределах (если они не искажают замысел автора)

Замечания по оцениванию С2 Ответ может быть представлен в виде текста на русском языке, алгоритма на псевдокоде, блок- схемы, программы на языке программирования Описывать алгоритм ввода данных в массив не требуется Для естественного языка возможно использование не вполне четких формулировок при существовании правильной интерпретации высказывания Не разрешается использовать стандартные процедуры и функции из библиотек (кроме функций чтения и записи) Эффективность алгоритма не оценивается За синтаксические ошибки, способ записи (отступы, прописные/строчные буквы), качество изображения графических элементов баллы не снимаются.

Задача для решения… Опишите на русском языке или на одном из языков программирования алгоритм поиска второго по величине (т.е. следующего по величине за максимальным) элемента в числовом массиве из 30 различных элементов.

Варианты решения и оценка Оценка: 0 баллов

Варианты решения и оценка Оценка: 2 балла

Варианты решения и оценка Оценка: 0 баллов

Задание С3 Тема: Дерево игры. Поиск выигрышной стратегии. Цель задания: Умение построить дерево игры по заданному алгоритму и обосновать выигрышную стратегию Время на решение: 30 минут.

Что нужно знать по С3 правила построения дерева игры (то есть перечисления всех возможных ходов игроков) правила исключения из рассмотрения тех ходов, которые являются ошибочными (по правилам игра ведется безошибочно обоими игроками) правила поиска в построенном дереве выигрышной стратегии, то есть наличия такой вершины («переломного момента игры»), после посещения которой, один из игроков проигрывает всегда (при безошибочной игре соперника)

Пример простого задания Сначала в кучке лежит 5 спичек; два игрока убирают спички по очереди, причем за 1 ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку.

Методика решения задачи 1. Построим полное дерево игры.

Методика решения задачи 2. Кто же выиграет при правильной игре? для этого нужно ответить на вопросы: a.1) «Может ли первый игрок выиграть, независимо от действий второго?» b.2) «Может ли второй игрок выиграть, независимо от действий первого?» a.Да b.Нет

Методика решения задачи 3. Таким образом, при правильной игре выиграет первый игрок; для этого ему достаточно первым ходом убрать всего одну спичку Это доказательство!!!

Пример задания С3 Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 1, а во второй 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 2 камня в какую то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 17 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Методика решения задачи С3 1. Построим полное дерево игры.

Методика решения задачи С3 1. Построим полное дерево игры.

Методика решения задачи С3 1. Построим полное дерево игры.

Методика решения задачи С3 1. Построим полное дерево игры.

Методика решения С3 2. Выигрывает второй игрок. Из дерева игры видно, что при любом ходе первого игрока у второго имеется ход, приводящий к победе.

Пример задания С3 Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5,2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: или в точку с координатами (x+3,y), или в точку с координатами (x,y+3), или в точку с координатами (x,y+4). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0,0) не меньше 13 единиц. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Методика решения задачи С3 1. Построим полное дерево игры.

Методика решения С3 2. Выигрывает второй игрок. Из дерева игры видно, что при любом ходе первого игрока второй игрок должен свести ситуацию к положению фишки (8,5) или (8,6), что приведет к победе второго игрока при любых ходах первого

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

За что снимаются баллы в С3 если вы правильно указали выигрывающего игрока, но не привели никакого обоснования, эксперт поставит 0 баллов не описана стратегия выигрывающего игрока (как именно ему нужно ходить) не проведен полный анализ возможных ходов обоих игроков (рассмотрены не все случаи ответных ходов)

Замечания по оцениванию С3 Доказательство выигрышности стратегии может быть представлено в любой форме Указание выигрывающего игрока без выигрышного хода не оценивается Если существует две (или более выигрышных стратегий) и ученик нашел только одну из них, то решение задачи засчитывается как полное Если есть все дерево, но нет анализа, то балл не ставится

Задача для решения… Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 5, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 22 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок? Ответ обоснуйте.

Варианты решения и оценка Оценка: 1 балл

Варианты решения и оценка Оценка: 2 балла

Задание С4 Тема: Обработка данных, вводимых в виде символьных строк (написать программу средней сложности из строк). Цель задания: Умение создавать собственные программы (30-50 строк) для решения задач средней сложности Время на решение: 60 минут.

Что нужно знать по С4 правила объявления записей в языке Паскаль правила объявления массива записей правила работы с текстовыми файлами (открытие, ассоциирование, чтение, закрытие) правила представления и обработки строк основные функции и процедуры работы со строками

Пример задания С4 На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой строке сообщается количество учеников N, которое не меньше 10, но не превосходит 100, каждая из следующих N строк имеет следующий формат:, где – строка, состоящая не более чем из 20 символов, – строка, состоящая не более чем из 15 символов, – через пробел три целых числа, соответствующие оценкам по пятибалльной системе. и, а также и разделены одним пробелом. Пример входной строки: Иванов Петр Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран фамилии и имена трех худших по среднему баллу учеников. Если среди остальных есть ученики, набравшие тот же средний балл, что и один из трех худших, то следует вывести и их фамилии и имена.

Общая методика решения С4

Методика решения С4 1. До того, как начать писать «нормальный» код, нужно определить, как хранить данные; в данном случае нужно запомнить несколько данных по каждому ученику, их удобнее объединить в запись с двумя полями (фамилия-имя и сумма баллов); таких записей нужно выделить в памяти не менее 100 (по условию), то есть, массив из 100 элементов: const LIM=100; var Info: array[1..LIM] of record name: string; sum: integer; end;

Методика решения С4 2. Чтение данных по полю «фамилия» repeat read ( c ); Info[i].name := Info[i].name + c; until c = ' '; { пока не прочитали пробел } 3. Чтение данных по полю «имя» repeat read ( c ); Info[i].name := Info[i].name + c; until c = ' '; { пока не прочитали пробел }

Методика решения С4 4. Чтение данных по полю «Оценки» Info[i].sum := 0; for k:=1 to 3 do begin read(mark); Info[i].sum := Info[i].sum + mark; end; readln;

Методика решения С4 for i:=1 to N do begin { ввод имени и фамилии } Info[i].name := ''; for k:=1 to 2 do repeat read(c); Info[i].name := Info[i].name + c; until c = ' '; { ввод и суммирование оценок } Info[i].sum := 0; for k:=1 to 3 do begin read(mark); writeln(mark); Info[i].sum := Info[i].sum + mark; end; readln; end;

Методика решения С4 5. Алгоритм поиска трех минимальных min1 := 20; min2 := 20; min3 := 20; for i:=1 to N do begin if Info[i].sum < min1 then begin { новый min1 } min3 := min2; min2 := min1; min1 := Info[i].sum; end else if Info[i].sum < min2 then begin { новый min2 } min3 := min2; min2 := Info[i].sum; end else if Info[i].sum < min3 then { новый min3 } min3 := Info[i].sum; end;

Методика решения С4 6. Вывод результатов на экран for i:=1 to N do if Info[i].sum <= min3 then writeln(Info[i].name);

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

За что снимаются баллы перепутаны знаки, логические операции or и and применяется недопустимая операция, например, div или mod для вещественных чисел неверно расставлены операторные скобки begin-end в цикле for используется вещественная переменная (Паскаль) в цикле while или repeat не изменяется переменная цикла, из-за чего происходит зацикливание синтаксические ошибки (знаки пунктуации – запятые, точки, точки с запятой; неверное написание ключевых слов); чтобы получить 4 балла, нужно сделать не более одной синтаксической ошибки; на 3 балла – до трех ошибок, на 2 балла – до пяти и на 1 балл – до семи ошибок

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

Список используемых источников Сайт Константина Полякова Материалы для подготовки к ЕГЭ Демонстрационные варианты ЕГЭ с 2004 по 2009 год Учебно-методические материалы для председателей и членов региональных предметных комиссии по проверке выполнения заданий с развернутым ответом экзаменационных работ ЕГЭ 2009 года по информатике

Спасибо за внимание Составитель: доцент каф. ВТ, к.т.н. Мартынов А.И. Ульяновск, 2009 год