ЕГЭ по информатике (часть С) Никитина Т.П., к.т.н., доцент ЯГТУ февраль 2013 г. - презентация

1 ЕГЭ по информатике (часть С) Никитина Т.П., к.т.н., доцент ЯГТУ февраль 2013 г.

2 Задача С Тема: Определение условий попадания в заданные области и исправление ошибок в простой программе с условными операторами Знать – базовую алгоритмическую структуру - ветвление и конкретные реализации ее в языках программирования. Язык программирования Паскаль: if then else ; Условие задачи. Требовалось написать программу, при выполнении которой с клавиатуры считывается координата точки на прямой (x – действительное число) и определяется принадлежность этой точки одному из выделенных отрезков В и D (включая границы). Программист торопился и написал программу неправильно.

3 Задача С1 Паскаль var x: real; begin readln(x); if x>=-3 then if x1 then write('не принадлежит') else write('принадлежит') end. Си void main(void) { float x; scanf("%f",&x); if(x>=-3) if(x1) printf("не принадлежит"); else printf("принадлежит"); } =-3) if(x1) printf("не принадлежит"); else printf("принадлежит"); }">

4 Задача С1 Последовательно выполните следующее. 1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (A, B, C, D и E). Границы (точки –3, 1, 5 и 9) принадлежат заштрихованным областям (B и D соответственно).

5 Задача С1 В столбцах условий укажите «да», если условие выполнится, «нет», если условие не выполнится, «» (прочерк), если условие не будет проверяться, «не изв.», если программа ведет себя по-разному для разных значений, принадлежащих данной области. В столбце «Программа выведет» укажите, что программа выведет на экран. Если программа ничего не выводит, напишите «» (прочерк). Если для разных значений, принадлежащих области, будут выведены разные тексты, напишите «не изв.». В последнем столбце укажите «Да» или «Нет». 2. Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)

6 Задача С1 Нет нет

7 Задача С1 Возможная доработка (Паскаль) if (x>=-3) and (x =5) and (x

8 Задача С1 Возможная доработка Си if ((x>=-3) && (x =5) && (x

9 Задача С1 Указания по оцениванию Обратите внимание! В задаче требуется выполнить три действия. 1. Заполнить таблицу. 2. Исправить ошибку в условном операторе. 3. Исправить ошибку, связанную с неправильным набором условий. Баллы за данное задание начисляются как сумма баллов за верное выполнение каждого действия. 1. Действие по заполнению таблицы считается выполненным, если в таблице нет ошибок или ошибки присутствуют только в одной строке.

10 Задача С1 Указания по оцениванию 2. Неправильное использование условного оператора, в результате чего при невыполнении первого или второго условия программа не выдавала ничего (отсутствуют случаи ELSE). Исправлением этой ошибки может быть либо добавление ELSE к каждому условию IF, либо объединение всех условий IF в одно при помощи конъюнкции. В сложных случаях это действие считается выполненным, если программа выдает одно из двух сообщений: «принадлежит» или «не принадлежит» – для любых чисел x, при этом программа не стала работать хуже, чем раньше, т.е. для всех точек, для которых программа ранее выдавала верный ответ, доработанная программа также должна выдавать верный ответ.

11 Задача С1 Указания по оцениванию 3. Приведённых трёх ограничений недостаточно для описания двух областей (потеряно условие x>=5). Кроме того, необходимо учесть, что области не соединены. Исправлением этой ошибки может быть разбиение области на две части и использование дизъюнкции, либо использование сложной (для выведения) математической конструкции (||x–3|–4|2), либо использование сложной комбинации каскадных условий. В сложных случаях это действие считается выполненным, если верно определены заштрихованные области, т.е. программа выводит сообщение «принадлежит» для всех точек закрашенных областей, и только для них, для точек вне заштрихованных областей программа выводит «не принадлежит» или не выводит ничего. В работе (во фрагментах программ) допускается наличие отдельных синтаксических ошибок, не искажающих замысла автора решения

12 Задача С1 Указания по оцениванию Максимальный балл за задачу С1 - 3 Он ставится если правильно выполнены все три действия. Два балла ставится в следующих случаях. Правильно выполнены два действия из трёх (исправлены обе ошибки, но в пункте 1 задания не приведена таблица (либо таблица содержит ошибки в двух и более строках), либо приведена таблица (которая содержит ошибки не более чем в одной строке), но исправлена только одна ошибка программы). При написании операций сравнения допускается одно неправильное использование строгих/нестрогих неравенств (считается несущественной ошибкой, погрешностью записи). Например, вместо «x>=5» используется «x>5»

13 Задача С1 Указания по оцениванию Один балл Правильно выполнено только одно действие из трёх, т.е. либо только приведена таблица, которая содержит ошибки в не более чем одной строке, либо таблица не приведена (или приведена и содержит ошибки более чем в одной строке), но исправлена одна ошибка программы. При оценивании этого задания на 1 балл допускается не учитывать корректность работы программ на точках границ областей (вместо нестрогих неравенств в решении были использованы строгие неравенства или наоборот). 0 баллов Все пункты задания выполнены неверно (таблица анализа правильности алгоритма не приведена либо содержит ошибки в двух и более строках, программа не приведена либо ни одна из двух ошибок не исправлена)

14 Задача С Требовалось написать программу, при выполнении которой с клавиатуры считываются координаты точки на плоскости (x, y – действительные числа) и определяется принадлежность этой точки заданной закрашенной области (включая границы). Программист торопился и написал программу неправильно.

15 Задача С1 2012

16 Последовательно выполните следующее. 1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (A, B, C, D, E, F и G). Точки, лежащие на границах областей, отдельно не рассматривать.

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

18 Задача С Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)

19 Задача С1 2012

20 2. Возможная доработка (Паскаль): if (x =x) or (x>=0) and (y>=0) and (y=x)) then write('принадлежит') else write('не принадлежит');

21 Задача С Максимальный балл 3 В задаче требовалось выполнить три действия: указать для каждой области, как будет работать программа, что она выведет на экран и правильно ли это (в виде таблицы), и исправить две ошибки. Баллы за данное задание начисляются как сумма баллов за верное выполнение каждого действия. 1. Верное заполнение предложенной таблицы. 2. Неправильное использование условного оператора, в результате чего при невыполнении первого или второго условия программа не выдавала ничего (отсутствуют случаи ELSE). Исправлением этой ошибки может быть либо добавление случая ELSE к каждому условию IF, либо объединение всех условий IF в одно при помощи конъюнкции. В сложных случаях это действие считается выполненным, если программа выдает одно из двух сообщений «принадлежит» или «не принадлежит» для любых чисел x и y, при этом программа не стала работать хуже, чем раньше, то есть для всех точек, для которых программа ранее выдавала верный ответ, доработанная программа также должна выдавать верный ответ.

22 Задача С Максимальный балл 3 3. Приведенным трем ограничениям не удовлетворяют точки плоскости, у которых y 2 x2, y x и y < 0, а также точки, для которых y 2 x2, y < x и y 0. Исправлением этой ошибки может быть разбиение области на две части и использование дизъюнкции либо отбрасывание от большей области ее части. В сложных случаях это действие считается выполненным, если верно определена закрашенная область, то есть программа выводит сообщение «принадлежит» для всех точек закрашенной области и только для них, для точек вне закрашенной области программа выводит «не принадлежит» или не выводит ничего.

23 Задача С Максимальный балл 3 Правильно выполнены оба пункта задания. Исправлены две ошибки. Программа для всех пар чисел x, y верно определяет принадлежность точки закрашенной области. В работе (во фрагментах программ) допускается наличие отдельных синтаксических ошибок, не искажающих замысла автора решения.

24 Задача С Максимальный балл 3 1. Правильно выполнены два действия из трех (исправлены обе ошибки, но в первом пункте задания не приведена таблица (либо таблица содержит ошибки более чем в одной строке), либо приведена таблица которая содержит ошибки не более чем в одной строке, но исправлена только одна ошибка программы. При написании операций сравнения допускается одно неправильное использование строгих/нестрогих неравенств (считается несущественной ошибкой, погрешностью записи). Например, вместо «y>=-x» используется «y>-x». 2. Или выполнены все три действия, но при этом в логическом выражении неверно учтены приоритеты логических операций (не расставлены или неправильно расставлены скобки в выражениях).

25 Задача С Максимальный балл 3 Правильно выполнено только одно действие из трех, то есть, либо только приведена таблица, которая содержит ошибки в не более чем двух строках, либо таблица не приведена (или приведена и содержит ошибки более чем в двух строках), но исправлена одна ошибка программы. При оценивании этого задания на 1 балл допускается не учитывать корректность работы программ на точках границ областей (вместо нестрогих неравенств в решении были использованы строгие неравенства или наоборот). 0 баллов. Все пункты задания выполнены неверно (таблица анализа правильности алгоритма не приведена, либо содержит ошибки более чем в двух строках, программа не приведена, либо ни одна из двух ошибок не исправлена).

26 Задача С Массивы Массив – это набор однотипных элементов, имеющих общее имя и расположенных в смежных участках памяти для обращения к элементу массива необходимо указать имя массива и индексное выражение. A[i] обозначает элемент массива A с номером (индексом) i. Для обработки всех элементов одномерного массива используется цикл вида for i:=1 to N do... A[i] … ; Матрица (двухмерный массив) – это прямоугольная таблица однотипных элементов, если матрица имеет имя A, то обращение A[i,k] обозначает элемент, расположенный на пересечении строки i и столбца k. Для обработки всех элементов двумерного массива используются вложенные циклы for i:=1 to N do for k:=1 to N do …. A[i,k]…..;

27 Задача С Свойства матриц если номер строки элемента совпадает с номером столбца (i = j), это означает что элемент лежит на главной диагонали матрицы Для работы со всеми элементами главной диагонали достаточно использовать цикл for i:=1 to N do... A[i,i] … ; если номер строки превышает номер столбца (i > j), то элемент находится ниже главной диагонали; если номер столбца больше номера строки (i < j), то элемент находится выше главной диагонали. элемент лежит на побочной диагонали, если его индексы удовлетворяют равенству i + j - 1 = n; неравенство i + j - 1< n характерно для элемента находящегося выше побочной диагонали; соответственно, элементу лежащему ниже побочной диагонали соответствует выражение i + j - 1 > n.

28 Задача С Условие задачи Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 100. Опишите на русском языке или на одном из языков программирования алгоритм, позволяющий найти и вывести произведение элементов массива, которые имеют нечётное значение и делятся на 3. Гарантируется, что в исходном массиве есть хотя бы один элемент, значение которого нечётно и кратно 3. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них. Исходные данные всегда подобраны так, что результат произведения не выходит за пределы объявленных типов данных.

29 Задача С Условие задачи Паскаль const N=30; var a: array [1..N] of longint; i, j, p: longint; begin for i := 1 to N do readln(a[i]); … end. Си #include #define N 30 void main(void) { long a[N]; long i, j, p; for (i=0; i

30 Задача С Решение На языке Паскаль p := 1; for i := 1 to N do if (a[i] mod 20) and (a[i] mod 3=0) then p := p * a[i]; writeln(p); На языке СИ p=1; for (i=0; i

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

32 Задача С Указания по оцениванию Ставится если в любом варианте решения может присутствовать не более одной ошибки из числа следующих. 1. Не инициализируется или неверно инициализируется переменная P (например, присваивается начальное значение, равное 0). 2. Неверно осуществляется проверка на нечётность. 3. На нечётность проверяется не значение элемента, а его индекс. 4. Неверно осуществляется проверка делимости на На делимость на 3 проверяется не значение элемента, а его индекс. 6. В сложном условии вместо логической операции «И» используется логическая операция «ИЛИ». 7. Неверно осуществляется накопление произведения в цикле (например, p := a[i]). 8. Отсутствует вывод ответа. 9. Используется переменная, не объявленная в разделе описания переменных. 10. Не указано или неверно указано условие завершения цикла. 11. Индексная переменная в цикле не меняется (например, в цикле while) или меняется неверно. 12. Неверно расставлены операторные скобки.

33 Задача С Указания по оцениванию 0 баллов ставится, если ошибок, перечисленных в п. 1– 12, две или больше, или алгоритм сформулирован неверно.

34 Задача С Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до Опишите на русском языке или на одном из языков программирования алгоритм, позволяющий найти и вывести минимальное значение среди элементов массива, которые имеют чётное значение и не делятся на три. Гарантируется, что в исходном массиве есть хотя бы один элемент, значение которого чётно и не кратно трем. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но использовать все описанные переменные не обязательно.

35 Задача С2 2012

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

37 Задача С Содержание верного ответа На языке Паскаль min:=1000; for i:=1 to N do if (a[i] mod 2=0) and (a[i] mod 30) and (a[i]

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

39 Задача С Указания по оцениванию В любом варианте решения может присутствовать не более одной ошибки из числа следующих. 1. Не инициализируется или неверно инициализируется переменная MIN (например, ей присваивается значение a[1] или число, меньшее 1000). 2. Неверно осуществляется проверка чётности элемента массива. 3. На чётность проверяется не значение элемента, а его индекс. 4. Неверно осуществляется проверка делимости на три. 5. На делимость на три проверяется не значение элемента, а его индекс. 6. В условии проверки на делимость вместо логической операции «И» используется логическая операция «ИЛИ». 7. Отсутствует вывод ответа. 8. Используется переменная, не объявленная в разделе описания переменных. 9. Не указано или неверно указано условие завершения цикла. 10. Индексная переменная в цикле не меняется (например, в цикле while) или меняется неверно. 11. Неверно расставлены операторные скобки.

40 Задача С Указания по оцениванию 0 баллов. Ошибок, перечисленных в п. 1–11, две или больше, или алгоритм сформулирован неверно.

41 Задача С2 Дан массив из 30 элементов. Каждый элемент может принимать целочисленные значения от 0 до 100. Опишите на русском языке или на одном из языков программирования алгоритм, позволяющий найти и вывести произведение двузначных четных элементов массива, которые начинаются с цифр 5, 6 и 7. Гарантируется, что в исходном массиве есть хотя бы один такой элемент. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но использовать все описанные переменные не обязательно. const N=30; var a: array [0..N-1] of integer; i, k: integer; prod: longint; begin for i:=0 to N-1 do readln(a[i]); ………. end.

42 Задача С2 const N=30; var a: array [0..N-1] of integer; i, k: integer; prod: longint; begin for i:=0 to N-1 do readln(a[i]); prod:=1; for i:=0 to N-1 do if (a[i]>=50) and (a[i]

43 Задача С Дерево игры. Поиск выигрышной стратегии Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 22. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 22 или больше камней. В начальный момент в куче было S камней, 1 S 21. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

44 Задача С Дерево игры. Поиск выигрышной стратегии Выполните следующие задания. Во всех случаях обосновывайте свой ответ. 1. а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S. б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани. 2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём – Петя не может выиграть за один ход, и – Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети.

45 Задача С Дерево игры. Поиск выигрышной стратегии 3. Укажите значение S, при котором: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в куче.

46 Задача С а) Чтобы Петя мог выиграть, необходимо выполнение условия 2S 22 (S+1 22). Из этого следует S 11. Петя может выиграть первым ходом, если S =11, …, 21. Во всех случаях нужно удвоить количество камней в куче. При меньших значениях S за один ход нельзя получить кучу, в которой больше 21 камня.

47 Задача С б) Рассматриваем неравенства: 4S 22; 2S+1 22; 2S+2 22; S+2 22, при этом необходимо помнить, что при S=11, 12, ….21, первым же ходом выиграет Петя. Имеем S 6; S 11; S 10; S 20. Учитывая все ограничения, получает S=10. Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S =10 камней. Тогда после первого хода Пети в куче будет 11 камней или 20 камней. В обоих случаях Ваня удваивает количество камней и выигрывает своим первым ходом.

48 Задача С S 10 – установлено ранее. 8S 22; 4S+1 22; 4S+2 22; 2S+2 22; 4S+4 22; 2S+3 22; 2S+4 22; S S 4; S 6; S 5; S 10; S 5; S 9; S 19; Возможные значения S: 5 и 9. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 10 камней. Эта позиция разобрана в п. 1 б. В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (то есть, Петя) следующим ходом выиграет.

49 Задача С Содержание верного ответа 3.

50 Задача С Содержание верного ответа 3. Возможное значение S: 8. После первого хода Пети в куче будет 9 или 16 камней. Если в куче станет 16 камней, Ваня удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 9 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом.

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

52 Задача С Указания по оцениванию Максимальный балл - 3. В задаче от ученика требуется выполнить 3 задания. Их трудность возрастает. Количество баллов в целом соответствует количеству выполненных заданий. Ошибка в решении, не искажающая основного замысла, например, арифметическая ошибка при вычислении количества камней в заключительной позиции, при оценке решения не учитывается.

53 Задача С Указания по оцениванию Первое задание считается выполненным полностью, если выполнены полностью оба пункта а) и б). Пункт а) считается выполненным полностью, если правильно указаны все позиции, в которых Петя выигрывает первым ходом и указано, каким должен быть первый ход. Пункт б) считается выполненным полностью, если правильно указана позиция, в которой Ваня выигрывает первым ходом и описана стратегия Вани, т.е. показано, как Ваня может получить кучу, в которой содержится нужное количество камней при любом ходе Пети.

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

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

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

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

58 Задача С Указания по оцениванию Два балла ставится, если не выполнены условия, позволяющие поставить 3 балла, и выполнено одно из следующих условий. 1. Задание 3 выполнено полностью. 2. Первое и второе задания выполнены полностью. 3. Первое задание выполнено полностью или частично; для заданий 2 и 3 указаны правильные значения S

59 Задача С Указания по оцениванию Один балл ставится, если не выполнены условия, позволяющие поставить 3 или 2 балла, и выполнено одно из следующих условий. 1. Первое задание выполнено полностью. 2. Во втором задании правильно указано одно из двух возможных значений S и для этого значения указана и обоснована выигрышная стратегия Пети. 3. Первое задание выполнено частично и для одного из остальных заданий правильно указано значение S. 4. Для второго и третьего задания правильно указаны значения S. 0 баллов ставится если, не выполнено ни одно из условий, позволяющих поставить 3, 2 или 1 балл.

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

61 Задача С3 Содержание верного ответа Выигрывает Петя, своим первым ходом он должен добавить 2 камня к первой куче. Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записаны пары чисел, разделённые запятой. Эти числа соответствуют количеству камней на каждом этапе игры в первой и второй кучах соответственно.

62 Задача С3 Содержание верного ответа Таблица содержит все возможные варианты ходов второго игрока. Из неё видно, что при любом ответе второго игрока у первого имеется ход, приводящий к победе.

63

64 Краткая характеристика задания С4 Задание С4 предполагает написание учащимся программы на одном из распространенных языков программирования. Рекомендуется использовать языки Бейсик, Паскаль, Си, Си++, при этом версия языка указывается учащимся в явном виде на листе вместе с текстом программы. Это задача самая трудоемкая и самая сложная для проверки.

65 Для выполнения задания С4 необходимо проверять развернутый ответ в произвольной форме. Из спецификации экзаменационной работы по информатике: Проверяемые элементы содержания Умения создавать собственные программы (30-50 строк) для решения задач средней сложности Уровень сложности задания - повышенный Название раздела Технологии программирования

66 Из кодификатора элементов содержания по информатике (задание С4) Примеры возможных задач: обработка строк знаков; суммирование массива; проверка упорядоченности массива; слияние двух упорядоченных массивов; сортировка (например, вставками); поиск заданной подстроки в последовательности символов; поиск корня делением пополам; разложение целого числа на множители (простейший алгоритм); умножение двух многочленов.

67 Пример задачи С4 (2009 г.) На автозаправочных станциях (АЗС) продается бензин с маркировкой 92, 95 и 98. В городе N был проведен мониторинг цены бензина на различных АЗС. Необходимо написать эффективную по времени работы и по используемой памяти программу, которая будет определять для каждого вида бензина, сколько АЗС продают его дешевле всего. На вход программе в первой строке подается число данных о стоимости бензина. В каждой из последующих N строк находится информация в следующем формате: где – строка, состоящая не более, чем из 20 символов без пробелов, – строка, состоящая не более, чем из 20 символов без пробелов, – одно из чисел – 92, 95 или 98, – целое число в диапазоне от 1000 до 3000, обозначающее стоимость одного литра бензина в копейках. и, и, а также и разделены ровно одним пробелом. Пример входной строки: Синойл Цветочная Программа должна выводить через пробел 3 числа – количество АЗС, продающих дешевле всего 92-й, 95-й и 98-й бензин соответственно. Если бензин какой-то марки нигде не продавался, то следует вывести 0. Пример выходных данных:

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

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

70 Пример правильной и эффективной программы на языке Паскаль: var min, ans: array[92..98] of integer; c: char; i, k, N, b: integer; begin for i:=92 to 98 do begin min[i]:=3001; {допустимо и другое число >3000} ans[i]:=0; end; readln(N); for i:=1 to N do begin repeat read(c); until c=' '; {считана компания} repeat read(c); until c=' '; {считана улица} readln(k,b); if min[k] > b then begin min[k]:=b; ans[k]:=1 end else if min[k] = b then ans[k]:=ans[k]+1; end; {если бензина какой-то марки не было, ans[i] осталось равным 0} writeln(ans[92],' ', ans[95],' ', ans[98]) end.

71 #include "stdafx.h" #include void main () { int min[3], ans[3]; char c; int j,i,k,n,b; for (i=0; i

72 Указания по оцениванию Программа работает верно для любых входных данных произвольного размера и находит ответ, не сохраняя входные данные в массиве, размер которого соответствует числу N (количество данных мониторинга) или диапазону цен (3000). Программа просматривает входные данные один раз, используя для нахождения ответа два массива из 3-х (8-и) элементов каждый (как в примерах программ) или 6 соответствующих переменных. Допускается наличие в тексте программы одной синтаксической ошибки: пропущен или неверно указан знак пунктуации, неверно написано или пропущено зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку).

73 Указания по оцениванию Программа работает верно, но входные данные или только цены запоминаются в массиве, в том числе возможно в массиве (трех массивах) с индексами от 0 до 3000, обозначающем количество АЗС, продающих бензин по соответствующей цене, или входные данные считываются несколько раз. Возможно, вместо алгоритма поиска минимума используется сортировка всех цен. Допускается наличие от одной до трех синтаксических ошибок: Возможно, в принципиально верно организованном вводе данных есть одна ошибка. Три балла также выставляется, если в эффективной программе, удовлетворяющей критериям выставления 4 баллов, есть одна ошибка, в результате которой программа работает не верно на некоторых (не типичных) наборах входных данных (например, все цены на одну из марок бензина равны 3000).

74 Указания по оцениванию Программа работает в целом верно, эффективно или нет, но, в реализации алгоритма содержатся до двух ошибок (неверная инициализация переменных, в частности значения минимума, возможно программа не верно работает, если минимальное значение равно 3000, выход за границу массива, перевод символов в числа, используется знак < вместо

75 Указания по оцениванию Программа, возможно, неверно работает при некоторых входных данных. Возможно, программа не определяет или неверно определяет, что бензина какой-то марки не было. Или минимальная цена марки бензина считается верно, а количество соответствующих АЗС – нет. При использовании сортировки допущены ошибки в ее реализации. Допускается до 4 различных ошибок в реализации алгоритма, в том числе описанных в критериях присвоения двух баллов. Допускается наличие от одной до семи синтаксических ошибок, описанных выше. 0 Задание не выполнено или выполнено неверно

76 Задача С На вход программе подаются сведения о пассажирах, желающих сдать свой багаж в камеру хранения на заранее известное время до полуночи. В первой строке сообщается количество пассажиров N, которое не меньше 3, но не превосходит 1000; во второй строке – количество ячеек в камере хранения М, которое не меньше 10, но не превосходит Каждая из следующих N строк имеет следующий формат:, где – строка, состоящая не более чем из 20 непробельных символов; – через двоеточие два целых числа, соответствующие часам (от 00 до 23 – ровно 2 символа) и минутам (от 00 до 59 – ровно 2 символа); имеет тот же формат. и, а также и разделены одним пробелом. Время освобождения больше времени сдачи.

77 Задача С Сведения отсортированы в порядке времени сдачи багажа. Каждому из пассажиров в камере хранения выделяется свободная ячейка с минимальным номером. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит, не дожидаясь освобождения одной из них. Требуется написать программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет выводить на экран для каждого пассажира номер ячейки, которая ему будет предоставлена (можно сразу после ввода данных очередного пассажира). Если ячейка пассажиру не предоставлена, то его фамилия не печатается.

78 Задача С Пример входных данных: 3 10 Иванов 09:45 12:00 Петров 10:00 11:00 Сидоров 12:00 13:12 Результат работы программы на этих входных данных: Иванов 1 Петров 2 Сидоров 1

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

80 Задача С Паскаль var p:array[ ] of integer; c,c1:char; i,j,N,K:integer; name:string; time1,time2:integer; begin readln(N,K); for i:=1 to K do p[i]:=0; for i:=1 to N do begin name:=''; repeat read(c); name:=name+c until c=' '; {считана фамилия} read(c,c1); {считаны часы первого времени} time1:=60*((ord(c)-ord('0'))*10+ ord(c1)-ord('0')); read(c,c,c1); {пропущено двоеточие, и считаны минуты} time1:=time1+(ord(c)-ord('0'))*10+ord(c1)-ord('0'); read(с,c,c1); {считаны часы второго времени} time2:=60*((ord(c)-ord('0'))*10+ ord(c1)-ord('0')); readln(c,c,c1); {пропущено двоеточие, и считаны минуты} time2:=time2+(ord(c)-ord('0'))*10+ord(c1)-ord('0'); for j:=1 to K do if p[j]

81 Задача С Бейсик DIM p(1000) AS INTEGER DIM s AS STRING DIM nm AS STRING INPUT n INPUT k FOR i = 1 TO k p(i) = 0 NEXT i FOR j = 1 TO n LINE INPUT s c$ = MID$(s, 1, 1) i = 1 WHILE NOT (c$ = " ") i = i + 1 c$ = MID$(s, i, 1) WEND nm = MID$(s, 1, i) time1 = (ASC(MID$(s, i + 1, 1)) - ASC("0")) * 60 * 10 time1 = time1 + (ASC(MID$(s, i + 2, 1)) - ASC("0")) * 60 time1 = time1 + (ASC(MID$(s, i + 4, 1)) - ASC("0")) * 10 time1 = time1 + (ASC(MID$(s, i + 5, 1)) - ASC("0")) time2 = (ASC(MID$(s, i + 7, 1)) - ASC("0")) * 60 * 10 time2 = time2 + (ASC(MID$(s, i + 8, 1)) - ASC("0")) * 60 time2 = time2 + (ASC(MID$(s, i + 10, 1)) - ASC("0")) * 10 time2 = time2 + (ASC(MID$(s, i + 11, 1)) - ASC("0")) FOR i = 1 TO k IF time1 >= p(i) THEN p(i) = time2 PRINT nm, i GOTO 10 ENDIF NEXT i 10 NEXT j END = p(i) THEN p(i) = time2 PRINT nm, i GOTO 10 ENDIF NEXT i 10 NEXT j END">

82 Задача С Указания по оцениванию Максимальный балл 4. Программа работает верно, т.е. корректно выделяет из входных данных время, ищет первую свободную ячейку и распечатывает в случае успеха результат. Фамилии пассажиров и время сдачи багажа при этом не запоминаются. Допускается наличие в тексте программы одной синтаксической ошибки: пропущен или неверно указан знак пунктуации; неверно написано или пропущено зарезервированное слово языка программирования; не описана или неверно описана переменная; применяется операция, не допустимая для соответствующего типа данных. Допускается наличие одной из нерациональностей: сохраняются фамилии пассажиров; сохраняется как время сдачи багажа, так и время освобождения ячейки; до анализа данных очередного пассажира анализируется массив, соответствующий ячейкам камеры хранения на предмет освобождения ячеек к данному времени

83 Задача С Указания по оцениванию Задача оценивается в три балла. Программа работает в целом верно, но содержит, по крайней мере, две из указанных выше нерациональностей; допускается наличие до трёх синтаксических ошибок, описанных выше. Задача оценивается в два балла. Программа работает в целом верно, но не всегда определяет для хранения допустимую ячейку с минимальным номером или некорректно работает в случае отсутствия свободных ячеек. Возможно, в реализации алгоритма содержится одна-две ошибки (используется знак « », «or» вместо «and» и т.п.). Возможно, некорректно организовано считывание входных данных. Допускается до трёх ошибок в ходе решения задачи. Допускается наличие до пяти синтаксических ошибок, описанных выше.

84 Задача С Указания по оцениванию Один балл ставится, если решение возможно, содержит ошибку в определении свободной ячейки. Допускается до четырёх различных ошибок в ходе решения задачи, в том числе описанных в критериях. Допускается наличие до семи синтаксических ошибок, описанных выше. Задание выполнено неверно ставится 0 баллов.

85 Задача С Условие задачи У исполнителя Утроитель две команды, которым присвоены номера: 1. прибавь 1, 2. умножь на 3. Первая из них увеличивает число на экране на 1, вторая – утраивает его. Программа для Утроителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 29? Ответ обоснуйте.

86 Задача С Обозначим R(n) – количество программ, которые преобразуют число 1 в число n. Обозначим t(n) наибольшее кратное трем, не превосходящее n. Обе команды исполнителя увеличивают исходное число, поэтому общее количество команд в программе не может превосходить 28. Верны следующие соотношения: 1. Если n не делится на 3, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) – прибавлением единиц. 2. Пусть n делится на 3. Тогда R(n) = R(n/3)+R(n-1)= R(n/3)+R(n-3) (если n>3). При n=3 R(n) = 2 (два способа: прибавлением двух единиц или однократным умножением на 3).

87 Задача С Поэтому достаточно по индукции вычислить значения R(n) для всех чисел, кратных трем и не превосходящих 29. Имеем: R(2)=1 R(3) = 2 = R(4)=R(5) R(6) = R(2)+R(3) =1+2 = 3 = R(7)=R(8) R(9) = R(3)+R(6) =2+3 =5 = R(10)=R(11) R(12) = R(4)+R(9) = 2+5 = 7 = R(13)=R(14) R(15) = R(5)+R(12) =2+7 =9 = R(16)=R(17) R(18) = R(6)+R(15) = 3+9 = 12 = R(19)=R(20) R(21) = R(7)+R(18) = 3+12 = 15 = R(22)=R(23) R(24) = R(8)+R(21) = = 18 = R(25)=R(26) R(27) = R(9)+R(24) = = 23 = R(28)=R(29) Ответ: 23

88 Задача С Другой способ решения Будем решать поставленную задачу последовательно для чисел 1, 2, 3, …, 29 (то есть для каждого из чисел определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 1 в число n, будем обозначать через R(n). Число 1 у нас уже есть, значит, его можно получить с помощью пустой программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, R(1) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на три, то оно может быть получено только из предыдущего с помощью команды прибавь 1. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего числа: R(i) = R(i-1). Если число на 3 делится, то вариантов последней команды два: прибавь 1 и умножь на 3, тогда R(i) = R(i-1) + R(i/3).

89 Задача С Другой способ решения

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

91 Задача С Указания по оцениванию Один балл. Представленное решение обладает одним из свойств 1. Указано, что нужно рассматривать значения n, меньшие, чем 29, и приведены правильные рекуррентные соотношения, возможно, неполные. 2. Правильно выписаны и обоснованы значения R(n) для небольших n. 3. Правильно написан ответ, но нет его обоснования. 0 баллов. Не выполнено ни одно из перечисленных выше условий