Задание 20
Теория игр
Типов: 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)])Как распознать
К одной куче прибавляют 1 или умножают её на 2.
Условие
Первая куча 5, вторая S; победа при сумме не меньше 59.
Разбор
Запиши все ходы обеих куч, используй any и all по чётности глубины.
Шаблон
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 all(h)
print([s for s in range(1,54) if not f(5,s,1) and f(5,s,3)])
print([s for s in range(1,54) if not f(5,s,2) and f(5,s,4)])Как распознать
Выигрыш только при 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)])