Автор статьи: Андрей Рогов
Введение
Продолжаем разбирать задания ЕГЭ по информатике. Прежде чем изучать решения в электронных таблицах, рекомендуем ознакомиться с аналитическим решением в статье по ссылке.
Нет единого способа решения в электронных таблицах. Вот для чего их можно использовать:
- оформление решения на поиск позиций вручную
- автоматизация вычислений
- полноценное решение всех заданий
В статье об аналитическом решении электронные таблицы использовались для наглядного изображения игровых позиций. Это помогает их упорядочить. А в задании на две кучи камней (№ 20 и 21) легко увидеть позиции, которые требуются по условию. Поэтому рассмотрим, как можно автоматизировать вычисления, и выйдем на полное решение всех трёх заданий.
Задача 1. Одна куча камней, два разных хода
Ссылка на задачу 19\
Ссылка на задачу 20\
Ссылка на задачу 21
В отличие от аналитического решения, мы не будем просчитывать все позиции, а сразу перейдём к поиску ответов на задания. Для этого создадим математическую модель игры.
Выстроим необходимое количество ходов и с помощью условного форматирования будем отслеживать победы и поражения. Для решения будем использовать программу Libre Office Calc, но эти средства универсальны и есть в других редакторах.
Чтобы отслеживать все действия, описанные дальше, и применить навык на практике, рекомендуем параллельно с чтением строить таблицы.
Для ответа на вопрос задания № 19 нужно просчитать первый ход первого игрока и первый ход второго игрока. Для первого хода первого игрока существует два варианта, а после первого хода второго игрока возможно четыре различных ситуации, так как на каждый ход первого игрока приходится два варианта хода второго.
Построим электронную таблицу, которая вычисляет все возможные значения камней в куче. Для удобства кратко оформим условия задачи, возможные ходы и количество камней для победы.
Синими стрелками показаны ходы, которые может сделать первый игрок. А зелёными — ходы, которые может сделать второй игрок в зависимости от того, какой ход сделал первый.
Электронные таблицы позволяют рассчитать значение камней в куче после хода и отследить победные ходы. Но чтобы понять, как именно искать ответ на вопрос, нужно разобраться в концепции выигрышных и проигрышных позиций.
В задании № 19 нужны такие позиции, в которых первый игрок не может выиграть своим первым ходом, но второй игрок всегда побеждает своим первым ходом. Для ответа на вопрос необходимо отслеживать, в каком месте количество камней превысило 301. Можно отслеживать вручную, но для удобства настроим условное форматирование так, чтобы ячейки с количеством камней для победы выделялось цветом.
Условное форматирование позволяет автоматически применять форматирование к ячейкам, исходя из их значений. Зайдём в меню управления условным форматированием: Формат → Условное → Управление. Будем применять два стиля форматирования: «Хорошо» для ячеек игрока, который должен побеждать по условию задачи, и «Плохо» для ячеек его противника.
По условию задания № 19 побеждать должен второй игрок. Добавим условие: для ячеек столбца Е при значении ячейки больше или равно 301 применить стиль «Хорошо», а для ячеек столбца D применить стиль «Плохо» при том же условии.
Следующий этап решения — поиск подходящих позиций. Для этого будем менять число в ячейке С2, где хранится начальное количество камней в куче.
Для начала запишем в ячейку число 300 — наибольшее количество камней, которое может быть. Тогда электронная таблица изменится.
Ячейки с 1 ходом первого игрока выделены стилем «Плохо». Это означает, что при начальном количестве камней в куче 300 первый игрок победит любым своим ходом. А для задания № 19 это плохо, поскольку первый игрок не может выиграть своим первым ходом.
Будем уменьшать начальное количество камней в куче до тех пор, пока форматирование ячеек не изменится. Это произойдёт при значении 297.
Верхняя ячейка хода первого игрока изменила форматирование на стандартное. Это означает, что на этом ходу игра не заканчивается. И далее второй игрок любым своим ходом побеждает, поскольку оба значения, соответствующие ходам из его ячейки, окрасились зелёным.
Нижняя ячейка хода первого игрока всё ещё красная. Это означает, что, если первый игрок сделает ход умножить на 5, он победит. Это не соответствует вопросу задания № 19.
Сформулируем, какую картину мы ожидаем увидеть, чтобы получить верную ситуацию для задания № 19. Поскольку первый игрок не должен победить своим первым ходом, в столбце D ячейки должны быть без форматирования. При этом второй игрок должен победить своим первым ходом. Для этого у него должен быть хотя бы один ход, приводящий к победе, для любого хода первого игрока. Соответственно, хотя бы одна ячейка из двух, которая обозначает ход второго игрока (светло-зелёные и тёмно-зелёные на рисунке) и соответствует первому ходу первого игрока, должна быть зелёной.
Если просто уменьшать значение на 1 в ячейке с начальным количеством камней, то подбор может занять много времени. Удобно пользоваться бинарным поиском и каждый раз брать значение из середины.
Например, мы выяснили, что 297 — неподходящее значение. Разделим его примерно пополам и возьмём значение 150. При таком значении первый игрок всё ещё может выиграть первым ходом. Снова возьмём значение в два раза меньше, т. е. 75. Оно тоже выигрышное для первого игрока. Следующее значение — 36, и тогда первый игрок уже не может выиграть первым ходом. Но и второй игрок не сможет победить, если первый сделает ход + 3.
Следовательно, нужные значения находятся между 36 и 75. Возьмём середину диапазона — 55. У второго игрока всё ещё не будет выигрышного хода для верхнего хода первого игрока.
Следующим значением возьмём середину между 55 и 75 — 65. Первый игрок сможет победить первым ходом, поэтому рассматриваем значения между 55 и 65, т. е. 60. Оно подходит под условия задания № 19.
Первый игрок не может победить своим первым ходом, но второй игрок побеждает своим первым ходом всегда. Нам необходимо найти наименьшее значение. Поэтому рассмотрим числа от 55 до 60. При значении 57 второй игрок уже не может победить всегда. А при значении 58, независимо от первого хода первого игрока, второй может победить. Следовательно, ответ на задание № 19 — это 58.
Задание № 20
Чтобы ответить на вопрос задания № 20, нужно построить таблицу на ещё один ход первого игрока. При этом мы будем использовать полученные результаты для последнего шага. Такой метод определения последовательности действий, когда сначала выбираются действия для последнего шага, а потом — для предшествующих, называется методом обратной индукции.
По условию победить теперь должен первый игрок. Поэтому в условном форматировании в столбцах первого игрока применим стиль «Хорошо» при числах, больших или равных 301, а в столбцах второго игрока — стиль «Плохо» при том же условии.
Необходимо найти позиции, при которых первый игрок побеждает вторым ходом. Первый игрок определяет первым ходом, из какой позиции будет делать свой ход второй игрок (жёлтый и фиолетовый прямоугольники).
Поэтому для победы первому игроку достаточно, чтобы в красном и зелёном прямоугольнике было хотя бы по одной зелёной клетке. При этом достаточно, чтобы это были красный и зелёный прямоугольники только одной из веток — жёлтой или фиолетовой. Подберём значение, удовлетворяющее всем условиям:
- в ходе второго игрока по одной из веток нет красных клеток
- в ветке, подходящей под первое условие, во втором ходе первого игрока есть хотя бы одна зелёная клетка на каждый ход второго игрока
Первым подходящим значением (если искать по убыванию от числа 57) будет 56.
Если первый игрок сходит в 59, он победит своим вторым ходом при любом ходе второго игрока. Второе значение, обладающее теми же свойствами, — это 55. А вот при значении 54 у второго игрока есть ход, после которого первый игрок не сможет победить.
Таким образом, мы нашли все подходящие значения для верхней ветки, в которой первый игрок первым ходом добавляет три камня.
Найдём теперь значения для нижней ветки, в которой первый игрок первым ходом умножает количество камней на 5. Существует ровно одно значение, подходящее для нижней ветки, — это 12.
В ответе на вопрос необходимо указать два наименьших значения. Это 12 и 55.
Задание № 21
Для ответа на задание 21 нужно построить ещё один ход. В задании 21 победить должен второй игрок — настроим соответствующим образом условное форматирование.
Определим, как мы будем подбирать начальное количество камней в куче. Первый игрок первым ходом определяет, как дальше пойдёт игра: по верхней ветке (фиолетовый фон) или по нижней (жёлтый фон). Выигрышная стратегия должна быть у второго игрока. Поэтому по обеим веткам второй игрок должен побеждать. Каждая подветка внутри фиолетовой и жёлтой веток должна приводить к победе второго игрока. Рассмотрим ситуацию, при которой начальное значение камней в куче 54.
Если первый игрок сделал ход + 3, второй игрок тоже делает + 3. Тогда второй игрок побеждает своим вторым ходом, какой бы ход ни сделал первый. Если первый игрок первым ходом делает ход × 5, второй игрок тоже делает ход × 5 и побеждает своим первым ходом. Это полностью соответствует условию задания № 21.
Позиции 53 и 52 будут аналогичными. А вот в позиции 51 одна из веток становится невыигрышной для второго игрока (обозначено красным прямоугольником).
Все подходящие позиции: 52, 53 и 54. Наименьшая из них — это 52.
Задача 2. Убираем камни
Ссылка на задачу 19\
Ссылка на задачу 20\
Ссылка на задачу 21
В этом задании камни не добавляются, а убираются. Сложность представляет только третий ход, когда количество камней уменьшается в 4 раза, поскольку происходит округление в меньшую сторону. Для такой операции в электронных таблицах есть функция ОКРУГЛВНИЗ, принимающая два аргумента: число, которое необходимо округлить, и количество знаков после запятой.
Так как в задаче три различных хода, на каждый ход одного игрока будет приходиться по три разных хода другого. Поэтому таблица будет выглядеть больше. Оформим таблицу на первые ходы каждого игрока и добавим условное форматирование.
Затем подбором найдём значение, при котором Петя не выигрывает первым ходом, но Ваня выигрывает при любом ходе Пети. Таким значением будет 124.
Задание № 20
Построим таблицу для задания № 20, добавим ещё один ход Пети.
Для наглядности можно добавить фон ячеек и внешние границы, скопировать фрагмент таблицы для 19-го задания. При копировании условное форматирование сохраняется. Но для новых ячеек (первый ход Пети) его необходимо добавить.
Найдём значение, при котором хотя бы по одной из веток после первого хода Пети Ваня не будет побеждать (не будет красных ячеек), но Петя победит вторым ходом (хотя бы один ход из трёх после каждого варианта хода Вани будет зелёным).
Первым подходящим значением будет 127, следующее за ним — 128. Первым ходом Петя убирает три камня, затем, независимо от хода Вани, Петя может победить.
Два наименьших значения — это 127 и 128.
Задание № 21
Достроим ещё один ход. Так как таблица получится довольно большой, рекомендуем пользоваться полосами прокрутки.
Подберём подходящее значение, чтобы Ваня победил первым (не гарантированно) или вторым ходом. Таким значением будет 132.
Если Петя делает первый ход − 3, Ваня может сходить как − 3, так и − 5. В обоих случаях Петя не сможет победить вторым ходом, но Ваня затем побеждает независимо от хода Пети. Если Петя делает первый ход − 5, Ваня делает ход − 3 и побеждает независимо от хода Пети. Если Петя делает первый ход / 4, Ваня может сразу победить любым своим первым ходом.
Ответом на задание № 19 будет 124, на задание № 20 — 127 и 128, на задание № 21 — 132.
Задача 3. Две кучи камней
Ссылка на задачу 19\
Ссылка на задачу 20\
Ссылка на задачу 21
В задании дано две кучи камней, что значительно усложняет решение. Если раньше задача была одномерной (позиции можно было изобразить в виде ряда чисел), то задача с двумя кучами становится двумерной: позиции теперь изображаются с помощью пары чисел, а для каждого игрока есть четыре варианта хода.
Этот метод применим к таким задачам, но решение будет громоздким. Покажем, как с его помощью получить ответ на задание № 19. А затем опишем другой метод, более подходящий для заданий на две кучи камней.
Таблица для задания № 19 будет выглядеть так.
Обратим внимание на другой вопрос в задании № 19. Нужно найти минимальное значение, чтобы Ваня мог победить после неудачного хода Пети.
Для этого найдем значение, при котором Ваня сможет победить хотя бы в одном случае; таким значением будет 7. В этом случае Петя умножает на 3 вторую кучу, Ваня своим ходом тоже умножает вторую кучу и побеждает.
Можно продолжить решение и найти ответы на все остальные вопросы. Мы же продемонстрируем другой вариант решения задачи на две кучи камней. Для этого построим двумерную таблицу, в которой по оси Х будет количество камней во второй куче, а по оси У — в первой.
Как мы помним из статьи об аналитическом решении, для определения выигрышных позиций за один ход необходимо рассматривать «сильный» ход. В этом случае «сильный» ход — утроить кучу, в которой больше камней. Поэтому заполним ячейки формулой, которая находит максимальное значение из двух куч, утраивает его и суммирует количество камней в двух кучах после хода. Таким образом, содержимым ячеек будет сумма количества камней в двух кучах после «сильного» хода.
Чтобы формулу можно было скопировать на все ячейки, будем использовать смешанную адресацию.
Чтобы отметить выигрышные позиции, используем условное форматирование. Если значение в ячейке больше или равно 65, выделим её зелёным цветом.
После применения формул и условного форматирования получается следующая таблица.
Дополнительно строка с 6 камнями в первой куче выделена жёлтым цветом, так как ответы будем искать именно в ней.
Найдём ответ на задание № 19. Нам необходим такой столбец из выделенной строки, из которого можно попасть в зелёную зону «сильным» ходом. Например, из позиции (6, 5) «сильным» ходом будет умножить на 3 большую кучу, где 6 камней. Тогда это будет позиция (18, 5). Она не выделена зелёным цветом, следовательно (6, 5) нам не подходит.
(6, 7) — минимальная позиция, из которой можно попасть в зелёную зону. Если утроить кучу, где 7 камней, получится позиция (6, 21).
Задание № 20
Для ответа на задание № 20 необходимо найти проигрышные позиции за один ход и выигрышные за два хода. Проигрышные позиции за один ход найти довольно просто: все ходы из них должны идти в выигрышные. «Слабый» ход — добавить один камень. Поэтому мы находим позиции, у которых и справа, и снизу расположены выигрышные, т. е. зелёные позиции. Отметим все такие позиции красным фоном.
Будем отталкиваться от позиций, максимально близких к победе, но которые не позволяют победить. Для победы сумма количества камней в двух кучах должна быть 65.
Рассмотрим позиции, сумма камней в которых равна 64. Например, позиция (10, 54). Её можно получить «сильным» ходом из позиции (10, 18). Из позиции (10, 18) нельзя победить ни одним ходом, но какой бы ход ни сделал игрок из (10, 18), его противник затем побеждает.
Таким свойством будут обладать все позиции, из которых можно попасть в позицию с суммой камней 64, причём сделать это «сильным ходом», т. е. утраивая бóльшую кучу. Это позиции (1, 21), (4, 20), (7, 19), (10, 18), (13, 17) и (16, 16).
Нас интересуют только такие, в которые можно попасть из стартовой позиции (6, S). В позицию (7, 19) можно попасть из (6, 19). Эта позиция обладает теми же свойствами, что и позиция (10, 18). Из неё нельзя победить, но при любом ходе побеждает противник.
Это позиция П1 (проигрышная за один ход), и её можно получить из стартовой позиции (6, 19). Следовательно, позиция (6, 19) выигрышная за два хода.
Из позиции (6, 10) можно попасть в позицию (18, 10), которая аналогична позиции (10, 18). В другие позиции из набора (1, 21), (4, 20), (7, 19), (10, 18), (13, 17) и (16, 16) нельзя попасть из стартовой позиции. Следовательно, мы нашли все выигрышные позиции за два хода. Это позиции (6, 10) и (6, 19).
Ответ на задание № 20 — 10 и 19. Для наглядности изобразим его в виде таблицы. Позиции В1 обозначены зелёным цветом, П1 — красным, В2 — тёмно-зелёным.
Для поиска позиций П2 рассмотрим соседние с В2 позиции. Это (6, 9) и (6, 18). Из позиции (6, 9) существует ход в (7, 9) — неопределённую позицию. А вот для (6, 18) все ходы можно рассчитать.
Ходы в (18, 18) и (6, 54) сразу приводят к победе второго игрока, а из позиций (7, 18) и (6, 19) существует ход в (7, 19), это проигрышная позиция (рассмотрели в задании № 20). Таким образом, позиция (6, 18) удовлетворяет всем условиям задания № 21.
Из таблицы мы видим, что такая позиция одна.
Заключение
Мы рассмотрели аналитический подход к решению заданий № 19, 20 и 21 ЕГЭ по информатике. Он эффективен при решении заданий различных уровней сложности, от простых игр с одной кучей до сложных игр с несколькими кучами и типами ходов. Аналитический метод — фундамент для решения в электронных таблицах или программированием.
Метод обратной индукции — универсальный инструмент для определения выигрышных и проигрышных позиций. Очень важно понимать концепции «сильного» и «слабого» хода, чтобы быстро определять критические позиции.
Для подготовки к ЕГЭ по информатике рекомендуем попрактиковаться и решить подборки задач:
Рекомендуем решить подборки задач для практики