Задание 19
Теория игр
Типов: 4
Как распознать
Ходы +1, +3, *2; победа при s >= 39.
Условие
Найти стартовые значения по условиям заданий 19-21.
Разбор
m хранит оставшиеся ходы; any используется на своём ходе, all на ходе соперника.
Шаблон
def f(s, m):
if s >= 39: return m%2==0
if m == 0: return 0
h = [f(s+1,m-1),f(s+3,m-1),f(s*2,m-1)] #ходы
return any(h) if m%2 != 0 else all(h)
print([s for s in range(1,39) if f(s,2)])
print([s for s in range(1,39) if not f(s,1) and f(s,3)])
print([s for s in range(1,39) if not f(s,2) and f(s,4)])Как распознать
Ходы -3, -5, //4; победа при s <= 30.
Условие
Найти стартовые значения по условиям заданий 19-21.
Разбор
Используется та же игровая рекурсия с нижней терминальной границей.
Шаблон
def f(s, m):
if s <= 30: return m%2==0
if m == 0: return 0
h = [f(s-3,m-1),f(s-5,m-1),f(s//4,m-1)] #ходы
return any(h) if m%2 != 0 else all(h)
print([s for s in range(31,1000) if f(s,2)])
print([s for s in range(31,1000) if not f(s,1) and f(s,3)])
print([s for s in range(31,1000) if not f(s,2) and f(s,4)])Как распознать
В условии есть фраза после неудачного первого хода Пети.
Условие
Найти S, при котором Ваня выигрывает первым ходом после ошибки Пети.
Разбор
На обоих уровнях достаточно существования хода, поэтому используется any.
Шаблон
def f(s1,s2, m):
if s1+s2 >=59: return m%2==0
if m == 0: return 0
h = [f(s1+1,s2,m-1),f(s1,s2+1,m-1), f(s1*2,s2,m-1),f(s1,s2*2,m-1)] #ходы
return any(h) if m%2 != 0 else any(h)
print([s for s in range(1,54) if f(5,s,2)])Как распознать
Выигрыш только при 50 <= s <= 119; s > 119 отдаёт победу сопернику.
Условие
Ходы +2 и *3, стартовое S от 1 до 49.
Разбор
Для перебора верхней границы верни противоположную чётность.
Шаблон
def f(s,m):
if 50<=s<=119: return m%2==0
if s > 119: return m%2!=0
if m == 0: return 0
h = [f(s+2,m-1),f(s*3,m-1)] #ходы
return any(h) if m%2 != 0 else all(h)
print([s for s in range(1,50) if f(s,2)])
print([s for s in range(1,50) if not f(s,1) and f(s,3)])
print([s for s in range(1,50) if not f(s,2) and f(s,4)])