Презентация к семинару методического объединения учителей информатики г.Арзамас

Решение задач ЕГЭ повышенной сложностиПервушкина Елена Александровна,доцент кафедры ФМО АФ ННГУ Тип заданий 26: теория игр.Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 73. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 73 камня или больше.Игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (6, 34), (7, 33), (9, 32) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче. Задание 1. Для каждой из начальных позиций (6, 33), (8, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.Решение:Первый ход делает Петя.Игрок выигрывает, когда суммарное количество камней в куче становится >= 73. Будем считать, что прибавление одного камня в маленькую кучу — самый слабый ход, а увеличение в два раза большой кучи — самый сильный ход.Петя первым ходом не может получить суммарное количество >=73, зато Ваня может, удвоив количество камней во второй куче после хода Пети:7 + 2*33 = 736 + 2*66 = 1389 + 2*32 = 738 + 2*64 = 136То есть при позициях (6, 33) и (8, 32)  второй игрок (Ваня) выигрывает первым ходом. Так как Петя, получив такие позиции, проиграл, будем считать, что позиции (6, 33) и (8, 32) проигрышные, и игрок, которому они достанутся, проиграет. Задание 2. Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.Решение:Первый ход делает Петя. Чтобы выиграть, он должен стараться сделать так, чтобы Ване досталась проигрышная позиция. Мы знаем две проигрышные позиции из пункта 1 — (6, 33) и (8, 32). Эти проигрышные позиции Петя может сделать своим первым ходом для Вани из предложенных позиций:(6, 32) -> (6, 33)(7, 32) -> (8, 32)(8, 31) -> (8, 32)То есть, Петя сделал для Вани проигрышную позицию, в результате чего Ваня проиграет, а Петя выиграет своим вторым ходом. Будем считать, что позиции (6, 32), (7, 32), (8, 31) выигрышные, так как они достались Пете и Петя выиграл. Задание 3. Для начальной позиции (7, 31) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.Решение:Рассмотрим все возможные ходы Пети из этой позиции:(7, 31) -> (8, 31)(7, 31) -> (7, 32)(7, 31) -> (14, 31)(7, 31) -> (7, 62)То есть Ване могут достаться позиции (8, 31), (7, 32), (14, 31), (7, 62). (8, 31) — выигрышная позиция, исходя из пункта 2 решения;(7, 32) — выигрышная позиция, исходя из пункта 2 решения;(14, 31) — Ваня выиграет, умножив 31 на 2;(7, 62) — Ваня выиграет, умножив 62 на 2..Все позиции, которые достались Ване — выигрышные. При позициях (8, 31) и (7,32) Ване потребуется сделать два хода для победы. То есть при начальной позиции (7, 31) Ваня выиграет максимум двумя ходами. Два игрока, Петя и Ваня, играют в игру. Перед ними лежит куча камней. Игроки ходят по очереди. Первый ход делает Петя. За один ход игрок может добавить в кучу один камень, три камня, или увеличить количество камней в куче в два раза. Для того, чтобы сделать ход, у игроков имеется неограниченное количество камней. Игра завершается, когда количество камней в куче превышает 46. Победителем становится игрок, сделавший последний ход, и получивший в куче 46 или более камней. В начальный момент в куче было S камней, 1≤ S ≤ 45. Последовательно решите следующие задания:1) При каких S: а) Петя выигрывает первым ходом; б) Ваня выигрывает первым ходом при любой игре Пети.2) Назовите три значения S, при которых Петя может выиграть своим вторым ходом при любой игре Вани.3) Назовите такое значение S, при котором Ваня может выиграть своим первым или вторым ходом при любой игре Пети.Тип заданий 26: теория игр. Тип заданий 26: теория игр.Решение: 1а. При каких S Петя выигрывает первым ходом.Игрок выигрывает в том случае, когда количество камней в куче больше или  равно 46. Самый сильный ход, который может сделать Петя — увеличить количество камней в куче в два раза. Получается, что минимальная выигрышная S будет равна:46:2=23То есть при S={23..45} Петя выигрывает первым ходом, просто умножив эти числа на два. Будем считать, что позиции S={23..45} — выигрышные, то есть любой игрок, у которого в куче появилось 23 или более камней выиграет.  Тип заданий 26: теория игр.1б. При каких S Ваня выигрывает первым ходом при любой игре Пети.Мы знаем, что позиции 23..45 — выигрышные, значит Ваня может выиграть в том случае, если у Пети не останется другой возможности, кроме как сделать своим первым ходом количество камней в куче равным 23..45.Самый слабый ход, который может сделать Петя — увеличить количество камней на один. Получается, что при S=22 Петя сделает выигрышную позицию для Вани:22 + 1 = 23 — Ваня выиграет следующим ходом22 + 3 = 25 — Ваня выиграет следующим ходом22 * 2 = 44 — Ваня выиграет следующим ходомТо есть при S=22 Ваня выиграет, а Петя — проиграет. Будем считать, что позиция S=22 — проигрышная для любого игрока, кому она попадётся. 2. Назовите три значения S, при которых Петя может выиграть своим вторым ходом при любой игре Вани.Мы знаем, что позиция S=22 проигрышная, Петя ходит первым и он должен выиграть. То есть он должен сделать для Вани проигрышную позицию, то есть количество камней в куче после его хода должно стать равным 22. При том, что у Пети есть три возможных хода (+1, +3, *2), Петя может получить 22 камня в куче из следующих позиций S:21 + 1 = 2219 + 3 = 2211 * 2 = 22То есть Петя выиграет при S = 21, 19, 11, сделав количество камней в куче равным 22. Будем считать, что позиции 21, 19, 11 выигрышные для любого игрока, у которого они появятся.Тип заданий 26: теория игр. 3. Назовите все значения S, при которых Ваня может выиграть своим первым или вторым ходом при любой игре Пети.Из пункта 2 решения мы знаем, что позиции 21, 19, 11 обеспечивают победу игроку вторым ходом. То есть мы должны найти такое S, чтобы у Пети не было другой возможности, кроме как сделать количество камней в куче равным или 21, или 19, или 11, или чтобы их количество было в диапазоне {23..45}.Очевидно, что это число 18. При любой игре Пети Ваня получит выигрышную позицию:18 + 1 = 19 — выигрышная позиция18 + 3 = 21 — выигрышная позиция18 * 2 = 36 — выигрышная позицияТип заданий 26: теория игр. Тип заданий 27: разработка программыСпециальная камера, установленная на перекрёстке, фиксирует количество проезжающих автомобилей, и каждую минуту по каналу связи передаёт неотрицательное целое число — количество автомобилей, проехавших перекрёсток за эту минуту. Известно, что за минуту перекрёсток может проехать не более 100 автомобилей. Необходимо найти в заданной серии показаний максимальное количество автомобилей, проехавших перекрёсток в течение пяти подряд идущих минут. Максимальное количество показаний, которое может передать камера, не превышает 1440.Напишите на любом языке программирования программу для решения поставленной задачи. Для получения максимального результата программа должна быть эффективна по времени и по используемой памяти.Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество переданных показаний. Гарантируется, что N>5. В каждой из следующих N строк задаётся одно положительное целое число – очередное показание камеры. Пример входных данных:85122710450716Программа выводит только одно число – наибольшее количество автомобилей, проехавших перекресток за пять подряд идущих минут.Пример выходных данных для приведённого выше примера входных данных:103Тип заданий 27: разработка программы Решение на 2 балла:Первый вариант решения заключается в том, чтобы объявить массив с максимально возможным количеством элементов — 1440:var a: array[1..1440] of byte;Далее вводится значение N и считаются данные в массив:for i:=1 to N do   readln(a[i]);Теперь с помощью вложенных циклов будем находить сумму пяти текущих элементов, и сравнивать её с максимальным значением. При этом каждый повтор первого цикла переменную S будем обнулять:for i:=1 to N-4 dobegin   for j:=0 to 4 do      s := s+a[i+j];      if s > max then         max := s;      s := 0;end;Выводим значение переменной max:writeln(max); Полное решение:vara: array[1..1440] of byte;i, j, N, max, s: integer;begin   readln(N);   for i:=1 to N do      readln(a[i]);   max := 0; s := 0;   for i:=1 to N-4 do   begin      for j:=0 to 4 do         s := s+a[i+j];      if s > max then         max := s;      s := 0;   end;   writeln(max);   end.Данная программа не является эффективной по памяти, так как хранит все введенные данные. Решение на 4 балла:Для решения задания мы можем не использовать такой огромный массив, достаточно хранить в памяти всего пять значений, сумму которых мы находим:var a: array[1..5] of byte;Сначала введем N и считаем в массив первые пять значений, при этом сразу можно найти и их сумму:readln(n);for i:=1 to 5 dobegin   readln(a[i]);   s := s+a[i];end;Сразу же присвоим переменной max значение s:max := s;Теперь введём оставшиеся значения. Для этого будем использовать последний (пятый) элемент массива, предварительно сдвинув все элементы на один влево:for i:=6 to N dobegin   for j:=1 to 4 do //сдвиг массива     a[j] := a[j+1];   readln(a[5]); То есть теперь код будет выглядеть так:for i:=6 to N dobegin  s := s — a[1];  for j:=1 to 4 do    a[j] := a[j+1];  readln(a[5]);  s := s + a[5]Остаётся сравнить значение переменной s с max:if s > max then   max :=s;Сумму элементов мы можем посчитать, вычтя из предыдущей суммы первый элемент до сдвига, и прибавив к ней введённый элемент после сдвига: Полное решение:vara: array[1..5] of integer;s, i, j, max, N: integer;begin   readln(n);   s := 0;   for i:=1 to 5 do   begin      readln(a[i]);      s := s+a[i];   end;   max := s;   for i:=6 to N do   begin      s := s — a[1];      for j:=1 to 4 do         a[j] := a[j+1];      readln(a[5]);      s := s + a[5];      if s > max then         max :=s;   end;   writeln(max);end. Тип заданий 27: разработка программы Тип заданий 27: разработка программы Дисциплины изучаемыепо профилю Информатика{5FD0F851-EC5A-4D38-B0AD-8093EC10F338}Теоретические основы информатикиЧисленные методыПрактикум решения задач школьного курса информатикиОсновы искусственного интеллектаМетоды и средства защиты информацииИнформационные системыАрхитектура компьютераКомпьютерное моделированиеПрограммированиеПрактикум по решению задач на ЭВМПрограммное обеспечение ЭВМИнформатизация управления образовательным процессом Литература для подготовки к ЕГЭ   Лещинер В.Р. ЕГЭ 2016. Информатика. Типовые тестовые задания. — М.: Экзамен, 2015.          Крылов С.С., Ушаков Д.М. ЕГЭ 2016. Информатика. Тематические тестовые задания. — М.: Экзамен, 2015.          Ушаков Д.М. ЕГЭ-2016. Информатика. 20 типовых вариантов экзаменационных работ для подготовки к ЕГЭ. — М.: Астрель, 2015. Ройтберг М.А., Зайдельман Я.Р. Информатика. Подготовка к ЕГЭ в 2016 году. Диагностические работы. — М.: МЦНМО, 2015. Самылкина Н.Н., Синицкая И.В., Соболева В.В., ЕГЭ 2016. Информатика. Тематические тренировочные задания. — М.: Эксмо, 2015. Зорина Е.М., Зорин М.В. ЕГЭ 2016. Информатика. Сборник заданий. — М.: «Эксмо», 2015. Крылов С.С., Чуркина Т.Е. ЕГЭ 2016. Информатика и ИКТ. Типовые экзаменационные варианты. — М.: «Национальное образование», 2015. Богомолова О.Б. ЕГЭ Информатика. Новый полный справочник.— М.: АСТ, 2015. Сайты для подготовки к ЕГЭhttp://kpolyakov.spb.ru/school/ege.htm - Методические материалы и программное обеспечение http://www.fipi.ru/ - Федеральный институт педагогических измерений http://infbu.ru/ - Информатик БУ http://inf.reshuege.ru/- Решу ЕГЭ Сайты для учителя информатикиpedsovet.su - «Педагогическое сообщество Екатерины Пашковой» http://videouroki.net –Видеоуроки в Интернет http://www.metod-kopilka.ru/informatika.html- Методическая копилка http://nashol.com/informatika-i-komputeri/ - Учебники и книги