Решение задач 19 21 егэ по информатике с помощью excel

На уроке рассмотрен разбор 19, 20, 21 задания ЕГЭ по информатике: дается подробное объяснение и решение задания.

Читать текстовую версию — https://labs-org.ru/ege-19/

Объяснение заданий 19, 20 и 21 ЕГЭ по информатике

19-е задание: «Анализ алгоритма логической игры»

Уровень сложности — повышенный,

Требуется использование специализированного программного обеспечения — нет,

Максимальный балл — 1,

Примерное время выполнения — 6 минут.

Проверяемые элементы содержания: Умение анализировать алгоритм логической игры

20-е задание: «Поиск выигрышной стратегии»

Уровень сложности — повышенный,

Требуется использование специализированного программного обеспечения — нет,

Максимальный балл — 1,

Примерное время выполнения — 6 минут.

Проверяемые элементы содержания: Умение найти выигрышную стратегию игры

21-е задание: «Дерево игры для выигрышной стратегии»

Уровень сложности — повышенный,

Требуется использование специализированного программного обеспечения — нет,

Максимальный балл — 1,

Примерное время выполнения — 10 минут.

Проверяемые элементы содержания: Умение построить дерево игры по заданному алгоритму и найти выигрышную стратегию

Решение заданий 19-21 (Теория игр) из ЕГЭ по Информатике. Решение на Python, т.к. он наиболее популярен среди сдающих ЕГЭ

Зачем это сделал?

Серфил интернет, находил какую то чепуху их серии «Решим как с помощью Excel». В самом задании уже нам дам намек, что рекурсивное решение плавает на поверхности. Вот пожалуйста

Что тут есть

Здесь реализованы решения для заданий как с одной кучей, так и для заданий с двумя. С тремя и больше я не видел, да и вряд ли дадут такое в ЕГЭ, но доработать легко

Категория

Programming

Разбор заданий 19,20,21 ЕГЭ по информатике в Excel.

Задание 19.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10камней, а в другой 5 камней; такую позицию в игре будем обозначать (10,5). Тогда за один ход можно получить любую из четырёх позиций: (11,5), (20,5), (10,6), (10,10). Для того чтобы делать ход, у каждого игрока есть неограниченное количество камней.

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

В начальный момент впервой куче было семь камней, вовторой куче – S камней: 1S69

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

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

Решение.

Поскольку у нас 2 кучикамней, будем использовать 2 ячейки. В ячейку A4 введём 7 (количество камней в первой куче) и поскольку количество камней во второй куче неизвестно, введём в ячейкуB4 Excelпроизвольное число, например 10. Распишем ходы Пети.

Для того чтобы Ваня гарантировано выиграл первым ходом, последний ход его должен быть самым сильным. Для этого количество камней из кучи с максимальным количеством камней умножаем на 2 и прибавляем количество камней из другой кучи. В ячейку E4 вводим формулу

=МАКС(C4:D4)*2 + МИН(C4:D4). Копируем эту формулу в ячейки E5:E7.

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

И

Для наглядности выполним условное форматирование. Выделим ячейки E4:E7. Выбираем Условное форматирование – Правила выделения ячеек – другие правила – значения 77 – форма – заливка – зеленая – ОК — ОК

такое количество камней во второй куче будет равно 18.

Задание 20. Для игры, описанной в предыдущем задании, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Ответ:

Решение.

Введём в ячейку A10количество камней в первой куче — 7, в ячейку B10 – количество камней во второй куче, т.к. количество камней во второй куче неизвестно, введём 10 (число произвольное). Скопируем таблицу, полученную в первом задании, в ячейку C9.

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

При S=10 Петя выигрывает своим вторым ходом только при одном ходе Вани (7,40), а нам надо, чтобы Петя после своего первого хода при любом ходе Вани выигрывал своим вторым ходом, т.е. нам нужно найти такое S, при котором все вторые ходы Пети в одном из прямоугольников были 77. Кроме того, нам надо будет следить за последним ходом Вани, т.к. может случиться так,что Петя выигрывает своим вторым ходом, но до этого побеждает Ваня. Для этого создадим дополнительный столбец, в который будем записывать сумму камней в двух кучах у Вани и следить, чтобы это значение было 77. В ячейку H10вводим формулу =E10 + F10и копируем её в ячейки H11:H25. Для наглядности выполним условное форматирование.

Меняя значение Sво второй куче, находим решение задачи. Первое значение S=31 ивторое значение S=34

Ответ: 3134

Задание 21.

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

— у Вани естьвыигрышная стратегия,позволяющая ему выиграть первым иливторым ходом при

любой игре Пети;

— у Вани нет стратегии,которая позволит ему гарантированно выиграть первым ходом.

Решение.

Скопируем таблицу из второго задания в ячейку K3 и снова поменяем местами Петя, Ваня, Петя. В ячейку I4 введём количество камней в первой куче, в ячейку J4 – число, например, 10 (количество камней во второй куче). Тогда при первом ходе Пети K4 =I4+1, L4=J4.

Выделим данный фрагмент таблицы жирным. Так как Петя не должен выиграть своим первым ходом, скопируем полученную таблицу ещё 3 раза. Введём формулы в ячейкиK20=I4, L20=J4+1, K36=I4*2, L36=J4, K52=I4, L52=J4*2. Также надо проверить, не выиграет ли Ваня своим первым ходом. Для этого в ячейку M5 введём формулу =M4+N4. Скопируем эту формулу в ячейкиM9, M13,M17, M21, M25, M29, M33, M37, M41, M45, M49. Снова будем проверять, используя условное форматирование. Меняя значение вячейке J4, находим такое минимальное S, при которому Вани естьвыигрышная стратегия,позволяющая ему выиграть первым иливторым ходом прилюбой игре Пети;у Вани нет стратегии,которая позволит ему гарантированно выиграть первым ходом.

Теория игр

19

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень, увеличить количество камней в первой куче в два раза или увеличить количество камней во второй куче в три раза. Например, пусть в одной куче 6 камней, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (7, 9), (12, 9), (6, 10), (6, 27). Чтобы делать

ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в первой куче было 10 камней, во второй куче — S камней, 1 ≤ S ≤ 58.

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

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

def f(x, y, p): #Рекурсивная функция
	if x + y >= 69 or p > 3: #Условия завершения игры
		return p == 3
	return f(x + 1, y, p + 1) or f(x, y + 1, p + 1) or
		   f(x * 2, y, p + 1) or f(x, y * 3, p + 1) #Варианты действий

for s in range (1, 58 + 1): #Перебор S
	if f(10, s, 1): #Начали с 10 камней
		print(s)
		break
20

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень, увеличить количество камней в первой куче в два раза или увеличить количество камней во второй куче в три раза. Например, пусть в одной куче 6 камней, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (7, 9), (12, 9), (6, 10), (6, 27). Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в первой куче было 10 камней, во второй куче — S камней, 1 ≤ S ≤ 58.

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

Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

def f(x, y, p): #Рекурсивная функция
	if x + y >= 69 or p > 4: #Условия завершения игры
		return p == 4
	if p % 2 != 0:
		return f(x + 1, y, p + 1) or f(x, y + 1, p + 1) or
			   f(x * 2, y, p + 1) or f(x, y * 3, p + 1) #Варианты действий
	else:
		return f(x + 1, y, p + 1) and f(x, y + 1, p + 1) and
			   f(x * 2, y, p + 1) and f(x, y * 3, p + 1) #Варианты действий


for s in range (1, 58 + 1): #Перебор S
	if f(10, s, 1): #Начали с 10 камней
		print(s)

19 - 2 кучи
def e(x1,x2,s):
    if x1+x2>=77 and s==3:
        return True
    else:
        if x1+x2<77 and s==3:
            return False
    return e(x1+1,x2,s+1) or e(x1,x2+1,s+1) or e(x1*2,x2,s+1) or e(x1,x2*2,s+1)

for i in range (1,150+1):
    if e(7,i,1):
        print(i)
        break
20 - 2 кучи
def e(x1,x2,s):
    if x1+x2>=77 and s==4:
        return True
    else:
        if x1+x2<77 and s==4:
            return False
        else:
            if x1+x2>=77:
                return False

    if s%2==1:
        return e(x1+1,x2,s+1) or e(x1,x2+1,s+1) or e(x1*2,x2,s+1) or e(x1,x2*2,s+1)
    else:
        return e(x1+1,x2,s+1) and e(x1,x2+1,s+1) and e(x1*2,x2,s+1) and e(x1,x2*2,s+1)        

for i in range (1,150+1):
    if e(7,i,1):
        print(i)

21

def f(x,y,p):
    if x+y>=142 and (p==5 or p==3):
        return True
    else:
        if x+y<142 and p==5:
            return False
        else:
            if x+y>=142:
                return False              
    if p%2==0:
        return f(x+2,y,p+1) or f(x*2,y,p+1) or f(x,y+2,p+1) or f(x,y*2,p+1)
    else:
        return f(x+2,y,p+1) and f(x*2,y,p+1) and f(x,y+2,p+1) and f(x,y*2,p+1)        

def f1(x,y,p):
    if x+y>=142 and p==3:
        return True
    else:
        if x+y<142 and p==5:
            return False
        else:
            if x+y>=142:
                return False              
    if p%2==0:
        return f1(x+2,y,p+1) or f1(x*2,y,p+1) or f1(x,y+2,p+1) or f1(x,y*2,p+1)
    else:
        return f1(x+2,y,p+1) and f1(x*2,y,p+1) and f1(x,y+2,p+1) and f1(x,y*2,p+1)        


for i in range(1,150+1):
    if f(2,i,1):
        print (i)

for i in range(1,150+1):
    if f1(2,i,1):
        print (i)

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень, увеличить количество камней в первой куче в два раза или увеличить количество камней во второй куче в три раза. Например, пусть в одной куче 6 камней, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (7, 9), (12, 9), (6, 10), (6, 27). Чтобы делать

ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в первой куче было 10 камней, во второй куче — S камней, 1 ≤ S ≤ 58.

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

Найдите минимальное значение S, при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

def f(x, y, p): #Рекурсивная функция
	if x + y >= 69 or p > 5: #Условия завершения игры
		return p == 3 or p == 5
	if p % 2 == 0:
		return f(x + 1, y, p + 1) or f(x, y + 1, p + 1) or
			   f(x * 2, y, p + 1) or f(x, y * 3, p + 1) #Варианты действий
	else:
		return f(x + 1, y, p + 1) and f(x, y + 1, p + 1) and
			   f(x * 2, y, p + 1) and f(x, y * 3, p + 1) #Варианты действий

for s in range (1, 58 + 1): #Перебор S
	if f(10, s, 1): #Начали с 10 камней
		print(s)

1.

РЕШЕНИЕ ЗАДАНИЙ 19-21
ПРОГРАММИРОВАНИЕМ
суммарное время решения задач 19-21: 22 минуты

2.

ПОРЯДОК РЕШЕНИЯ
Если Вы собираетесь решать задания 19-21 через программирование, то есть 2
варианта:
• начинать решать не с 19-го задания, а с 20-го или с 21-го;
• решить 19-е задание на бумажке, 20 и 21 – через программу.
В любом случае полученные программой ответы нужно проверить вручную,
т.к. в программе нельзя задать условия вот такого типа:
• Петя не может выиграть за один ход, но может выиграть своим вторым
ходом независимо от того, как будет ходить Ваня;
• у Вани нет стратегии, которая позволит ему гарантированно выиграть
первым ходом, но есть выигрышная стратегия, позволяющая ему выиграть
первым или вторым ходом при любой игре Пети.
И в том, и в другом случае программа выдаёт одинаковые числа (2 хода), т.е.
проверять возможность выигрыша за 1 ход нужно самостоятельно.

3.

О ПРОГРАММЕ
Есть несколько способов написать программу для решения задачи,
наиболее оптимальной по времени будет программа, решающая задачу
с помощью динамического программирования и сохраняющая
результаты в таблицу. В программе оба игрока не допускают ошибок
при игре, т.е. её можно использовать как для определения выигрышных
позиций как Вани, так и Пети.
Те места в программе, которые нужно будет менять в зависимости от
условий задачи, будут выделены жёлтым маркером. Всё остальное
остаётся неизменным (по крайней мере для решения задач 20-21).
Значения чисел в итоговой таблице:
Х – выигрыш Пети за Х ходов (например, 2 это выигрыш Пети за 2 хода);
-X – выигрыш Вани за Х ходов (например, -3 это выигрыш Вани за 3
хода).

4.

СТРУКТУРА ПРОГРАММЫ
1) создание таблицы, в которой будут храниться результаты игры;
2) рекурсивное заполнение таблицы с результатами (при этом
смысл чисел в таблице меняется: если в итоговом выводе число
5 означает победу Пети на 5 ходе, то при рекурсивном
заполнении таблицы число 5 в проверке будет означать
выигрыш Вани на 5 ходе, а не Пети);
3) вывод результатов (при этом никак не помечается, мог ли игрок
выиграть за меньшее количество ходов при другой игре
соперника: результаты нужно перепроверять вручную, в ответ
попадает самая длинная игра).

5.

ТИП 1: КОЛИЧЕСТВО
КАМНЕЙ В КУЧАХ
УВЕЛИЧИВАЕТСЯ

6.

1: УСЛОВИЕ
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает
Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два
раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок,
сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней. В начальный
момент в первой куче было семь камней, во второй куче – S камней; 1 ≤ S ≤ 69.
Задание 19.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая
ситуация возможна.
Задание 20.
Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

7.

1: СОЗДАНИЕ ТАБЛИЦЫ
19-е задание пропускаем, сначала решаем 20-е задание.
Код ниже создаёт таблицу из SUMMA*2 строк и SUMMA*2 колонок:
SUMMA = 77
t = [ [0]*2*SUMMA for i in range(2*SUMMA) ]
SUMMA – сумма, при которой завершается игра.
Нумерация колонок и строк таблице начинается с 0.
Если в ячейке таблицы t[x][y] записано число 2, то это означает, что если в начале игры в первой куче
было Х камней, а во второй куче было У камней, то Петя гарантированно побеждает на 2 ходу.
Если в ячейке таблицы t[x][y] записано число -3, то это означает, что если в начале игры в первой куче
было Х камней, а во второй куче было У камней, то Ваня гарантированно побеждает на 3 ходу.
Таблица большая, т.к. разбираются все возможные ходы и есть ходы типа (1; 76) -> (1; 76*2)

8.

1: РЕКУРСИВНОЕ ЗАПОЛНЕНИЕ ТАБЛИЦЫ
Перебираем все возможные сочетания из Х камней в первой куче и У
камней во второй куче. Сумма Х и У не может быть больше 76 (это конец
игры). Начинаем перебирать с конца:
for x in range(SUMMA-1, 0, -1):
for y in range(SUMMA-x-1, 0, -1):
….
Почему перебор начинается именно с конца, мы разбирать не будем:
это нужно для того, чтобы задачу можно было решить рекурсивно.
Изменять порядок перебора нельзя.

9.

1: РЕКУРСИВНОЕ ЗАПОЛНЕНИЕ ТАБЛИЦЫ
Внутри цикла в отдельную переменную сохраним все возможные
ходы Пети:
for x in range(SUMMA-1, 0, -1):
for y in range(SUMMA-x-1, 0, -1):
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ]

10.

1: РЕКУРСИВНОЕ ЗАПОЛНЕНИЕ ТАБЛИЦЫ
Если в таблице в t[x][y] стоит положительное число, это значит, что при таких Х и У Петя
побеждает. Но в нашем случае Х и У – это числа не ДО Петиного хода, это числа в ПОСЛЕ
Петиного хода, т.е. это начальные условия для Вани. Поэтому если в PetyaHod
оказывается положительное число, Петя не выигрывает, а, наоборот, проигрывает! Петя
будет выигрывать, если в PetyaHod оказалось отрицательное число. Нули тоже считаем
выигрышными для Пети (красивого объяснения здесь нет, это нужно, чтобы таблицу
можно было рекурсивно заполнить):
for x in range(SUMMA-1, 0, -1):
for y in range(SUMMA-x-1, 0, -1):
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ]
PetyaWin = [V for V in PetyaHod if V <= 0] # выбираем отрицательные числа из PetyaHod

11.

1: РЕКУРСИВНОЕ ЗАПОЛНЕНИЕ ТАБЛИЦЫ
Программа ищет наиболее оптимальные стратегии и для Пети, и для Вани, поэтому если Петя
может выиграть, он будет стараться выиграть и сделать это за наименьшее количество ходов.
Это значит, что он возьмёт самое маленькое отрицательное число из Ваниного результата
(отрицательное – значит, Ваня проиграл, маленькое – значит, проиграл за маленькое число
ходов).
…. # продолжение программы с предыдущего слайда
if PetyaWin:
t[x][y] = -max(PetyaWin) + 1
Если Ваня проиграл за N ходов, то Петя выиграл за N + 1 ход, поэтому к ответу добавляем
единицу. Минус нам нужен, т.к. Ванин проигрыш (для Вани обозначается отрицательным
числом) это Петин выигрыш (для Пети обозначается положительным числом).

12.

1: РЕКУРСИВНОЕ ЗАПОЛНЕНИЕ ТАБЛИЦЫ
Если Петя не может победить, значит, побеждает Ваня. Программа будет играть за Петю
наиболее оптимальным образом (т.е. Петя будет стараться максимально растянуть игру,
надеясь на ошибку противника). Если Ваня победил за N ходов, то Петя проиграл тоже за N
ходов, поэтому:
…. # продолжение программы
if PetyaWin:
t[x][y] = -max(PetyaWin) + 1
else:
t[x][y] = -max(PetyaHod)
Берём максимальное положительное число из PetyaHod, т.к. Петя будет вести максимально
длинную игру при проигрыше, берём со знаком минус, т.к. при безошибочной игре Вани Петя
проигрывает.

13.

1: ВЫВОД ОТВЕТА
…. # продолжение программы
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if t[x][y] == 2: # Петя победил на втором ходе
print(y) # выводим начальное количество камней во 2-й куче
Программа выводит всего 2 значения: 31 и 34. В условии просили найти два значения S, при
которых Петя выигрывает вторым своим ходом, но не может выиграть первым. Это значит,
что в данном случае значения 31 и 34 можно не перепроверять: других вариантов у нас всё
равно нет.
Ответ: 31 34

14.

1: ВСЯ ПРОГРАММА (20-Е ЗАДАНИЕ)
SUMMA = 77 # сумма, необходимая для выигрыша
t = [ [0]*2*SUMMA for i in range(2*SUMMA) ]
for x in range(SUMMA-1, 0, -1):
for y in range(SUMMA-x-1, 0, -1):
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ] # возможные ходы из текущей позиции
PetyaWin = [V for V in PetyaHod if V <= 0]
if PetyaWin:
t[x][y] = -max(PetyaWin) + 1
else:
t[x][y] = -max(PetyaHod)
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if t[x][y] == 2: # Петя победил на втором ходе
print(y)

15.

1: РЕШЕНИЕ 21-ГО ЗАДАНИЯ
Т.к. программа играет оптимально и за Ваню, и за Петю, то чтобы найти значения S, при которых Ваня
выигрывает 2-м ходом, достаточно поменять условие в выводе:
…. # продолжение программы
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if t[x][y] == -2: # Ваня победил на втором ходу
print(y) # выводим начальное количество камней во 2-й куче
Программа выводит числа 30 и 33. Минимальное число – 30, но нужно проверить, что в таком случае есть
какой-то Петин ход, позволяющий выиграть Ване за 1 ход.
Проверяем: (7, 30) -> (7, 60) -> (7, 120). Если Петя первым своим ходом умножит количество камней во 2-й куче
в 2 раза, Ваня выиграет за 1 ход. Значение 30 подходит в качестве ответа. Ответ: 30
Готовая программа находится на следующем слайде.

16.

1: РЕШЕНИЕ 21-ГО ЗАДАНИЯ
SUMMA = 77 # сумма, необходимая для выигрыша
t = [ [0]*2*SUMMA for i in range(2*SUMMA) ]
for x in range(SUMMA-1, 0, -1):
for y in range(SUMMA-x-1, 0, -1):
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ] # возможные ходы из текущей позиции
PetyaWin = [V for V in PetyaHod if V <= 0]
if PetyaWin:
t[x][y] = -max(PetyaWin) + 1
else:
t[x][y] = -max(PetyaHod)
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if t[x][y] == -2: # Ваня победил на втором ходе (изменения только здесь)
print(y)

17.

1: РЕШЕНИЕ 19-ГО ЗАДАНИЯ
Программа для 20 и 21 задания не совсем подходит для решения 19-го задания, т.к. в
ней Петя должен играть с ошибкой. Чтобы найти ответ, программу можно немного
изменить: оставить таблицу t с правильными решениями и добавить таблицу d для
вычисления результатов при неправильном ходе Пети.
SUMMA = 77
t = [ [0]*2*SUMMA for i in range(2*SUMMA) ] # таблица ОПТИМАЛЬНОЙ игры Пети
d = [ [0]*2*SUMMA for i in range(2*SUMMA) ] # таблица для игры Пети с ошибкой

18.

1: РЕШЕНИЕ 19-ГО ЗАДАНИЯ
После заполнения таблицы t добавляем кусок кода, который заполняет таблицу d. В таблице d
Ваня должен выигрывать за 1 ход, а Петя должен проигрывать за 1 ход:
# СТРОИМ ТАБЛИЦУ, В КОТОРОЙ ПЕТЯ ДОПУСКАЕТ ОШИБКУ И ПРОИГРЫВАЕТ ЗА 1 ХОД
for x in range(SUMMA-1, 0, -1):
for y in range(SUMMA-x-1, 0, -1):
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ]
PetyaLose = [V for V in PetyaHod if V == 1] # Ваня выигрывает за 1 ход
if PetyaLose:
d[x][y] = -1 # Петя проигрывает за 1 ход
Остальные варианты нас просто не интересуют, поэтому мы их не заполняем.

19.

1: РЕШЕНИЕ 19-ГО ЗАДАНИЯ
Результат выводим, естественно, для таблицы d:
# ВЫВОД ОТВЕТА
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if d[x][y] == -1: # Ваня выигрывает за 1 ход после Петиной ошибки
print(y)
Вывод программы: числа 18, 19, 20, 21 … Минимальное число – 18. Ответ: 18
Готовая программа находится на следующем слайде.

20.

1: РЕШЕНИЕ 19-ГО ЗАДАНИЯ
SUMMA = 77
t = [ [0]*2*SUMMA for i in range(2*SUMMA) ] # таблица ОПТИМАЛЬНОЙ игры Пети
d = [ [0]*2*SUMMA for i in range(2*SUMMA) ] # таблица для игры Пети с ошибкой
# СТРОИМ ТАБЛИЦУ, В КОТОРОЙ ПЕТЯ НЕ ДОПУСКАЕТ ОШИБОК
for x in range(SUMMA-1, 0, -1):
# х — количество камней в первой куче
for y in range(SUMMA-x-1, 0, -1):
# y — количество камней во второй куче
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ] # возможные ходы из текущей позиции
PetyaWin = [c for c in PetyaHod if c <= 0]
if PetyaWin:
# если Петя может выиграть, он будет стараться выиграть
t[x][y] = -max(PetyaWin) + 1
else:
# если Петя проигрывает
t[x][y] = -max(PetyaHod)
# СТРОИМ ТАБЛИЦУ, В КОТОРОЙ ПЕТЯ ДОПУСКАЕТ ОШИБКУ И ПРОИГРЫВАЕТ ЗА 1 ХОД
for x in range(SUMMA-1, 0, -1):
# х — количество камней в первой куче
for y in range(SUMMA-x-1, 0, -1):
# y — количество камней во второй куче
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ] # возможные ходы из текущей позиции
PetyaLose = [V for V in PetyaHod if V == 1] # Ваня выигрывает за 1 ход
if PetyaLose:
# если Петя может проиграть Ване за 1 ход, он должен проиграть
d[x][y] = -1
# Петя проигрывает
# ВЫВОД ОТВЕТА
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if d[x][y] == -1: # Ваня выигрывает за 1 ход после Петиной ошибки
print(y, d[x][y])

21.

1: О ПОСТРОЕНИИ ТАБЛИЦЫ t
Если Вы запускаете программу в IDLE, то t у Вас сохраняется после первого решения
(20-го задания) и перестраивать t не нужно. Тогда при решении 21-го и 19-го заданий
t можно не строить заново. Т.е. если Вы уже решили 20-е задание, для решения 21-го
достаточно запустить только код для вывода ответа:
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if t[x][y] == -2: # Ваня победил на втором ходе (изменения только здесь)
print(y)

22.

1: О ПОСТРОЕНИИ ТАБЛИЦЫ t
Программа для решения 19-го задания при построенной таблице t:
d = [ [0]*2*SUMMA for i in range(2*SUMMA) ] # таблица для игры Пети с ошибкой
# СТРОИМ ТАБЛИЦУ, В КОТОРОЙ ПЕТЯ ДОПУСКАЕТ ОШИБКУ И ПРОИГРЫВАЕТ ЗА 1 ХОД
for x in range(SUMMA-1, 0, -1):
for y in range(SUMMA-x-1, 0, -1):
PetyaHod = [ t[x+1][y], t[2*x][y], t[x][y+1], t[x][2*y] ] # возможные ходы из текущей позиции
PetyaLose = [V for V in PetyaHod if V == 1]
if PetyaLose:
d[x][y] = -1
# ВЫВОД ОТВЕТА
x = 7 # в первой куче 7 камней
for y in range(1, SUMMA-x, 1):
if d[x][y] == -1: # Ваня

23.

1: ИТОГ
Даже если Вы не до конца понимаете отдельные участки кода (например, строчку
создания таблицы t), эти отдельные строчки всегда можно выучить. Смотрите сами,
что Вам проще: выучить наизусть несколько строчек кода (но написать их на экзамене
нужно будет без единой ошибки) или решить задачу математически.
Код программ для заданий 19-21 находится в курсе в файле «Пример 19-21.txt».

24.

ТИП 2: КОЛИЧЕСТВО
КАМНЕЙ В КУЧАХ
УМЕНЬШАЕТСЯ

25.

2: УСЛОВИЕ
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может убрать из одной из куч один камень или уменьшить количество камней в куче в два раза (если количество камней в
куче нечётно, остаётся на 1 камень больше, чем убирается). Игра завершается в тот момент, когда суммарное количество камней в кучах
становится не более 40. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет
40 или меньше камней. В начальный момент в первой куче было 20 камней, во второй куче — S камней, S > 20.
Задание 19.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите максимальное значение S, когда такая ситуация
возможна.
Задание 20.
Найдите три наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.
Задание 21
Найдите максимальное значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

26.

2: ИЗМЕНЕНИЕ ПРОГРАММЫ ПОД 2-Й ТИП
Для того, чтобы рекурсивно заполнить таблицу при уменьшении количества камней в кучах, требуется:
1) определиться с максимальным размером таблицы (теперь мы сверху не ограничены)
2) понять, как запустить циклы в обратном порядке;
3) понять, как изменить формулы (в вычислении следующего хода).
Максимальный размер возьмём таким: SUMMA * 16. Такой размер таблицы позволяет вычислить игру
минимум в 4 хода.
SUMMA = 40
MAXS = 16*SUMMA
t = [ [0]*MAXS for i in range(MAXS) ]
Максимальный размер таблицы во всех задачах на уменьшение берём хотя бы 16*SUMMA.

27.

2: ИЗМЕНЕНИЕ ПРОГРАММЫ ПОД 2-Й ТИП
Запуск циклов в обратном порядке:
# СТРОИМ ТАБЛИЦУ ИГРЫ
for x in range(1, MAXS, 1):
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
…..
# ВЫВОД ОТВЕТА
x = 20
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
….
Если не очень понятно, почему нужно именно так запустить циклы, остаётся одно: зазубрить эти три
строчки кода.

28.

2: ИЗМЕНЕНИЕ ПРОГРАММЫ ПОД 2-Й ТИП
Теперь изменим формулы в PetyaHod.
Убрать камень из одной кучи легко:
PetyaHod = [ t[x-1][y], t[ ??? ][y], t[x][y-1], t[x][ ??? ] ]
Теперь уменьшим количество камней в куче в 2 раза, причём если камней – нечётное
количество, лишний камень заберём:
PetyaHod = [ t[x-1][y], t[ x//2 ][y], t[x][y-1], t[x][ y//2 ] ]
Но по условию ведь нам нельзя забирать лишний камень, он должен остаться в куче, поэтому:
PetyaHod = [ t[x-1][y], t[x//2 + x%2][y], t[x][y-1], t[x][y//2 + y%2] ]

29.

2: ИЗМЕНЕНИЕ ПРОГРАММЫ ПОД 2-Й ТИП
Всё. Больше никаких изменений нет.
Программы для решения заданий 20, 21 и 19 на следующих
слайдах.

30.

2: ВСЯ ПРОГРАММА (20-Е ЗАДАНИЕ)
SUMMA = 40 # минимальное количество камней
MAXS = 16*SUMMA # берём хотя бы 16
t = [ [0]*MAXS for i in range(MAXS) ]
# СТРОИМ ТАБЛИЦУ БЕЗОШИБОЧНОЙ ИГРЫ
for x in range(1, MAXS, 1):
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
PetyaHod = [ t[x-1][y], t[x//2 + x%2][y], t[x][y-1], t[x][y//2 + y%2] ]
PetyaWin = [V for V in PetyaHod if V <= 0]
if PetyaWin:
t[x][y] = -max(PetyaWin) + 1
else:
t[x][y] = -max(PetyaHod)
# ВЫВОД ОТВЕТА ДЛЯ 20-ГО ЗАДАНИЯ
x = 20
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
if t[x][y] == 2: # Петя выигрывает в 2 хода
print(y)
Программа выводит числа 42, 43, 61, 81, 82.
Вывод программы нужно перепроверить (что
Петя не может выиграть за 1 ход).
После перепроверки оказывается, что первые
три наименьших значения (42, 43, 61)
подходят.
Ответ: 42 43 61

31.

2: ВСЯ ПРОГРАММА (21-Е ЗАДАНИЕ)
SUMMA = 40 # минимальное количество камней
MAXS = 16*SUMMA # берём хотя бы 16
t = [ [0]*MAXS for i in range(MAXS) ]
# СТРОИМ ТАБЛИЦУ БЕЗОШИБОЧНОЙ ИГРЫ
for x in range(1, MAXS, 1):
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
PetyaHod = [ t[x-1][y], t[x//2 + x%2][y], t[x][y-1], t[x][y//2 + y%2] ]
PetyaWin = [V for V in PetyaHod if V <= 0]
if PetyaWin:
t[x][y] = -max(PetyaWin) + 1
else:
t[x][y] = -max(PetyaHod)
# ВЫВОД ОТВЕТА ДЛЯ 21-ГО ЗАДАНИЯ
x = 20
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
if t[x][y] == -2: # Ваня выигрывает в 2 хода
print(y)
Программа выводит единственное число — 44.
Ничего перепроверять не будем, всё равно
других вариантов нет.
Ответ: 44

32.

2: ВСЯ ПРОГРАММА (19-Е ЗАДАНИЕ)
SUMMA = 40 # минимальное количество камней
MAXS = 16*SUMMA # берём хотя бы 16
t = [ [0]*MAXS for i in range(MAXS) ]
# СТРОИМ ТАБЛИЦУ БЕЗОШИБОЧНОЙ ИГРЫ
for x in range(1, MAXS, 1):
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
PetyaHod = [ t[x-1][y], t[x//2 + x%2][y], t[x][y-1], t[x][y//2 + y%2] ]
PetyaWin = [V for V in PetyaHod if V <= 0]
if PetyaWin:
t[x][y] = -max(PetyaWin) + 1
else:
t[x][y] = -max(PetyaHod)
# РЕШЕНИЕ 19-ГО ЗАДАНИЯ
d = [ [0]*MAXS for i in range(MAXS) ]
# СТРОИМ ТАБЛИЦУ, В КОТОРОЙ ПЕТЯ ДОПУСКАЕТ ОШИБКУ И ПРОИГРЫВАЕТ ЗА 1 ХОД
for x in range(1, MAXS, 1):
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
PetyaHod = [ t[x-1][y], t[x//2 + x%2][y], t[x][y-1], t[x][y//2 + y%2] ]
PetyaLose = [V for V in PetyaHod if V == 1]
if PetyaLose:
d[x][y] = -1
# ВЫВОД ОТВЕТА ДЛЯ 19-ГО ЗАДАНИЯ
x = 20
for y in range(max(SUMMA-x+1, 1), MAXS, 1):
if d[x][y] == -1: # Ваня выигрывает за 1 ход после Петиной ошибки
print(y)
Программа выводит много чисел: 22, 23, 24 …
78, 79, 80. Максимальное — 80.
Ответ: 80