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

Ваня, играют в следующую игру. Перед игроками лежат две

кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 73. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 73 камня или больше.
Игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (6, 34), (7, 33), (9, 32) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.

(8, 32) укажите, кто из игроков имеет выигрышную стратегию.

В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Решение:
Первый ход делает Петя.
Игрок выигрывает, когда суммарное количество камней в куче становится >= 73.
Будем считать, что прибавление одного камня в маленькую кучу — самый слабый ход, а увеличение в два раза большой кучи — самый сильный ход.
Петя первым ходом не может получить суммарное количество >=73, зато Ваня может, удвоив количество камней во второй куче после хода Пети:

7 + 2*33 = 73
6 + 2*66 = 138
9 + 2*32 = 73
8 + 2*64 = 136

То есть при позициях (6, 33) и (8, 32)  второй игрок (Ваня) выигрывает первым ходом. Так как Петя, получив такие позиции, проиграл, будем считать, что позиции (6, 33) и (8, 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) выигрышные, так как они достались Пете и Петя выиграл.

из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните,

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

Решение:
Рассмотрим все возможные ходы Пети из этой позиции:
(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: теория игр.

Петя выигрывает первым ходом.

Игрок выигрывает в том случае, когда количество

камней в куче больше или  равно 46.
Самый сильный ход, который может сделать Петя — увеличить количество камней в куче в два раза.
Получается, что минимальная выигрышная S будет равна:

46:2=23

То есть при S={23..45} Петя выигрывает первым ходом, просто умножив эти числа на два. 

Будем считать, что позиции S={23..45} — выигрышные, то есть любой игрок, у которого в куче появилось 23 или более камней выиграет.
 

Ваня выигрывает первым ходом при любой игре Пети.

Мы знаем, что

позиции 23..45 — выигрышные, значит Ваня может выиграть в том случае, если у Пети не останется другой возможности, кроме как сделать своим первым ходом количество камней в куче равным 23..45.
Самый слабый ход, который может сделать Петя — увеличить количество камней на один. Получается, что при S=22 Петя сделает выигрышную позицию для Вани:
22 + 1 = 23 — Ваня выиграет следующим ходом
22 + 3 = 25 — Ваня выиграет следующим ходом
22 * 2 = 44 — Ваня выиграет следующим ходом
То есть при S=22 Ваня выиграет, а Петя — проиграет. Будем считать, что позиция S=22 — проигрышная для любого игрока, кому она попадётся.

выиграть своим вторым ходом при любой игре Вани.

Мы знаем, что

позиция S=22 проигрышная, Петя ходит первым и он должен выиграть. То есть он должен сделать для Вани проигрышную позицию, то есть количество камней в куче после его хода должно стать равным 22. При том, что у Пети есть три возможных хода (+1, +3, *2), Петя может получить 22 камня в куче из следующих позиций S:

21 + 1 = 22
19 + 3 = 22
11 * 2 = 22

То есть Петя выиграет при S = 21, 19, 11, сделав количество камней в куче равным 22.
Будем считать, что позиции 21, 19, 11 выигрышные для любого игрока, у которого они появятся.

Тип заданий 26: теория игр.

выиграть своим первым или вторым ходом при любой игре

Пети.

Из пункта 2 решения мы знаем, что позиции 21, 19, 11 обеспечивают победу игроку вторым ходом. То есть мы должны найти такое S, чтобы у Пети не было другой возможности, кроме как сделать количество камней в куче равным или 21, или 19, или 11, или чтобы их количество было в диапазоне {23..45}.
Очевидно, что это число 18.
При любой игре Пети Ваня получит выигрышную позицию:
18 + 1 = 19 — выигрышная позиция
18 + 3 = 21 — выигрышная позиция
18 * 2 = 36 — выигрышная позиция

Тип заданий 26: теория игр.

перекрёстке, фиксирует количество проезжающих автомобилей, и каждую минуту по

каналу связи передаёт неотрицательное целое число — количество автомобилей, проехавших перекрёсток за эту минуту. Известно, что за минуту перекрёсток может проехать не более 100 автомобилей. Необходимо найти в заданной серии показаний максимальное количество автомобилей, проехавших перекрёсток в течение пяти подряд идущих минут. Максимальное количество показаний, которое может передать камера, не превышает 1440.
Напишите на любом языке программирования программу для решения поставленной задачи. Для получения максимального результата программа должна быть эффективна по времени и по используемой памяти.
Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество переданных показаний. Гарантируется, что N>5. В каждой из следующих N строк задаётся одно положительное целое число – очередное показание камеры.

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

минут.
Пример выходных данных для приведённого выше примера входных данных: 103

Тип заданий 27: разработка программы

том, чтобы объявить массив с максимально возможным количеством элементов

— 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 do begin    for j:=0 to 4 do       s := s+a[i+j];       if s > max then          max := s;       s := 0; end;
Выводим значение переменной max:
writeln(max);

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.
Данная программа не является эффективной по памяти, так как хранит все введенные данные.

не использовать такой огромный массив, достаточно хранить в памяти всего

пять значений, сумму которых мы находим:
var a: array[1..5] of byte;
Сначала введем N и считаем в массив первые пять значений, при этом сразу можно найти и их сумму:
readln(n); for i:=1 to 5 do begin    readln(a[i]);    s := s+a[i]; end;
Сразу же присвоим переменной max значение s:
max := s;
Теперь введём оставшиеся значения. Для этого будем использовать последний (пятый) элемент массива, предварительно сдвинув все элементы на один влево:
for i:=6 to N do begin    for j:=1 to 4 do //сдвиг массива      a[j] := a[j+1];    readln(a[5]);

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]

Остаётся сравнить значение переменной s с max:

if s > max then    max :=s;

Сумму элементов мы можем посчитать, вычтя из предыдущей суммы первый элемент до сдвига, и прибавив к ней введённый элемент после сдвига:

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.

Лещинер В.Р. ЕГЭ 2016. Информатика. Типовые тестовые задания. — М.:

Экзамен, 2015.
         Крылов С.С., Ушаков Д.М. ЕГЭ 2016. Информатика. Тематические тестовые задания. — М.: Экзамен, 2015.
         Ушаков Д.М. ЕГЭ-2016. Информатика. 20 типовых вариантов экзаменационных работ для подготовки к ЕГЭ. — М.: Астрель, 2015.
Ройтберг М.А., Зайдельман Я.Р. Информатика. Подготовка к ЕГЭ в 2016 году. Диагностические работы. — М.: МЦНМО, 2015.
Самылкина Н.Н., Синицкая И.В., Соболева В.В., ЕГЭ 2016. Информатика. Тематические тренировочные задания. — М.: Эксмо, 2015.
Зорина Е.М., Зорин М.В. ЕГЭ 2016. Информатика. Сборник заданий. — М.: «Эксмо», 2015.
Крылов С.С., Чуркина Т.Е. ЕГЭ 2016. Информатика и ИКТ. Типовые экзаменационные варианты. — М.: «Национальное образование», 2015.
Богомолова О.Б. ЕГЭ Информатика. Новый полный справочник.— М.: АСТ, 2015.

и программное обеспечение

Пашковой»