ПОДГОТОВКА К ЕГЭ-2014 ПО ИНФОРМАТИКЕ Старший преподаватель кафедры информационных технологий Яковенко Роман Геннадьевич Краснодарский краевой институт. - презентация

1 ПОДГОТОВКА К ЕГЭ-2014 ПО ИНФОРМАТИКЕ Старший преподаватель кафедры информационных технологий Яковенко Роман Геннадьевич Краснодарский краевой институт дополнительного профессионального педагогического образования

2 Задание C1

3

4 Nmax_digitdigit 1 При вводе числа 423 программа выведет число

5 Задание C1 Nmax_digitdigit 2 Строку max_digit := 9 заменить на max_digit := 0 Строку while N >= 10 do заменить на while N > 0 do Инициализация заведомо максимальным значением Старший разряд не обрабатывается Неверное выделение младшего разряда Неправильный знак неравенства Неправильное отбрасывание младшего разряда Неправильный вывод, например, writeln(digit);

6 Задание C1 Внимательно читайте условие Выполняйте ровно то, что от Вас просят Не переписывайте программу целиком, укажите лишь неправильные строки Укажите явно: строка … не верна. Необходимо заменить на … Не ищите ошибок там, где их нет

7 Задание C2 Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести максимальное значение среди трёхзначных элементов массива, не делящихся на 9. Если в исходном массиве нет элемента, значение которого является трёхзначным числом и при этом не кратно 9, то выведите сообщение «Не найдено». Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных. В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Free Pascal 2.4) или в виде блок-схемы. В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).

8 Задание C2 максимальное значение среди трёхзначных элементов массива, не делящихся на 9 Стандартный алгоритм поиска максимума: max := a[1]; for i := 2 to N do if a[i] > max then max := a[i]; writeln(max);..могут принимать целые значения от 0 до включительно.. max := 99; {может быть любое, меньшее 100} for i := 1 to N do if(a[i] >= 100) and (a[i] max) then max := a[i]; if max = 99 then writeln(Не найдено) else writeln(max); Решение Если в исходном массиве нет элемента, значение которого является трёхзначным числом и при этом не кратно 9, то выведите сообщение «Не найдено»

9 Задание C3 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 27. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 27 или больше камней. В начальный момент в куче было S камней, 1 S 26.

10 Задание C3 Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Выигрышная стратегия игрока А должна содержать все возможные ходы игрока В (он может противостоять любыми способами) и только выигрышные ходы игрока А. На любой ход игрока В должен быть указан ровно один выигрышный ход игрока А. XXa1 Xb11 Xb12 Xb13 C1 C2 C3 Xa21 C2 Xa22 C1 Xa23 C1 А I B I А II

11 Задание C *2 Ответ S 14 Выигрывающий ход: увеличить количество камней в куче в два раза. При этом камней станет 2 * S 28. При S 13 Петя никак не получит больше 26 камней, а значит не выиграет в один ход. >=27 1. а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S. Замечания Ни в коем случае не перечислять: S = 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 Можно не указывать верхнюю границу S 26: она задана по условию Обязательно укажите выигрывающий ход Пети

12 Задание C *2 Ответ S 14 Выигрывающий ход: увеличить количество камней в куче в два раза. При этом камней станет 2 * S 28. При S 13 Петя никак не получит больше 26 камней, а значит не выиграет в один ход а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S. Замечания Ни в коем случае не перечислять: S = 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 Можно не указывать верхнюю границу S 26: она задана по условию Обязательно укажите выигрывающий ход Пети S 26 S S S * 2 27 S 26 S 25 S 13,5 14 S 26 Можно формализовать решение: Укажите один выигрывающий ход Пети для всех S (не надо отдельно для 25 и 26)

13 Задание C *2 Ответ S = 13 Выигрывающий ход: независимо от хода Пети, Ваня своим первым ходом должен увеличить количество камней в куче в два раза б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани. Соображения Исходя из п. 1а, чтобы Петя не выиграл в один ход, S должно быть меньше, чем 14 Чтобы Ваня выиграл своим первым ходом, исходя из п. 1а, после хода Пети камней должно быть не меньше, чем 14. Поскольку возможны ходы «+1», «+2» и «*2», единственным возможным значением S является 13. Иначе, если S 13 (например 12), то Петя может ходом «+1» получить количество камней не превосходящее 13 (например 13) и тогда Ваня не выиграет своим первым ходом. S < 14 S S S * 2 14 S < 14 S 13 S 12 S 7 S = 13 Можно формализовать решение:

14 Задание C * Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть за один ход и (б) Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети. Соображения Исходя из п. 1б, чтобы Петя выиграл своим вторым ходом, после его первого хода камней должно быть 13. Задача Пети – своим первым ходом привести количество камней к 13. Возможны ходы «+1», «+2» и «*2», с помощью которых Петя будет доводить количество камней до 13. Поэтому возможны следующие значения S: S = 12, тогда Петя должен пойти «+1» S = 11, тогда Петя должен пойти «+2» Ход «*2» невозможен, поскольку нет целого числа, которое при умножении на 2 дает 13

15 Задание C *2 Ответ (вариант 1) S = 11, S = 12 Выигрышная стратегия: 1) Первым ходом Петя должен привести количество камней к 13. 2) Вторым ходом, независимо от первого хода Вани, Петя должен увеличить количество камней в куче в два раза Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть за один ход и (б) Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети. Ответ (вариант 2) S = 11, S = 12 Выигрышная стратегия видна из дерева игры, в котором указаны все возможные ходы Вани и только выигрышные ходы Пети: *2 28 *2 30 *2 52 *2 П I В I П II 12 +1

16 Задание C * Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть за один ход и (б) Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети. S + 1 = 13 S + 2 = 13 S * 2 = 13 S = 12 S = 11 S = 6,5 Можно формализовать решение:

17 Задание C * Укажите значение S, при котором: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах – количество камней в куче. Соображения Исходя из п. 2, чтобы Ваня выиграл своим вторым ходом, после первого хода Пети камней должно быть 11 или 12 (либо не менее 14). Возможны ходы «+1», «+2» и «*2», после которых Петя должен попасть в указанные выше значения. Поэтому возможно единственное значение S = 10. Тогда: Если Петя пойдет «+1» или «+2» - попадаем в условия п. 2 Если Петя пойдет «*2» - попадаем в условия п. 1а

18 Задание C *2 27 Ответ (для п. 3) S = 10 Выигрышная стратегия видна из дерева игры, в котором указаны все возможные ходы Пети и только выигрышные ходы Вани: *2 28 *2 30 *2 52 *2 П I В I П II *2 В II

19 Задание C3 Ответ 1. а) S 14. Выигрывающий ход: увеличить количество камней в куче в два раза. При этом камней станет 2 * S 28. При S 13 Петя никак не получит больше 26 камней, а значит не выиграет в один ход. б) S = 13 Выигрывающий ход: независимо от хода Пети, Ваня своим первым ходом должен увеличить количество камней в куче в два раза. 2. S = 11, S = 12 Выигрышная стратегия: 1) Первым ходом Петя должен привести количество камней к 13. 2) Вторым ходом, независимо от первого хода Вани, Петя должен увеличить количество камней в куче в два раза. 3. S = 10 Выигрышная стратегия видна из дерева игры, в котором указаны все возможные ходы Пети и только выигрышные ходы Вани: (изображенное дерево игры)

20 Задание C4 По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности – наибольшее число R, удовлетворяющее следующим условиям: 1) R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел; допускаются произведения различных элементов последовательности, равных по величине); 2) R делится на 21. Если такого числа R нет, то контрольное значение полагается равным 0. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.

21 Задание C4 Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме: Вычисленное контрольное значение: … Контроль пройден (или – Контроль не пройден) Перед текстом программы кратко опишите используемый Вами алгоритм решения. На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее В последней строке записано контрольное значение.

22 Задание C4 Пример входных данных: Пример выходных данных для приведённого выше примера входных данных: Вычисленное контрольное значение: Контроль пройден

23 Задание C4 Соображения R – произведение двух различных переданных элементов последовательности R делится на 21 N*M=21*K, следовательно возможны варианты: 1)Одно из чисел N и M делится на 21. 2)Одно из чисел делится на 7, другое – на 3 Произведение будет наибольшим, когда сомножители принимают максимально возможные значения. наибольшее число R Вывод Необходимо найти две пары различных элементов массива: 1)Наибольший элемент, делящийся на 21 и отличный от него наибольший из оставшихся элементов. 2)Наибольший элемент, делящийся на 7 и отличный от него наибольший элемент, делящийся на 3. Таким образом, вводим переменные max, max21, max7 и max3. Каждый из поступающих на вход элементов сравниваем с ними и при необходимости сохраняем.

24 Задание C4 Замечания Если текущий элемент массива делится на 21 и превосходит max21 (сохраняем его в max21), то его сравнение с max необходимо исключить – вложенный условный оператор. Если текущий элемент массива делится на 7 и превосходит max7 (сохраняем его в max7), то его сравнение с max3 необходимо исключить – вложенный условный оператор. Вывод Необходимо найти две пары различных элементов массива: 1)Наибольший элемент, делящийся на 21 и отличный от него наибольший из оставшихся элементов. 2)Наибольший элемент, делящийся на 7 и отличный от него наибольший элемент, делящийся на 3. Таким образом, вводим переменные max, max21, max7 и max3. Каждый из поступающих на вход элементов сравниваем с ними и при необходимости сохраняем. Если текущий элемент массива делится на 21 и превосходит max21, то перед его сохраняем в max21 необходимо проверить, не содержится ли в max21 текущий максимум по всем элементам. Если да, то сначала max21 сохранить в max, а затем текущий элемент в max21.

25 Задание C4 Главное замечание!!! Чтобы научиться программировать нужно программировать!

26 Желаем успехов!