19 - 21 задание ЕГЭ Информатика - решаем программой

Коротка программа Алексея Кабанова из г. Тольятти.
Видео Алексея Кабанова 2022 г с подробными объяснениями

Для задач с 1 кучей:
#f - функция, которая проверяет, можно ли выиграть за m ходов
#s - текущее количество камней в куче
#с - текущий ход
#m - конечный ход
#если игра окончена, то количество ходов c должно иметь ту же четность, что и m
#т.е. игра может быть закончена не только при c=m, но и раньше.

def f(s,c,m):
    if s>=42: return c%2==m%2                
#проверка: если в куче нужное количество камней, то если целевой игрок выиграл, возвращает true, иначе false
    if c==m: return 0                        
#если игра не закончилась за ходов, то заканчиваем ее
    if (c+1)%2==m%2: return f(s+1,c+1,m) or f(s+3,c+1,m) or f(s*2,c+1,m) 
    else: return f(s+1,c+1,m) and f(s+3,c+1,m) and f(s*2,c+1,m)          
#если это ход целевого игрока, то достаточно победы в одном из вариантов,
#иначе победа должна быть во всех вариантах
for s in range (1,42):
    for m in range (1,5):
        if f(s,0,m)==1:
            print(s,m)
            break           # если нашлась выигрышная стратегия, то закончить вычисления

#для каждой кучи камней проверяется, можно ли выиграть за 1, 2, 3, 4 хода
#в начальный момент времени c=0 - еще никто не ходил

#программа выдает в столбик количество камней в куче и через сколько ходов можно выиграть
# 1 - Петя выиграет за 1 ход
# 2 - Ваня выиграет за 1 ход
# 3 - Петя выиграет за 2 ход
# 4 - Ваня выиграет за 2 ход

Для задач с 2 кучами программа Кабанова из сборника Полякова:

def f(a,b,prevMoves, moveWin):
    if a+b>=77:
        return prevMoves % 2 == moveWin % 2
    if prevMoves==moveWin: return 0
    h = [f(a+1,b,prevMoves+1,moveWin), f(a,b+1,prevMoves+1,moveWin), f(a*2,b,prevMoves+1,moveWin), f(a,b*2,prevMoves+1,moveWin) ]
    return any(h) if (prevMoves+1)%2==moveWin%2 else all(h)
def f1(a,b,prevMoves, moveWin):
    if a+b>=77:
        return prevMoves % 2 == moveWin % 2
    if prevMoves==moveWin: return 0
    h = [f(a+1,b,prevMoves+1,moveWin), f(a,b+1,prevMoves+1,moveWin), f(a*2,b,prevMoves+1,moveWin), f(a,b*2,prevMoves+1,moveWin) ]
    return any(h)
print('19)', min(s for s in range (1,70) if f1(7,s,0,2)))
print('20)', *[s for s in range (1,70) if not f(7,s,0,1) and f(7,s,0,3)])
print('21)', min(s for s in range (1,70) if not f(7,s,0,1) and f(7,s,0,3)))

Усовершенствованная версия программы в видео 2024 года:





Комментарии

Отправить комментарий