Форум » Теория игр » Задача 19 Варианта 3 из генератора » Ответить
Задача 19 Варианта 3 из генератора
s11kai: (№ 4110) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может а) добавить в кучу один камень; б) увеличить количество камней в куче в три раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 56. Если при этом в куче оказалось не более 80 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. В начальный момент в куче было S камней, 1 ≤ S ≤ 55. Ответьте на следующие вопросы: Вопрос 1. Известно, что Ваня выиграл своим первым ходом после первого хода Пети. Назовите минимальное значение S, при котором это возможно. Константин Юрьевич, возник вопрос, не является ли первое задание избыточно – неопределенным, поскольку и так понятно, что после первого хода Пети, Ваня, сразу, не сможет сделать ни второй, ни третий ход - он просто обречен на первый ход. Но в таком случае, исходя из темы: Поиск выигрышной стратегии – Ваня выиграет первым ходом только в одном случае, когда в куче будет 54 камня. А в ответе – 7. Исследуя дерево игры для 7 камней, можно заметить, что Петя пойдет в позицию 21 только в том случае, опять же исходя из тематики, если ребята играют в поддавки. Но в таком случае и Ваня перейдет не в позицию 63, а попытается затянуть игру ходом 21+1 = 22, но, к сожалению, это не спасет его от поражения. Возникает некая неопределенность, которая исчезает, если в вопросе, слово «первого», заменить на слово - «неудачного» или «ошибочного». Задание 19. Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Или как это прописано у Вас в задании P-00 (демо-2021): "Задание 19. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети" Спасибо!
Ответов - 9
s11kai: Прошу прощенья, для второго хода Вани забыл проставить значения *3
Поляков: s11kai пишет: Возникает некая неопределенность, которая исчезает, если в вопросе, слово «первого», заменить на слово - «неудачного» или «ошибочного». Не думаю, что здесь есть неопределенность. Когда мы говорим "после первого хода Пети" мы не предполагаем, что этот ход следует какой-то стратегии, а рассматриваем все возможные ходы Пети. Если написать "после неудачного хода Пети" тут возникнет (уже возникала!) длинная дискуссия по поводу того, что такое "неудачный ход".
s11kai: Правильно ли я Вас понял - отсутствие в условии ключевого слова "стратегия", разрешает, или предполагает, или допускает, что некоторый игрок может сделать "неудачный", или "ошибочный", или просто ход, не гарантирующий достижения победы, а постановка вопроса из демоверсии 21 года - требует больших дискуссий
Поляков: Да, просто любой ход. Даже случайный.
s11kai: Поляков пишет: Да, просто любой ход. Даже случайный. Я думал, раз мы изучаем " Теорию игр. Поиск выигрышной стратегии", то из этого следует по умолчанию, что игроки должны придерживаться этой самой стратегии. В противном случае, в условии должно оговариваться ее отсутствие, что и подтверждает 19 задание демоверсии от 21 года, а не наоборот. Стало быть я ошибался, следовательно для рассматриваемой задачи, будет правомерным рассмотреть только один ход и в Excel это можно сделать следующей формулой: =ОКРВВЕРХ(65/9;1) а в питоне, соответственно: from math import ceil print(ceil(65/9)) Эту идею подсмотрел у Вас, за что Вам огромное спасибо!!!
s11kai: соединив Вашу идею с идеей Алексея Кабанова, получилось и наглядно, и не нужно менять код программы для получения разных ответов: [pre2] from math import ceil from functools import * def m(h): return h+1, h*3 @lru_cache(None) def g(h): if 56<=h<=80:return'w' if h>80:return 'p1' if any(g(i)=='w' for i in m(h)):return 'p1' if all(g(i)=='p1' for i in m(h)):return 'v1' if any(g(i)=='v1' for i in m(h)):return 'p2' if all(g(i)=='p1' or g(i)=='p2' for i in m(h)):return 'v2' ans2 = [] ans3 = [] for i in range(1,55): if g(i)=='p2': ans2.append(i) if g(i)=='v2': ans3.append(i) print("1. ", ceil(56/9) ) print("2. ", sorted(ans2)) print("3. ", sorted(ans3)) [/pre2]
Поляков: s11kai пишет: if all(g(i)=='p1' for i in m(h)):return 'v1' Мне что-то не очень это нравится. По сути тут утверждается, что мы получаем выигрыш за 1 ход, если все ходы ведут в позиции с проигрышем за 1 ход. Но что если есть один ход в позицию с оценкой p1, а второй - в позицию с оценкой p2? Это ведь тоже выигрыш за 1 ход. Или я что-то не понял?
s11kai: Поляков пишет: if all(g(i)=='p1' for i in m(h)):return 'v1' Мне что-то не очень это нравится. По сути тут утверждается, что мы получаем выигрыш за 1 ход, если все ходы ведут в позиции с проигрышем за 1 ход. Но что если есть один ход в позицию с оценкой p1, а второй - в позицию с оценкой p2? Это ведь тоже выигрыш за 1 ход. Или я что-то не понял? Правильно, поэтому данная строка используется только для поиска ответов на 20 и 21 задания, а ответ на 19 задание вычисляется строкой: print("1. ", ceil(56/9) ), которая вообще никаких позиций не рассматривает Что мне тоже не совсем нравится, поскольку, в противном случае, для поиска ответа на 19 задание необходимо заменить all на any т.е. писать: if any(g(i)=='p1' for i in m(h)):return 'v1 , но здесь, хотя-бы просматривается поиск стратегии, в отличии от, чуть ли не генератора случайных чисел: ceil(56/3/3), а для 20 и 21 задания вновь вернуться к if all(g(i)=='p1' for i in m(h)):return 'v1' Но, что поделаешь, если, согласно условию, в 19 задании ребятишки должны играть в разные игры: Петя - в "поддавки", а Ваня, соответственно, в "шашки". Согласитесь, на практике такое вряд ли возможно, так что: "Нравится, не нравится", а составителей заданий не судят!
s11kai: Подумал, что для экзамена важнее минимальность кода, чем красота вывода ответа и вот что у получилось: [pre2] from math import ceil from functools import * def m(h): return h+1, h*3 @lru_cache(None) def g(h): if 56<=h<=80:return'w' if h>80:return 'p1' if any(g(i)=='w' for i in m(h)):return 'p1' if all(g(i)=='p1' for i in m(h)):return 'v1' if any(g(i)=='v1' for i in m(h)):return 'p2' if all(g(i)=='p1' or g(i)=='p2' for i in m(h)):return 'v2' print("v1 min", ceil(56/9) ) for i in range(1,55): if g(i)=='p2' or g(i)=='v2': print(g(i),i) [/pre2] Еще раз, огромная благодарность и Вам, и Алексею Кабанову и другим участникам за форум, несущий просвещение от Москвы до самых до окраин
полная версия страницы